Any built-in ishashable method ?
Terry Reedy
tjreedy at udel.edu
Fri Jan 18 07:27:34 EST 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