hash and __eq__

[Terry Reedy]

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().

tjr