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

EQUAL, and hash tables, and value/object distinctions

    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.

(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).