hash and __eq__

[Piet van Oostrum]

>>>>> Aaron Brady <castironpi at gmail.com> (AB) wrote:

>AB> I am writing a mapping object, and I want to ask about the details of
>AB> __hash__ and __eq__.  IIUC if I understand correctly, the Python
>AB> dict's keys' hash codes are looked up first in O( 1 ), then all the
>AB> matching hash entries are compared on equality in O( n ).  That is,
>AB> the hash code just really narrows down the search.  Am I correct?

The O(1) part is correct. The O(n) is incorrect if n as usual is taken
to be the number of keys in the dict. But it is true if n is the number
of keys in the `bucket' that belongs to the hash value. The average
complexity of looking up a key is O(1).

See http://wiki.python.org/moin/DictionaryKeys
-- 
Piet van Oostrum <piet at cs.uu.nl>
URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4]
Private email: piet at vanoostrum.org