Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #5816 > unrolled thread

hash values and equality

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  hash values and equality Ethan Furman <ethan@stoneleaf.us> - 2011-05-19 22:43 -0700
    Re: hash values and equality Peter Otten <__peter__@web.de> - 2011-05-20 08:38 +0200
      Re: hash values and equality Ethan Furman <ethan@stoneleaf.us> - 2011-05-20 10:57 -0700
      Re: hash values and equality Peter Otten <__peter__@web.de> - 2011-05-20 22:25 +0200
      Re: hash values and equality Ethan Furman <ethan@stoneleaf.us> - 2011-05-20 14:48 -0700
    Re: hash values and equality Ulrich Eckhardt <ulrich.eckhardt@dominolaser.com> - 2011-05-20 08:33 +0200
      Re: hash values and equality MRAB <python@mrabarnett.plus.com> - 2011-05-20 16:50 +0100
      Re: hash values and equality Chris Angelico <rosuav@gmail.com> - 2011-05-21 02:20 +1000
      Re: hash values and equality Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-20 11:59 -0600
      Re: hash values and equality Ethan Furman <ethan@stoneleaf.us> - 2011-05-20 11:38 -0700
        Re: hash values and equality Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2011-05-21 20:24 +1200
          Re: hash values and equality Peter Otten <__peter__@web.de> - 2011-05-21 11:24 +0200
      Re: hash values and equality Christian Heimes <lists@cheimes.de> - 2011-05-20 21:01 +0200
      Re: hash values and equality MRAB <python@mrabarnett.plus.com> - 2011-05-20 21:17 +0100
        Re: hash values and equality Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-21 00:47 +0000
          Re: hash values and equality MRAB <python@mrabarnett.plus.com> - 2011-05-21 02:02 +0100
            Re: hash values and equality Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-21 01:55 +0000
      Re: hash values and equality John Nagle <nagle@animats.com> - 2011-05-21 15:55 -0700
        Re: hash values and equality Irmen de Jong <irmen.NOSPAM@xs4all.nl> - 2011-05-22 01:07 +0200
        Re: hash values and equality Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-22 00:24 +0000

#5816 — hash values and equality

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?  Here's a toy example of a class I'm thinking of writing 
that will compare equal with int's, but hash differently:

--> class Wierd():
...     def __init__(self, value):
...         self.value = value
...     def __eq__(self, other):
...         return self.value == other
...     def __hash__(self):
...         return hash((self.value + 13) ** 3)
...
--> one = Wierd(1)
--> two = Wierd(2)
--> three = Wierd(3)
--> one
<Wierd object at 0x00BFE710>
--> one == 1
True
--> one == 2
False
--> two == 2
True
--> three == 3
True
--> d = dict()
--> d[one] = '1'
--> d[two] = '2'
--> d[three] = '3'
--> d
{<Wierd object at 0x00BFE710>: '1',
  <Wierd object at 0x00BFE870>: '3',
  <Wierd object at 0x00BFE830>: '2'}
--> d[1] = '1.0'
--> d[2] = '2.0'
--> d[3] = '3.0'
--> d
{<Wierd object at 0x00BFE870>: '3',
  1: '1.0',
  2: '2.0',
  3: '3.0',
  <Wierd object at 0x00BFE830>: '2',
  <Wierd object at 0x00BFE710>: '1'}
--> d[2]
'2.0'
--> d[two]
'2'

All information greatly appreciated!

~Ethan~

[toc] | [next] | [standalone]

#5821

Ethan Furman wrote:

> 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?  Here's a toy example of a class I'm thinking of writing
> that will compare equal with int's, but hash differently:
> 
> --> class Wierd():
> ...     def __init__(self, value):
> ...         self.value = value
> ...     def __eq__(self, other):
> ...         return self.value == other
> ...     def __hash__(self):
> ...         return hash((self.value + 13) ** 3)
> ...

Try this:

>>> d = {Wierd(1): 0}
>>> 1 in d
False
>>> 1 in d.keys()
True

