# 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.

(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

```