>>>>> Arnaud Delobelle <arno...@googlemail.com> (AD) wrote:
>AD> Piet van Oostrum <p...@cs.uu.nl> writes: >>>>>>>> Aaron Brady <castiro...@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). -- Piet van Oostrum <p...@cs.uu.nl> URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4] Private email: p...@vanoostrum.org -- http://mail.python.org/mailman/listinfo/python-list