hash and __eq__
tjreedy at udel.edu
Sun May 31 00:29:10 CEST 2009
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().
More information about the Python-list