hash and __eq__
arnodel at googlemail.com
Sun May 31 08:24:09 CEST 2009
Piet van Oostrum <piet at cs.uu.nl> writes:
>>>>>> Arnaud Delobelle <arnodel at googlemail.com> (AD) wrote:
>>AD> Piet van Oostrum <piet at cs.uu.nl> writes:
>>>>>>>>> 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).
>>AD> As all the keys could be in the same bucket, O(n) seems correct to me
>>AD> (with n the total number of keys).
> For worst case only (mainly with a badly designed hash function).
... or a cleverly designed data set!
AFAIK, 'complexity' means 'worst case complexity' unless otherwise
More information about the Python-list