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 -- http://mail.python.org/mailman/listinfo/python-list
