wells at submute
Nov 8, 2009, 3:01 PM
Post #6 of 7
(349 views)
Permalink
|
|
Re: list vs tuple for a dict key- why aren't both hashable?
[In reply to]
|
|
On Nov 8, 2:42 pm, Mick Krippendorf <mad.m...@gmx.de> 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!
--
http://mail.python.org/mailman/listinfo/python-list
|
