[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: equals metamethod and hash functions
- From: Paul Chiusano <paul.chiusano@...>
- Date: Thu, 9 Jun 2005 10:13:24 -0400
Thanks for the responses.
> If you can construct hash functions and equality functions for your objects,
> why is it more difficult to stringify? Your __hash metamethod and __eq
> metamethod would have to be perfect, too, in combination.
I'm not sure if we're talking about the same thing... different
objects would be allowed to return the same __hash value, but if they
are different according to __eq, then both are retained as keys in the
table. Is this what you meant by the two methods needing to be perfect
in combination? If so, I think this is easier (not to mention more
space efficient) than using the stringifying approach. With a __hash
metamethod, I only need to be able to write a procedure to compute
equality; without it, I need to *actually produce* a string
representation that can be used to compare two objects for equality...
This might help (or it might be really obvious, if so, sorry! :-) In
java/python, all objects can define a hashCode() method (java) or a
__hash__() method (python). If none is defined, it uses the memory
address of the object. When the object is used as a key in a map, it
starts with the raw value supplied by the hashCode() method, then
transforms that (via modular reduction or something) into an index in
the underlying array that implements the map. If two keys hash to the
same location in the array, the equals method is used to determine if
both belong in the map (they are different according to equals), or if
they are equivalent, in which case only one is retained. get(akey)
works by computing the hashCode of the key, then going to that
location in the table and finding if any entries have a key equal to
akey, in which case, the corresponding value is returned. So really,
it is the equals method that provides the standard for uniqueness, and
the hashCode method is just used to make this speedier... there is the
contract that objects which are equal should return the same hashCode,
otherwise the scheme wouldn't work.
If I had a Pair class that just stored pairs of items, and I want
pairs to be equal if corresponding elements are the same, I could make
my __hash method return say, the sum of the hash values of the
elements stored, and I could make the __eq method compare objects at
the same position in the two pairs, returning true if both
corresponding elements were equal.