[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: barmar@Think.COM, Greenwald@STONY-BROOK.SCRC.Symbolics.COM*Subject*: EQUAL, and hash tables, and value/object distinctions*From*: Michael Greenwald <Greenwald@STONY-BROOK.SCRC.Symbolics.COM>*Date*: Sun, 3 Jul 88 12:54 EDT*Cc*: jrose@sun.com, edsel!jonl@labrea.stanford.edu, goldman@vaxa.isi.edu, common-lisp@sail.stanford.edu*In-reply-to*: <19880701191544.6.BARMAR@OCCAM.THINK.COM>

Date: Fri, 1 Jul 88 15:15 EDT From: Barry Margolin <barmar@Think.COM> Date: Thu, 30 Jun 88 16:36 EDT From: Michael Greenwald <Greenwald@stony-brook.scrc.symbolics.com> For example, one cannot construct a hash-function for #'= unless you limit the valid keys to not include both a floating point number and two integers that both coerce to that same float. (i.e. (let* ((a (expt 2 56)) (b (1+ a)) (c (float a))) (values (= a b) (= a c) (= b c))) => NIL T T ) Actually, it's not that difficult to construct such a hash function. All it has to do is coerce its argument before hashing, e.g. I think you are confused. The problem isn't in having a valid hash-function ( (DEFUN TRIVIAL-=-HASH (NUMBER) 1) is legal and valid, but inefficient), the problem is which bucket you put a, b, and c in my example above. In other words, what does (DEFUN TEST-BARMAR-HASH () (SETF (GETHASH a TABLE) 0) (SETF (GETHASH b TABLE) 1) (SETF (GETHASH c TABLE) 2) (VALUES (GETHASH a TABLE) (GETHASH b TABLE) (GETHASH c TABLE))) return?) Unless you restrict the domain as specified above, you are in a quandary. If you coerce them all to long-floats, then (TEST-BARMAR-HASH) => 2,2,2 If you coerce them all to integers then (depending on the implementation) you can get (TEST-BARMAR-HASH) => 0,1,2 or 0,2,2 or 2,1,2 (defun =-hash (number) (let ((real (realpart number)) (imag (imagpart number))) (setq number (complex (coerce real 'long-float) (coerce imag 'long-float)))) <compute the hash>) I admit that this isn't a great hash function if you expect your keys to include many bignums that are near each other. But it is guaranteed to be a correct hash (assuming <compute the hash> is well behaved). The hash isn't a problem. It's the fact that #'= isn't transitive. barmar

**Follow-Ups**:**What have hashing and equality to do with each other?***From:*David Vinayak Wallace <Gumby@MCC.COM>

**References**:**EQUAL, and hash tables, and value/object distinctions***From:*Barry Margolin <barmar@Think.COM>

- Prev by Date:
**dynamic extent lisp objects** - Next by Date:
**Re: dynamic extent lisp objects** - Previous by thread:
**EQUAL, and hash tables, and value/object distinctions** - Next by thread:
**What have hashing and equality to do with each other?** - Index(es):