[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
EQUAL, and hash tables, and value/object distinctions
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.
(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
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)))
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.