On Fri, 23 Apr 2004, Brian Hurt wrote:

> On Fri, 23 Apr 2004, Xavier Leroy wrote:
>
> > > I think a good addition to the Hashtbl-module
> > > would be a function, that gives back a list of keys
> > > that are in the hash.
> >
> > With your specification (no repetitions in the list), that function
> > would run in quadratic time, which is a sure sign that lists aren't
> > the right data structure here.  (More generally speaking, "lists
> > without repetitions" is almost always the wrong data structure.)
>
> No, I think creating such a list would take O(n log n) time.
>
> OK, we're starting with a hash table.  That means we have a set of
> buckets, each bucket is a set of key/data pairs.  Assume the same key can
> be inserted multiple times (can it?)

Yes it can.
Wouldn't it be easier to avoid duplicated keys???
See http://martin.jambon.free.fr/hashtbl2/Hashtbl2.html
and http://martin.jambon.free.fr/hashtbl2.ml


Martin

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners