Hashability?

Discussion in 'Python' started by Chris S., Jul 19, 2004.

  1. Chris S.

    Chris S. Guest

    Perhaps this is obvious to some, but why are dictionary keys constrained
    to hashable objects? why not use the object's id for the hash value.
    Wouldn't this allow typically non-hashable objects to be used as keys?
    I've done this in several instances and I've never encountered a problem.
     
    Chris S., Jul 19, 2004
    #1
    1. Advertising

  2. Chris S. wrote:

    > Perhaps this is obvious to some, but why are dictionary keys constrained
    > to hashable objects? why not use the object's id for the hash value.
    > Wouldn't this allow typically non-hashable objects to be used as keys?
    > I've done this in several instances and I've never encountered a problem.


    Bad idea: objects which compare to equality may have different ids

    In [1]: a=(1,2,3)

    In [2]: b=(1,2,3)

    In [3]: a is b
    Out[3]: 0

    Also, if you pickle such a dict and later restore it, all keys now hold bogus
    memory addresses of non-existent stuff.

    What you suggest may work in limited, highly constrained situations. Not a good
    idea for a general purpose tool like dicts.

    Cheers,

    f
     
    Fernando Perez, Jul 19, 2004
    #2
    1. Advertising

  3. Chris S.

    Tim Daneliuk Guest

    Chris S. wrote:

    > Perhaps this is obvious to some, but why are dictionary keys constrained
    > to hashable objects? why not use the object's id for the hash value.
    > Wouldn't this allow typically non-hashable objects to be used as keys?
    > I've done this in several instances and I've never encountered a problem.


    I am interested in the answer to this as well, but it seems to me that
    the objid _is_ itself a hashable item, hence it works... right?

    --
    ----------------------------------------------------------------------------
    Tim Daneliuk
    PGP Key: http://www.tundraware.com/PGP/
     
    Tim Daneliuk, Jul 19, 2004
    #3
  4. Chris S.

    Dan Bishop Guest

    "Chris S." <> wrote in message news:<cdfd0p$ls9$>...
    > Perhaps this is obvious to some, but why are dictionary keys constrained
    > to hashable objects?


    Because dictionaries are implemented as hash tables. But that's not
    helpful, because your real question is "Why were lists and
    dictionaries made unhashable?"

    Well, what do you expect their hash value to be? It can't be based on
    their contents, because those can change. It can't be based on object
    ID, either, because different (in id) lists can be equal (in
    contents), and that violates the principle that x == y implies hash(x)
    == hash(y).

    I suppose the hash code of a mutable type could be defined as always
    zero, which would be consistent, but horrible in terms of efficiency.

    So the only reasonable thing to do is make these types non-hashable.

    > why not use the object's id for the hash value.


    That *is* done by default.

    >>> x = object()
    >>> hash(x)

    1075889080
    >>> id(x)

    1075889080
    >>> {x: 0}

    {<object object at 0x4020c3b8>: 0}

    This is acceptable because the default implementation of the "=="
    operator is the same as the "is" operator, so x == y implies id(x) ==
    id(y) implies hash(x) == hash(y), so it's a consistent hash function.
     
    Dan Bishop, Jul 19, 2004
    #4
  5. On Monday 19 July 2004 3:50 am, Chris S. wrote:
    > Perhaps this is obvious to some, but why are dictionary keys constrained
    > to hashable objects?


    I'm not sure exactly what you mean here. My definition of a "hashable object"
    would be one that can serve as a dictionary key. This is basically all
    classes whose instances, when they compare equal, have the same hash value.

    > why not use the object's id for the hash value.
    > Wouldn't this allow typically non-hashable objects to be used as keys?
    > I've done this in several instances and I've never encountered a problem.


    By default user-defined class do use their ID as their hash value and this is
    fine because by default instances of user-defined classes do not compare
    equal. If you go and define a __cmp__() method for your class and there is a
    danger of instances comparing equal then you need to define the __hash__()
    method too. See the sections on __cmp__() and __hash__() in:

    http://www.python.org/doc/current/ref/customization.html

    Note that Python doesn't even stop you using an immutable type (say a subclass
    of the built-in list type) as a dictionary key if you give it a __hash__()
    method. See the following very bad code. :)

    >>> class MyList(list):

    .... def __hash__(self): return 1
    ....
    >>> l1 = MyList(range(10))
    >>> l1

    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>> l2 = MyList(range(10, 20))
    >>> d = {l1: 1, l2: 2}
    >>> d

    {[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]: 1, [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]:
    2}

    James
    --
    James Henderson, Logical Progression Ltd
    http://www.logicalprogression.net
    http://mailmanager.sourceforge.net
     
    James Henderson, Jul 19, 2004
    #5
  6. Chris S.

    Chris S. Guest

    Chris S. wrote:

    > Perhaps this is obvious to some, but why are dictionary keys constrained
    > to hashable objects? why not use the object's id for the hash value.
    > Wouldn't this allow typically non-hashable objects to be used as keys?
    > I've done this in several instances and I've never encountered a problem.


    I understand the issue now. My thanks to everyone who responded.
     
    Chris S., Jul 19, 2004
    #6
    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. =?iso-8859-1?Q?Fran=E7ois?= Pinard

    Hashability of classes, old and new

    =?iso-8859-1?Q?Fran=E7ois?= Pinard, Feb 16, 2004, in forum: Python
    Replies:
    1
    Views:
    281
    Josiah Carlson
    Feb 16, 2004
  2. James Stroud

    hashability

    James Stroud, Aug 12, 2009, in forum: Python
    Replies:
    20
    Views:
    677
    Carl Banks
    Aug 12, 2009
  3. kj
    Replies:
    4
    Views:
    408
    Arnaud Delobelle
    Oct 7, 2010
  4. Bob Grommes

    Hashability questions

    Bob Grommes, May 13, 2012, in forum: Python
    Replies:
    2
    Views:
    230
    Bob Grommes
    May 15, 2012
Loading...

Share This Page