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

andrew cooke wrote:

>[warning - copied as email; you may want to reply to the list.  what's
>correct protocol on this list?]
>
>Matthew Flatt <mflatt at cs.utah.edu> writes:
>  
>
>>Again, it sounds like you had to keep the item (such as 'a) in the
>>tree, so there's no bug.
>>    
>>
>
>  (if i understand correctly) they're using the hash to locate the
>  item in the tree.  the item itself would only be used once you got
>  to the leaf (since two items could have the same hash value they'd
>  be located at the same leaf)
>
Yes. But the hash code doesn't change for a given symbols as long as it 
is a live.

It is only in the case the symbol becoms unreferenced, removed by the 
garbage collector,
and a new symbol is created that the hash code change. But - when you 
make a new
symbol (that just happens to be spelled the same way as the old) then it 
is only fair
that an eq-hash doesn't give the same code.

Thus as long as they keep the symbols in the datastructure, it is safe 
to use the
eq-hash-code for comparisons in order to locate the symbol in the tree.

>>The underlying principle here is that you're going to compare the items
>>eventually (since a hash key does not uniquely determine an item), so
>>the hash key will work correctly, by definition.
>>    
>>
>  they only do the comparison on the subset (often empty) of items
>  that have the same hash code.
>
But that's okay - since this means that they keep the symbols in the 
data structure
- and then the hash code doesn't change even if there is a garbage 
collector.

-- 
Jens Axel Søgaard