eq and hashing (was Re: [plt-scheme] How to make unit functors?)

On Thu, 29 May 2003, andrew cooke wrote:

>   to make this explicit, consider storing "foo" with key 'j and (for
>   simplicity) a hashtable so big that array indices are hash values.
>   at the time of storage the hash code of 'j is 42, so we put "foo" at
>   index 42.  later, after garbage collection, we want to recover the
>   value associated with 'j.  so we get the hashcode of 'j, which is
>   now 666, and don't find anything.  that's not right, surely?

The key insight here is that as long as anyone has a reference to a
particular symbol value, its hash code won't change. So the fact that our
tree structure holds onto 'a if someone inserts it (as opposed
to merely holding onto 'a's hash code) ensures that  'a = 'a
and (eq-hash-code 'a) = (eq-hash-code 'a) everywhere. Therefore our
structure doesn't have a bug.

On the other hand, if we DIDN'T hold onto the value inserted, and just
used its hash code (for instance if our sets only responded to membership
queries and you couldn't extract a value from them) then we'd have a bug.
On the other hand, we'd have a bug anyway because a != b doesn't imply
that (eq-hash-code a) != (eq-hash-code b).

-jacob