On 2009-05-30 17:29, Terry Reedy wrote:
Aaron Brady wrote:
I am writing a mapping object, and I want to ask about the details of
__hash__ and __eq__. IIUC if I understand correctly, the Python
dict's keys' hash codes are looked up first in O( 1 ), then all the
matching hash entries are compared on equality in O( n ). That is,
the hash code just really narrows down the search. Am I correct?
Yes. Even if your mapping object did a linear O(n) search with the hash
value, only testing for equality after finding an equal hash value would
be faster. Your own mapping object can do whatever you want it to do
internally, as long as it provides the appropriate interface. You could,
for instance, make a map that allowed unhashable lists, (unfrozen) sets,
and dicts as heys by using len() as a surrogate for hash().
Only as long as you don't modify the length of those objects serving as keys in
the meantime. But if you're careful about that, knock yourself out.
The important property to maintain is that if two keys compare equal to each
other, then their hashes should equal each other. The reverse does not have to
be true.
--
Robert Kern
"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco
--
http://mail.python.org/mailman/listinfo/python-list