[toc] | [prev] | [next] | [standalone]

#5863

Peter Otten wrote:
> Ethan Furman wrote:
> 
>> 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?  Here's a toy example of a class I'm thinking of writing
>> that will compare equal with int's, but hash differently:
>>
>> --> class Wierd():
>> ...     def __init__(self, value):
>> ...         self.value = value
>> ...     def __eq__(self, other):
>> ...         return self.value == other
>> ...     def __hash__(self):
>> ...         return hash((self.value + 13) ** 3)
>> ...
> 
> Try this:
> 
>>>> d = {Wierd(1): 0}
>>>> 1 in d
> False
>>>> 1 in d.keys()
> True
> 

My apologies -- I'm trying this in Python3:

--> two in d
True
--> two in d.keys()
True
-->
--> 2 in d
True
--> 2 in d.keys()
True

~Ethan~

[toc] | [prev] | [next] | [standalone]

#5881

Ethan Furman wrote:

> Peter Otten wrote:
>> Ethan Furman wrote:
>> 
>>> 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?  Here's a toy example of a class I'm thinking of writing
>>> that will compare equal with int's, but hash differently:
>>>
>>> --> class Wierd():
>>> ...     def __init__(self, value):
>>> ...         self.value = value
>>> ...     def __eq__(self, other):
>>> ...         return self.value == other
>>> ...     def __hash__(self):
>>> ...         return hash((self.value + 13) ** 3)
>>> ...
>> 
>> Try this:
>> 
>>>>> d = {Wierd(1): 0}
>>>>> 1 in d
>> False
>>>>> 1 in d.keys()
>> True
>> 
> 
> My apologies -- I'm trying this in Python3:

Then you have to convert the keys to a list explicitly:

>>> class Weird:
...     def __init__(self, value):
...             self.value = value
...     def __eq__(self, other):
...             return self.value == other
...     def __hash__(self):
...             return hash((self.value + 13) **3)
...
>>> d = {Weird(1): 0}
>>> 1 in d
False
>>> 1 in d.keys()
False
>>> 1 in list(d.keys())
True

[toc] | [prev] | [next] | [standalone]

#5883

Peter Otten wrote:
> Ethan Furman wrote:
> 
>> Peter Otten wrote:
>>> Ethan Furman wrote:
>>>
>>>> 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__
>>>>
>>>> --> class Wierd():
>>>> ...     def __init__(self, value):
>>>> ...         self.value = value
>>>> ...     def __eq__(self, other):
>>>> ...         return self.value == other
>>>> ...     def __hash__(self):
>>>> ...         return hash((self.value + 13) ** 3)
>>>> ...
>>> Try this:
>>>
>>>>>> d = {Wierd(1): 0}
>>>>>> 1 in d
>>> False
>>>>>> 1 in d.keys()
>>> True
>>>
>> My apologies -- I'm trying this in Python3:
> 
> Then you have to convert the keys to a list explicitly:
> 
>>>> class Weird:
> ...     def __init__(self, value):
> ...             self.value = value
> ...     def __eq__(self, other):
> ...             return self.value == other
> ...     def __hash__(self):
> ...             return hash((self.value + 13) **3)
> ...
>>>> d = {Weird(1): 0}
>>>> 1 in d
> False
>>>> 1 in d.keys()
> False
>>>> 1 in list(d.keys())
> True

Ah!!  The light finally dawned!  Many thanks for everyone's input.

So if Wierd has a need to compare equal to some other type, it should 
implement a .equals() method.  Gotcha.

Likewise, if two different type's instances can compare equal, then for 
the most part they should be interchangeable.

~Ethan~

[toc] | [prev] | [next] | [standalone]

#5834

Ethan Furman wrote:
> 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?

