Any built-in ishashable method ?

Terry Reedy tjreedy at udel.edu
Fri Jan 18 13:27:34 CET 2013


On 1/18/2013 6:56 AM, Jean-Michel Pichavant wrote:
> is there any valid test case

You mean use case?

> where key1 != key2 and hash(key1) == hash(key2) ?

This is the normal case. There are many unequal items that have the same 
hash. The point of using hash is to quickly find items in the set/dict 
that *might* be equal to the candidate item, and to place items where 
they can be easily found. The alternative is a unordered list and a 
linear O(n) search, or a sorted list and a bisecting O(log(n)) search. 
(The latter is quite useful when one is doing insertion sort for small N 
or the list is static (or mostly so) and one want to know which items in 
the list bracket a candidate item that is not in the list.)

The rule is key==key implies hash==hash, which is equivalent to hash != 
hash implies key != key.

Reference 3.3 object.__hash__ "The only required property is that 
objects which compare equal have the same hash value;"

> Or is it some kind of design flaw ?

The flaw would be key1 == key2 and hash(key1) != hash(key2). Then the 
set/dict could store equal items multiple times in different places 
(unless it did a linear search of all members, which would make hashing 
pointless!).

-- 
Terry Jan Reedy




More information about the Python-list mailing list