Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!selfless.tophat.at!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
DomainKey-Signature: a=rsa-sha1; c=nofws; d=rebertia.com; s=google; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type :content-transfer-encoding; b=HN1tBEarKGJ3+rslyWHWxi03YyFWLhBocSUyjHK5nX+w+twnSS91hocOTwx+o2hjGg 5u6eBljKkA4Twu0MftAfvINIJG8m5D0bDmOAM6bK/RDYLuUfe8ephT1RGH2nUjMH2s2z g1321bxAnvqcnPe4J5x4zYbtx/EjplVsMshFU=
MIME-Version: 1.0
Sender: chris@rebertia.com
In-Reply-To: <4DD6AB32.7030306@stoneleaf.us>
References: <4DD2C2A5.3080403@stoneleaf.us> <BANLkTimvzZeN5dmm2xHP5xV8Kpw2Nb9kuQ@mail.gmail.com> <4DD2D89D.4000303@stoneleaf.us> <BANLkTintqgBLFtBx8+1b+R10nywuKdKHOw@mail.gmail.com> <4DD2F661.2050005@stoneleaf.us> <BANLkTikx8U4jWwLXXazpmtsL6MasDmyVyg@mail.gmail.com> <BANLkTi=_GqrNntRU7pv7x=kj3gHurk-Gaw@mail.gmail.com> <4DD5FF8F.604@stoneleaf.us> <BANLkTikaJnjK57ySq0hzZwUOUFaQo+accw@mail.gmail.com> <4DD6AB32.7030306@stoneleaf.us>
Date: Fri, 20 May 2011 12:00:43 -0700
Subject: Re: hash values and equality
From: Chris Rebert <clp2@rebertia.com>
To: Ethan Furman <ethan@stoneleaf.us>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: python list <python-list@python.org>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.1854.1305918047.9059.python-list@python.org>
Lines: 85
NNTP-Posting-Host: 82.94.164.166
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:5872

On Fri, May 20, 2011 at 10:56 AM, Ethan Furman <ethan@stoneleaf.us> wrote:
> Chris Rebert wrote:
>> On Thu, May 19, 2011 at 10:43 PM, Ethan Furman <ethan@stoneleaf.us> wrot=
e:
>>> Several folk have said that objects that compare equal must hash equal,
>>> and
>>> the docs also state this
>>> http://docs.python.org/dev/reference/datamodel.html#object.__hash__
>>>
>>> I'm hoping somebody can tell me what horrible thing will happen if this
>>> isn't the case?
<snip>
>> Here's a more common/plausible "horrible" case closer to what the docs
>> writers had in mind:
>> --> class Naughty(object):
>> ... =C2=A0 =C2=A0 def __init__(self, n):
>> ... =C2=A0 =C2=A0 =C2=A0 =C2=A0 self.n =3D n
>> ... =C2=A0 =C2=A0 def __eq__(self, other):
>> ... =C2=A0 =C2=A0 =C2=A0 =C2=A0 return self.n =3D=3D other.n
>> ...
>> --> Naughty(5) =3D=3D Naughty(5)
>> True
>> --> Naughty(5) is Naughty(5)
>> False
>> --> bad =3D Naughty(3)
>> --> y =3D {bad : 'foo'}
>> --> y[bad] # just happens to work
>> 'foo'
>> --> del bad
>> --> # ok, how do we get to 'foo' now?
>> --> y[Naughty(3)] # try the obvious way
>> Traceback (most recent call last):
>> =C2=A0File "<stdin>", line 1, in <module>
>> KeyError: <__main__.Naughty object at 0x2a1cb0>
>> --> # We're screwed.
>>
>> Naughty instances (and similar) can't be used sensibly as hash keys
>> (unless you /only/ care about object identity; this is often not the
>> case).
>
> I tried this sequence (using Python 3, BTW -- forgot to mention that litt=
le
> tidbit -- sorry!):

Doesn't matter anyway.

> --> del two
> --> two
> Traceback (most recent call last):
> =C2=A0File "<stdin>", line 1, in <module>
> NameError: name 'two' is not defined
> --> d
> {<__main__.Wierd object at 0x00C0C950>: '3',
> =C2=A01: '1.0',
> =C2=A02: '2.0',
> =C2=A03: '3.0',
> =C2=A0<__main__.Wierd object at 0x00B3AC10>: '2',
> =C2=A0<__main__.Wierd object at 0x00B32E90>: '1'}
> --> new_two =3D Wierd(2)
> --> d[new_two]
> '2'

Right, this is why I went to the trouble of writing Naughty instead of
using Wierd. Wierd's exact problem is less common and less severe. The
"equality implies identical hash" rule is not a universal one; some
other languages instead impose the lesser requirement of "equality and
same (or related) types implies identical hash". In Ruby for instance:
irb(main):001:0> 1 =3D=3D 1.0
=3D> true
irb(main):002:0> a =3D {1.0 =3D> 'hi'} # float key
=3D> {1.0=3D>"hi"}
irb(main):003:0> a[1] =3D 'bye' # int key
=3D> "bye"
irb(main):004:0> a # notice how they don't collide:
=3D> {1=3D>"bye", 1.0=3D>"hi"}
(Contrast this with my earlier analogous Python example.)

Basically, Naughty is fundamentally broken [hash(Naughty(2)) !=3D
hash(Naughty(2))], whereas Wierd merely defies convention [hash(2) !=3D
hash(Wierd(2)) but hash(Wierd(2)) =3D=3D hash(Wierd(2))].

Cheers,
Chris
--
http://rebertia.com