If you were familiar with what a hash map is, you wouldn't ask. The thing is 
that the hash is used to look up the place in the map where the thing is 
stored. If two equal objects have different hashes, they will be stored in 
different places in the hash map. Looking for object1 will then not turn up 
with object2, even though they are equal. If this is something you don't 
care about, and all you care about is identity, then I'd derive the hash 
from each object's ID.

This ID has another property which is something that is assumed for hashes, 
and your code seems a bit to get that wrong, too, and that is that the hash 
must not change. Again, the reason is that if the hash changes, the position 
in the hash map changes, too. If you then try to look up the changed object, 
it will look for it in the new place, but it won't be found because it is in 
the old place.

For that reason, it is generally useful to use immutable types like 
integers, floats, strings and tuples thereof as keys. Since you can't change 
them, you basically have the guarantee that they hash the same.

Uli

-- 
Domino Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932

[toc] | [prev] | [next] | [standalone]

#5856

On 20/05/2011 07:33, Ulrich Eckhardt wrote:
> Ethan Furman wrote:
>> 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?
>
> If you were familiar with what a hash map is, you wouldn't ask. The thing is
> that the hash is used to look up the place in the map where the thing is
> stored. If two equal objects have different hashes, they will be stored in
> different places in the hash map.
[snip]
Is this strictly true? I thought that the hash value, an integer, is
moduloed (Is that how you spell it? Looks weird!) with the number of
array elements to give an index into the array, so different hashes
could give the same index, and objects with different hashes could be
stored in the same 'bucket'.

[toc] | [prev] | [next] | [standalone]

#5857

On Sat, May 21, 2011 at 1:50 AM, MRAB <python@mrabarnett.plus.com> wrote:
> [snip]
> Is this strictly true? I thought that the hash value, an integer, is
> moduloed (Is that how you spell it? Looks weird!) with the number of
> array elements to give an index into the array, so different hashes
> could give the same index, and objects with different hashes could be
> stored in the same 'bucket'.

There can always be hash collisions between different objects, but the
assumption is that two identical objects will _always_ "collide".

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#5866

On Fri, May 20, 2011 at 10:36 AM, Chris Kaynor <ckaynor@zindagigames.com> wrote:
> I think the question was: can this dummy code ever produce a set containing
> less then itemCount items (for 0 < itemCount < 2**32)?

In CPython, no.  Even when you get a hash collision, the code checks
to see whether the hashes are actually equal before it calls the rich
comparison, the former check being a much faster operation since the
hash values are cached.

I'm not sure whether this can be counted on for all Python
implementations, though.

[toc] | [prev] | [next] | [standalone]

#5868

Ulrich Eckhardt wrote:
> Ethan Furman wrote:
>> 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?
> 
> If you were familiar with what a hash map is, you wouldn't ask. The thing is 
> that the hash is used to look up the place in the map where the thing is 
> stored. If two equal objects have different hashes, they will be stored in 
> different places in the hash map. Looking for object1 will then not turn up 
> with object2, even though they are equal. 

In this case this is the behavior I want.

> If this is something you don't 
> care about, and all you care about is identity, then I'd derive the hash 
> from each object's ID.

This won't work, as objects of the same type that compare equal should 
(and do, in my code) hash equal.

> This ID has another property which is something that is assumed for hashes, 
> and your code seems a bit to get that wrong, too, and that is that the hash 
> must not change. 

The hash does not change on the instances, and is the same for all 
instances of my type that compare equal.

~Ethan~

[toc] | [prev] | [next] | [standalone]

#5906

Ethan Furman wrote:
> Ulrich Eckhardt wrote:
> 
>> If two equal objects have different hashes, they 
>> will be stored in different places in the hash map. Looking for 
>> object1 will then not turn up with object2, even though they are equal. 
> 
> In this case this is the behavior I want.

You can't rely on it, though. The hash value gets reduced
modulo the size of the dict, so even if two objects have
different hashes, in some cases they will land on the same
dict slot anyway.

So an object such as you're postulating would behave
unpredictably when used as a dict key. Sometimes a lookup
using a different but equal object would find it, and
sometimes not, seemingly at random.

