From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 1327DBB9B for ; Wed, 12 Oct 2005 13:11:15 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j9CBBEFa009586 for ; Wed, 12 Oct 2005 13:11:14 +0200 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 NAA30278 for ; Wed, 12 Oct 2005 13:11:14 +0200 (MET DST) Received: from mail.physik.uni-muenchen.de (mail.physik.uni-muenchen.de [192.54.42.129]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j9CBBDHk013262 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL); Wed, 12 Oct 2005 13:11:13 +0200 Received: from localhost (unknown [127.0.0.1]) by mail.physik.uni-muenchen.de (Postfix) with ESMTP id 0D6112000B; Wed, 12 Oct 2005 13:11:13 +0200 (CEST) Received: from mail.physik.uni-muenchen.de ([127.0.0.1]) by localhost (mail.physik.uni-muenchen.de [127.0.0.1]) (amavisd-new, port 10024) with LMTP id 16413-01-66; Wed, 12 Oct 2005 13:11:12 +0200 (CEST) Received: from mailhost.cip.physik.uni-muenchen.de (kaiser.cip.physik.uni-muenchen.de [141.84.136.1]) by mail.physik.uni-muenchen.de (Postfix) with ESMTP id DEE4020006; Wed, 12 Oct 2005 13:11:12 +0200 (CEST) Received: from eiger.cip.physik.uni-muenchen.de (eiger.cip.physik.uni-muenchen.de [141.84.136.54]) by mailhost.cip.physik.uni-muenchen.de (Postfix) with ESMTP id 8D8CE26E87; Wed, 12 Oct 2005 13:11:12 +0200 (CEST) Received: by eiger.cip.physik.uni-muenchen.de (Postfix, from userid 3092) id 4FCA912F75; Wed, 12 Oct 2005 13:11:12 +0200 (CEST) Received: from localhost (localhost [127.0.0.1]) by eiger.cip.physik.uni-muenchen.de (Postfix) with ESMTP id 4ABBD12F20; Wed, 12 Oct 2005 13:11:12 +0200 (CEST) Date: Wed, 12 Oct 2005 13:11:12 +0200 (CEST) From: Thomas Fischbacher To: Xavier Leroy Cc: Christian Lindig , Caml List Subject: Re: [Caml-list] EQ hash tables? In-Reply-To: <434CC328.7060803@inria.fr> Message-ID: References: <14893115.1128951765427.JavaMail.www@wwinf1521> <434CC328.7060803@inria.fr> X-BOFH: Daemons did it MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Virus-Scanned: amavisd-new at physik.uni-muenchen.de X-Miltered: at nez-perce with ID 434CEF52.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 434CEF51.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 hash:01 hash:01 hashtbl:01 struct:01 hashtbl:01 semantics:01 structurally:01 semantics:01 2005,:98 cip:98 cip:98 lambda:01 lambda:01 wrote:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 On Wed, 12 Oct 2005, Xavier Leroy wrote: > Easily definable using the functorial interface to hash tables: > > module MyEqHashTable = > Hashtbl.Make(struct > type t = my_type_for_keys > let equal = (==) > let hash = Hashtbl.hash > end) > > > Of course, "EQ hash tables" have to be treated in a slightly special way > > when talking about stop© GCing. > > No, not "of course". You're thinking of using the address of a memory > block as its hash value. This indeed requires GC support. But you > can get the semantics you want (keys compared by reference) while > still computing the hash code structurally. This is what the code > snippet above does. Hm, okay. I agree that this does give me the same semantics. But doesn't this degrade expected lookup performance to an O(n) list lookup if I put a lot of stuff into the hash which is (=) but not (==)? -- regards, tf@cip.physik.uni-muenchen.de (o_ Thomas Fischbacher - http://www.cip.physik.uni-muenchen.de/~tf //\ (lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y) V_/_ (if (= x 0) y (g g (- x 1) (* x y)))) n 1)) (Debian GNU)