hash and __eq__

Robert Kern robert.kern at gmail.com
Sun May 31 00:40:16 CEST 2009

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

More information about the Python-list mailing list