Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Martin Jambon <martin_jambon@e...>
Subject: Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys
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