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 2DA88BB9B for ; Wed, 12 Oct 2005 17:06:28 +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 j9CF6RBB032695 for ; Wed, 12 Oct 2005 17:06:27 +0200 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA03316 for ; Wed, 12 Oct 2005 17:06:27 +0200 (MET DST) Received: from [128.93.11.95] (estephe.inria.fr [128.93.11.95]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j9CF6PhV032687 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 12 Oct 2005 17:06:25 +0200 Message-ID: <434D2670.7000507@inria.fr> Date: Wed, 12 Oct 2005 17:06:24 +0200 From: Xavier Leroy User-Agent: Mozilla Thunderbird 1.0.2 (X11/20050322) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Thomas Fischbacher Cc: Christian Lindig , Caml List Subject: Re: [Caml-list] EQ hash tables? References: <14893115.1128951765427.JavaMail.www@wwinf1521> <434CC328.7060803@inria.fr> In-Reply-To: X-Enigmail-Version: 0.90.0.0 X-Enigmail-Supports: pgp-inline, pgp-mime Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 434D2673.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 434D2671.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 hash:01 semantics:01 hash:01 hash-consing:01 integers:01 data:02 comparison:03 depends:04 inria:05 xavier:06 xavier:06 approach:07 standard:07 okay:07 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 > 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 (==)? Yes, of course. It depends on your application. For things like hash-consing, this approach (standard hash function + comparison finer than (=)) can still work well. Alternatively, you can always put unique integers in the data type used as key. - Xavier Leroy