-- 
Greg

[toc] | [prev] | [next] | [standalone]

#5911

Gregory Ewing wrote:

> Ethan Furman wrote:
>> Ulrich Eckhardt wrote:
>> 
>>> If two equal objects have different hashes, they
>>> will be stored in different places in the hash map. Looking for
>>> object1 will then not turn up with object2, even though they are equal.
>> 
>> In this case this is the behavior I want.
> 
> You can't rely on it, though. The hash value gets reduced
> modulo the size of the dict, so even if two objects have
> different hashes, in some cases they will land on the same
> dict slot anyway.
> 
> So an object such as you're postulating would behave
> unpredictably when used as a dict key. Sometimes a lookup
> using a different but equal object would find it, and
> sometimes not, seemingly at random.

I think for every potential match the current dict implementation checks 
identity, then hashes -- and equality only if the hash values are equal. The 
relevant function is lookdict() in dictobject.c.

While that means that the problem you describe cannot occur a simple 
approach that avoids relying on an implementation detail (?) would be to use 
(hash(obj), obj) tuples instead of just obj as the key.

[toc] | [prev] | [next] | [standalone]

#5873

Am 20.05.2011 17:50, schrieb MRAB:
> Is this strictly true? I thought that the hash value, an integer, is
> moduloed (Is that how you spell it? Looks weird!) with the number of
> array elements to give an index into the array, so different hashes
> could give the same index, and objects with different hashes could be
> stored in the same 'bucket'.

I don't think 'moduloed' is an existing word but your description is
mostly correct. The hash of the object and length of the hash table are
used to calculate the position in the hash table. However Python's
implementation doesn't use buckets to reduce memory usage and pointer
dereferencing. If a slot in the hash table is already filled with an
object that is not equal to the new object (a collision), the hash is
shifted and the new slot is checked. The implementation detail is well
described in Modules/dictobject.c.

Christian

[toc] | [prev] | [next] | [standalone]

#5878

On 20/05/2011 20:01, Christian Heimes wrote:
> Am 20.05.2011 17:50, schrieb MRAB:
>> Is this strictly true? I thought that the hash value, an integer, is
>> moduloed (Is that how you spell it? Looks weird!) with the number of
>> array elements to give an index into the array, so different hashes
>> could give the same index, and objects with different hashes could be
>> stored in the same 'bucket'.
>
> I don't think 'moduloed' is an existing word but your description is
> mostly correct. The hash of the object and length of the hash table are
> used to calculate the position in the hash table. However Python's
> implementation doesn't use buckets to reduce memory usage and pointer
> dereferencing. If a slot in the hash table is already filled with an
> object that is not equal to the new object (a collision), the hash is
> shifted and the new slot is checked. The implementation detail is well
> described in Modules/dictobject.c.
>
A brief search on the web found a use of the word in 1982.

[toc] | [prev] | [next] | [standalone]

#5892

On Fri, 20 May 2011 21:17:29 +0100, MRAB wrote:

> On 20/05/2011 20:01, Christian Heimes wrote:
>> Am 20.05.2011 17:50, schrieb MRAB:
>>> Is this strictly true? I thought that the hash value, an integer, is
>>> moduloed (Is that how you spell it? Looks weird!) ...
>>
>> I don't think 'moduloed' is an existing word but your description is
>> mostly correct. ...
>>
> A brief search on the web found a use of the word in 1982.

All that means is that two people, three decades apart, used the same non-
word :)

I think you are treating "modulo" as a verb, equivalent to division, 
hence:

a/b => a is divided by b
a%b => a is "moduloed" by b

But modulo is not a verb. It is a preposition, a modifier word. Just as 
you might say "the cat sat on the mat" (cat on mat) or "the Princess 
found a pea underneath her mattress" (pea underneath mattress) so 
mathematicians will say "a is taken modulo b" (a modulo b).

English verbs nouns at the drop of a hat, but I've never heard of it 
verbing propositions:

