list vs tuple for a dict key- why aren't both hashable?

Discussion in 'Python' started by Wells, Nov 8, 2009.

  1. Wells

    Wells Guest

    I'm not quite understanding why a tuple is hashable but a list is not.
    Any pointers? Thanks!
     
    Wells, Nov 8, 2009
    #1
    1. Advertising

  2. Wells

    Dj Gilcrease Guest

    On Sun, Nov 8, 2009 at 11:15 AM, Wells <> wrote:
    > I'm not quite understanding why a tuple is hashable but a list is not.
    > Any pointers? Thanks!


    tuple is hashable because it is immutable whereas a list is mutable.
     
    Dj Gilcrease, Nov 8, 2009
    #2
    1. Advertising

  3. On Sun, 8 Nov 2009, Wells wrote:

    > I'm not quite understanding why a tuple is hashable but a list is not.
    > Any pointers? Thanks!


    The keys of a dict have to be immutable. Lists are mutable, tuples are
    not.

    \t
     
    Tycho Andersen, Nov 8, 2009
    #3
  4. Wells

    MRAB Guest

    Wells wrote:
    > I'm not quite understanding why a tuple is hashable but a list is not.
    > Any pointers? Thanks!


    A hash is created from the object. If the object is mutable then the
    hash can change. Lists are mutable but tuples aren't.
     
    MRAB, Nov 8, 2009
    #4
  5. Wells wrote:
    > I'm not quite understanding why a tuple is hashable but a list is not.


    The short answer has already been given. Here is the long answer:

    For objects p and q, p==q implies hash(p)==hash(q). It is essential for
    dicts and sets that objects used as keys/elements uphold this law, and
    also that, for an object o, hash(o) doesn't change during the lifetime
    of o. What if you write a class that doesn't? Let's see:


    >>> class Thing(object):

    .... def __init__(self, value):
    .... self.value = value
    .... def __eq__(self, other):
    .... return self.value == other.value
    .... def __hash__(self):
    .... return hash(self.value)
    .... def __repr__(self):
    .... return "Thing(%s)" % self.value
    ....
    >>>
    >>> thinglist = [Thing(i) for i in xrange(10)]
    >>>
    >>> thingdict = dict((y,x) for x,y in enumerate(thinglist))
    >>>
    >>> print thingdict[thinglist[5]]

    5
    >>>
    >>> thinglist[5].value = 99
    >>>
    >>> print thingdict[thinglist[5]]

    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    KeyError: Thing(99)


    What happened? __eq__ and __hash__ both depend on a mutable attribute,
    and when that attribute was changed, their outcome changed as well. If a
    Thing is stored as key in a dict and later it's value attribute is
    changed, it cannot be found anymore. Too bad.

    BTW, this doesn't work either:

    >>> print thingdict[Thing(5)]

    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    KeyError: Thing(5)


    wheras this works:

    >>> print thingdict[Thing(6)]

    6


    What has this got to do with lists and tuples? Well, two tuples x and y
    are considered equal, iff:

    >>> all(a==b for a,b in zip(x,y))


    Also, by the law above, hash(x)==hash(y). Since tuples are immutable, x
    and y (and hash(x) and hash(y)) will be equal as long as they live.


    Lists have the same properties regarding equality, but are mutable.
    If we'd use a list as key in a dict and append an element to the list,
    __eq__ and __hash__ would return something different than before the
    append. The list couldn't be found anymore, just like the instance of
    the broken Thing class above. Lists are not hashable, because it would
    lead to untraceable bugs otherwise, and it would confuse beginners.

    This also teaches a lesson on how to implement __eq__ and __hash__, if
    you must. Just make sure your objects always do uphold the law above,
    and do not change in respect to __hash__ during their lifetime. OTOH it
    is possible to do otherwise, as long as you don't try to use these
    objects as elements of a set or keys in a dictionary. But then, why
    would you bother to implement your own __hash__ method?

    Regards,
    Mick.
     
    Mick Krippendorf, Nov 8, 2009
    #5
  6. Wells

    Wells Guest

    On Nov 8, 2:42 pm, Mick Krippendorf <> wrote:
    > Wells wrote:
    > > I'm not quite understanding why a tuple is hashable but a list is not.

    >
    > The short answer has already been given. Here is the long answer:
    >
    > For objects p and q, p==q implies hash(p)==hash(q). It is essential for
    > dicts and sets that objects used as keys/elements uphold this law, and
    > also that, for an object o, hash(o) doesn't change during the lifetime
    > of o. What if you write a class that doesn't? Let's see:
    >
    > >>> class Thing(object):

    >
    > ...     def __init__(self, value):
    > ...         self.value = value
    > ...     def __eq__(self, other):
    > ...         return self.value == other.value
    > ...     def __hash__(self):
    > ...         return hash(self.value)
    > ...     def __repr__(self):
    > ...         return "Thing(%s)" % self.value
    > ...
    >
    > >>> thinglist = [Thing(i) for i in xrange(10)]

    >
    > >>> thingdict = dict((y,x) for x,y in enumerate(thinglist))

    >
    > >>> print thingdict[thinglist[5]]

    > 5
    >
    > >>> thinglist[5].value = 99

    >
    > >>> print thingdict[thinglist[5]]

    >
    > Traceback (most recent call last):
    >   File "<stdin>", line 1, in <module>
    > KeyError: Thing(99)
    >
    > What happened? __eq__ and __hash__ both depend on a mutable attribute,
    > and when that attribute was changed, their outcome changed as well. If a
    > Thing is stored as key in a dict and later it's value attribute is
    > changed, it cannot be found anymore. Too bad.
    >
    > BTW, this doesn't work either:
    >
    > >>> print thingdict[Thing(5)]

    >
    > Traceback (most recent call last):
    >   File "<stdin>", line 1, in <module>
    > KeyError: Thing(5)
    >
    > wheras this works:
    >
    > >>> print thingdict[Thing(6)]

    >
    > 6
    >
    > What has this got to do with lists and tuples? Well, two tuples x and y
    > are considered equal, iff:
    >
    > >>> all(a==b for a,b in zip(x,y))

    >
    > Also, by the law above, hash(x)==hash(y). Since tuples are immutable, x
    > and y (and hash(x) and hash(y)) will be equal as long as they live.
    >
    > Lists have the same properties regarding equality, but are mutable.
    > If we'd use a list as key in a dict and append an element to the list,
    > __eq__ and __hash__ would return something different than before the
    > append. The list couldn't be found anymore, just like the instance of
    > the broken Thing class above. Lists are not hashable, because it would
    > lead to untraceable bugs otherwise, and it would confuse beginners.
    >
    > This also teaches a lesson on how to implement __eq__ and __hash__, if
    > you must. Just make sure your objects always do uphold the law above,
    > and do not change in respect to __hash__ during their lifetime. OTOH it
    > is possible to do otherwise, as long as you don't try to use these
    > objects as elements of a set or keys in a dictionary. But then, why
    > would you bother to implement your own __hash__ method?
    >
    > Regards,
    > Mick.


    Thanks Mick - this was very enlightening!
     
    Wells, Nov 8, 2009
    #6
  7. Wells

    Syeberman Guest

    On Nov 8, 3:42 pm, Mick Krippendorf <> wrote:
    > Wells wrote:
    > > I'm not quite understanding why a tuple is hashable but a list is not.

    >
    > The short answer has already been given.
    >

    The short answer isn't entirely correct, however. Tuples are only
    hashable so long as their elements are all hashable. The
    documentation, though, doesn't properly describe this:
    http://docs.python.org/glossary.html#term-hashable
    "All of Python’s immutable built-in objects are hashable"
     
    Syeberman, Nov 10, 2009
    #7
    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. Erik Max Francis
    Replies:
    10
    Views:
    537
  2. Bengt Richter
    Replies:
    2
    Views:
    297
    Jp Calderone
    Jul 21, 2003
  3. Mr. SweatyFinger
    Replies:
    2
    Views:
    1,998
    Smokey Grindel
    Dec 2, 2006
  4. Davy
    Replies:
    3
    Views:
    1,893
    Wildemar Wildenburger
    Nov 7, 2007
  5. Edward C. Jones
    Replies:
    0
    Views:
    238
    Edward C. Jones
    Jun 15, 2012
Loading...

Share This Page