From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA22694; Fri, 23 Apr 2004 18:31:34 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA22754; Fri, 23 Apr 2004 18:31:33 +0200 (MET DST) Received: from out2.smtp.messagingengine.com (out2.smtp.messagingengine.com [66.111.4.26]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i3NGVWYM002993; Fri, 23 Apr 2004 18:31:32 +0200 X-Sasl-enc: SzMTxVWZmDoSxxEKxVfhjA 1082737890 Received: from [192.168.1.100] (unknown [218.81.124.114]) by mail.messagingengine.com (Postfix) with ESMTP id A46EFA9286F; Fri, 23 Apr 2004 12:31:28 -0400 (EDT) Date: Sat, 24 Apr 2004 00:31:22 +0800 (HKT) From: Martin Jambon X-X-Sender: martin@localhost To: Brian Hurt Cc: Xavier Leroy , Oliver Bandel , Subject: Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at concorde by Joe's j-chkmail ("http://j-chkmail.ensmp.fr")! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 hashtbl:01 hash:01 quadratic:01 hash:01 hashtbl:01 jambon:02 jambon:02 wrote:03 wrote:03 data:03 data:03 duplicated:04 bucket:04 pairs:05 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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