Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Re: Any built-in ishashable method ?

Reply
Thread Tools

Re: Any built-in ishashable method ?

 
 
Terry Reedy
Guest
Posts: n/a
 
      01-18-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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Any built-in ishashable method ? Steven D'Aprano Python 0 01-18-2013 12:16 PM
Re: Any built-in ishashable method ? Peter Otten Python 0 01-18-2013 12:06 PM
Re: Any built-in ishashable method ? Terry Reedy Python 0 01-18-2013 11:25 AM
Re: Any built-in ishashable method ? Peter Otten Python 0 01-18-2013 11:22 AM
Re: Any built-in ishashable method ? Dave Angel Python 0 01-18-2013 11:05 AM



Advertisments