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

[Mick Krippendorf]

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.