Re: Any built-in ishashable method ?

Discussion in 'Python' started by Terry Reedy, Jan 18, 2013.

  1. Terry Reedy

    Terry Reedy Guest

    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
     
    Terry Reedy, Jan 18, 2013
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dave Angel

    Re: Any built-in ishashable method ?

    Dave Angel, Jan 18, 2013, in forum: Python
    Replies:
    0
    Views:
    140
    Dave Angel
    Jan 18, 2013
  2. Peter Otten

    Re: Any built-in ishashable method ?

    Peter Otten, Jan 18, 2013, in forum: Python
    Replies:
    0
    Views:
    142
    Peter Otten
    Jan 18, 2013
  3. Terry Reedy

    Re: Any built-in ishashable method ?

    Terry Reedy, Jan 18, 2013, in forum: Python
    Replies:
    0
    Views:
    135
    Terry Reedy
    Jan 18, 2013
  4. Peter Otten

    Re: Any built-in ishashable method ?

    Peter Otten, Jan 18, 2013, in forum: Python
    Replies:
    0
    Views:
    138
    Peter Otten
    Jan 18, 2013
  5. Steven D'Aprano

    Re: Any built-in ishashable method ?

    Steven D'Aprano, Jan 18, 2013, in forum: Python
    Replies:
    0
    Views:
    144
    Steven D'Aprano
    Jan 18, 2013
Loading...

Share This Page