"The princess underneathed the pea."

No, I don't think so.

English does use "remainder" as a verb, although not in the mathematical 
sense; I think that:

a%b => a is remaindered by b

is at least grammatical, although still ugly and awkward. I'm afraid that 
in English, the best way to say what you are trying to say is moderately 
verbose:

"the hash value, an integer, is taken modulo ..."


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#5896

On 21/05/2011 01:47, Steven D'Aprano wrote:
> On Fri, 20 May 2011 21:17:29 +0100, MRAB wrote:
>
>> On 20/05/2011 20:01, Christian Heimes wrote:
>>> Am 20.05.2011 17:50, schrieb MRAB:
>>>> Is this strictly true? I thought that the hash value, an integer, is
>>>> moduloed (Is that how you spell it? Looks weird!) ...
>>>
>>> I don't think 'moduloed' is an existing word but your description is
>>> mostly correct. ...
>>>
>> A brief search on the web found a use of the word in 1982.
>
> All that means is that two people, three decades apart, used the same non-
> word :)
>
[snip]
There were other uses. That's just the earliest one I found.

[toc] | [prev] | [next] | [standalone]

#5898

On Sat, 21 May 2011 02:02:48 +0100, MRAB wrote:

> On 21/05/2011 01:47, Steven D'Aprano wrote:
>> On Fri, 20 May 2011 21:17:29 +0100, MRAB wrote:
>>
>>> On 20/05/2011 20:01, Christian Heimes wrote:
>>>> Am 20.05.2011 17:50, schrieb MRAB:
>>>>> Is this strictly true? I thought that the hash value, an integer, is
>>>>> moduloed (Is that how you spell it? Looks weird!) ...
>>>>
>>>> I don't think 'moduloed' is an existing word but your description is
>>>> mostly correct. ...
>>>>
>>> A brief search on the web found a use of the word in 1982.
>>
>> All that means is that two people, three decades apart, used the same
>> non- word :)
>>
> [snip]
> There were other uses. That's just the earliest one I found.


Nevertheless, it is still ungrammatical and incorrect usage. I'm not a 
prescriptivist, but not everything people write down is a word, otherwise 
we'd be forcefied to say evert typlo and mystake wsa an actul wrd.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#5939

On 5/19/2011 11:33 PM, Ulrich Eckhardt wrote:

> For that reason, it is generally useful to use immutable types like
> integers, floats, strings and tuples thereof as keys. Since you can't change
> them, you basically have the guarantee that they hash the same.

    Right.  It's something of a lack that Python doesn't
have user-defined immutable objects.

				John Nagle

[toc] | [prev] | [next] | [standalone]

#5940

On 22-5-2011 0:55, John Nagle wrote:
> On 5/19/2011 11:33 PM, Ulrich Eckhardt wrote:
> 
>> For that reason, it is generally useful to use immutable types like
>> integers, floats, strings and tuples thereof as keys. Since you can't change
>> them, you basically have the guarantee that they hash the same.
> 
>    Right.  It's something of a lack that Python doesn't
> have user-defined immutable objects.
> 
>                 John Nagle
> 

collections.namedtuple is rather powerful though... and can be used as key AFAIK.

Irmen

[toc] | [prev] | [next] | [standalone]

#5943

On Sat, 21 May 2011 15:55:56 -0700, John Nagle wrote:

> On 5/19/2011 11:33 PM, Ulrich Eckhardt wrote:
> 
>> For that reason, it is generally useful to use immutable types like
>> integers, floats, strings and tuples thereof as keys. Since you can't
>> change them, you basically have the guarantee that they hash the same.
> 
>     Right.  It's something of a lack that Python doesn't
> have user-defined immutable objects.


Although it's not that hard to write your own immutable (-ish) objects.

http://northernplanets.blogspot.com/2007/01/immutable-instances-in-python.html


Or see the Decimal and Fraction classes in the standard library.


-- 
Steven

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web