Hi, Can anyone explain me how this is correct? Collection>>#hash "Answer an integer hash value for the receiver such that, -- the hash value of an unchanged object is constant over time, and -- two equal objects have equal hash values" | hash | hash := self species hash. self size <= 10 ifTrue: [self do: [:elem | hash := hash bitXor: elem hash]]. ^hash bitXor: self size hash I mean⦠a hash that changes when I add elements to the collection⦠how can this work? Esteban
You simply don't modify _objects_ which are used as keys in hashed collections. Or if you do so, you'll have to deal with the consequences yourself. Levente On Fri, 9 Oct 2015, Esteban Lorenzano wrote:
Hi,
Can anyone explain me how this is correct?
Collection>>#hash "Answer an integer hash value for the receiver such that, -- the hash value of an unchanged object is constant over time, and -- two equal objects have equal hash values"
| hash |
hash := self species hash. self size <= 10 ifTrue: [self do: [:elem | hash := hash bitXor: elem hash]]. ^hash bitXor: self size hash
I mean⦠a hash that changes when I add elements to the collection⦠how can this work?
Esteban
but thatâs an error, I think. a collection has to have always same hash⦠no matter its size (because is not an array) and no matter his elements.
On 09 Oct 2015, at 15:21, Levente Uzonyi <leves@elte.hu> wrote:
You simply don't modify _objects_ which are used as keys in hashed collections. Or if you do so, you'll have to deal with the consequences yourself.
Levente
On Fri, 9 Oct 2015, Esteban Lorenzano wrote:
Hi,
Can anyone explain me how this is correct?
Collection>>#hash "Answer an integer hash value for the receiver such that, -- the hash value of an unchanged object is constant over time, and -- two equal objects have equal hash values"
| hash |
hash := self species hash. self size <= 10 ifTrue: [self do: [:elem | hash := hash bitXor: elem hash]]. ^hash bitXor: self size hash
I mean⦠a hash that changes when I add elements to the collection⦠how can this work?
Esteban
The identityHash should stay the same for any number of changes to the array.. | c1 c2 | c1 := { #a . #b } asOrderedCollection. c2 := { #a . #b } asOrderedCollection. { c1 hash. c1 identityHash. c2 hash. c2 identityHash . (c2 add: #c; yourself) identityHash. } "inspect" Best regards, Henrik -----Original Message----- From: Pharo-dev [mailto:pharo-dev-bounces@lists.pharo.org] On Behalf Of Esteban Lorenzano Sent: Friday, October 9, 2015 4:08 PM To: Pharo Development List <pharo-dev@lists.pharo.org> Subject: Re: [Pharo-dev] hash and Collections but thatâs an error, I think. a collection has to have always same hash⦠no matter its size (because is not an array) and no matter his elements.
On 09 Oct 2015, at 15:21, Levente Uzonyi <leves@elte.hu> wrote:
You simply don't modify _objects_ which are used as keys in hashed collections. Or if you do so, you'll have to deal with the consequences yourself.
Levente
On Fri, 9 Oct 2015, Esteban Lorenzano wrote:
Hi,
Can anyone explain me how this is correct?
Collection>>#hash "Answer an integer hash value for the receiver such that, -- the hash value of an unchanged object is constant over time, and -- two equal objects have equal hash values"
| hash |
hash := self species hash. self size <= 10 ifTrue: [self do: [:elem | hash := hash bitXor: elem hash]]. ^hash bitXor: self size hash
I mean⦠a hash that changes when I add elements to the collection⦠how can this work?
Esteban
If the collection implements = using the objects it holds then you need to consider at least some of them in the hash calculation. I can't conceive a hash calculation for this case independent of the contents (well, just hardcode a number but this will lead to always collide if used as a key in a hashed collection). I'm with Levente here, I think the hash implementation is reasonable. And I wouldn't use a mutable object as key in a hashed collection. On Fri, Oct 9, 2015 at 11:07 AM, Esteban Lorenzano <estebanlm@gmail.com> wrote:
but thatâs an error, I think. a collection has to have always same hash⦠no matter its size (because is not an array) and no matter his elements.
On 09 Oct 2015, at 15:21, Levente Uzonyi <leves@elte.hu> wrote:
You simply don't modify _objects_ which are used as keys in hashed collections. Or if you do so, you'll have to deal with the consequences yourself.
Levente
On Fri, 9 Oct 2015, Esteban Lorenzano wrote:
Hi,
Can anyone explain me how this is correct?
Collection>>#hash "Answer an integer hash value for the receiver such that, -- the hash value of an unchanged object is constant over time, and -- two equal objects have equal hash values"
| hash |
hash := self species hash. self size <= 10 ifTrue: [self do: [:elem | hash := hash bitXor: elem hash]]. ^hash bitXor: self size hash
I mean⦠a hash that changes when I add elements to the collection⦠how can this work?
Esteban
On 09 Oct 2015, at 16:21, Gabriel Cotelli <g.cotelli@gmail.com> wrote:
If the collection implements = using the objects it holds then you need to consider at least some of them in the hash calculation. I can't conceive a hash calculation for this case independent of the contents (well, just hardcode a number but this will lead to always collide if used as a key in a hashed collection).
it is not :)
I'm with Levente here, I think the hash implementation is reasonable. And I wouldn't use a mutable object as key in a hashed collection.
no idea⦠Iâm not using it, just arrive to that method random and I cannot understand it. I still believe is wrong. Esteban
On Fri, Oct 9, 2015 at 11:07 AM, Esteban Lorenzano <estebanlm@gmail.com <mailto:estebanlm@gmail.com>> wrote: but thatâs an error, I think. a collection has to have always same hash⦠no matter its size (because is not an array) and no matter his elements.
On 09 Oct 2015, at 15:21, Levente Uzonyi <leves@elte.hu <mailto:leves@elte.hu>> wrote:
You simply don't modify _objects_ which are used as keys in hashed collections. Or if you do so, you'll have to deal with the consequences yourself.
Levente
On Fri, 9 Oct 2015, Esteban Lorenzano wrote:
Hi,
Can anyone explain me how this is correct?
Collection>>#hash "Answer an integer hash value for the receiver such that, -- the hash value of an unchanged object is constant over time, and -- two equal objects have equal hash values"
| hash |
hash := self species hash. self size <= 10 ifTrue: [self do: [:elem | hash := hash bitXor: elem hash]]. ^hash bitXor: self size hash
I mean⦠a hash that changes when I add elements to the collection⦠how can this work?
Esteban
On 09 Oct 2015, at 4:33 , Esteban Lorenzano <estebanlm@gmail.com> wrote:
On 09 Oct 2015, at 16:21, Gabriel Cotelli <g.cotelli@gmail.com <mailto:g.cotelli@gmail.com>> wrote:
If the collection implements = using the objects it holds then you need to consider at least some of them in the hash calculation. I can't conceive a hash calculation for this case independent of the contents (well, just hardcode a number but this will lead to always collide if used as a key in a hashed collection).
it is not :)
I'm with Levente here, I think the hash implementation is reasonable. And I wouldn't use a mutable object as key in a hashed collection.
no idea⦠Iâm not using it, just arrive to that method random and I cannot understand it. I still believe is wrong. It's not.
Either Dictionary >> #= or IdentityDictionary >> #species in Pharo *is* broken though. dic1 := Dictionary newFrom:{1 -> 4}. dic2 := IdentityDictionary newFrom: dic1 associations . dic1 = dic2 true dic1 hash = dic2 hash false Cheers, Henry
On Oct 9, 2015, at 7:51 AM, Henrik Johansen <henrik.s.johansen@veloxit.no> wrote:
On 09 Oct 2015, at 4:33 , Esteban Lorenzano <estebanlm@gmail.com> wrote:
On 09 Oct 2015, at 16:21, Gabriel Cotelli <g.cotelli@gmail.com> wrote:
If the collection implements = using the objects it holds then you need to consider at least some of them in the hash calculation. I can't conceive a hash calculation for this case independent of the contents (well, just hardcode a number but this will lead to always collide if used as a key in a hashed collection).
it is not :)
I'm with Levente here, I think the hash implementation is reasonable. And I wouldn't use a mutable object as key in a hashed collection.
no idea⦠Iâm not using it, just arrive to that method random and I cannot understand it. I still believe is wrong. It's not.
Either Dictionary >> #= or IdentityDictionary >> #species in Pharo *is* broken though.
dic1 := Dictionary newFrom:{1 -> 4}. dic2 := IdentityDictionary newFrom: dic1 associations .
dic1 = dic2 true dic1 hash = dic2 hash false
Cheers, Henry
+1. Henry is right. Esteban, given #(1 2 3) = #(1 2 3) and #(1 2 3) ~= #(1 2 3 4) we require that #(1 2 3) hash = #(1 2 3) hash and would like that #(1 2 3) hash ~= #(1 2 3 4) hash Now it's too much for me to type in my phone but exactly the same should be true of dictionaries. And given that a Dictionary with eg key/value pairs 1->a 2->b 3->c can have 4->d added to it it implies that if the hash function is good it will change when 4->d is added. And as others have said if you want a hash that doesn't change there is the identityHash and identity collections for that very purpose.
Resending because the last was HTML'd: Never use #newFrom: with associations from another dictonary if you reuse the first after. Â The bug is actually deeper than you know: dic1 := Dictionary newFrom:{'test' -> 4}. dic2 := IdentityDictionary newFrom: {'test' copy -> 4}. dic1 = dic2. dic2 = dic1. Â Depending on the order, they are equal or inequal. Â The bug is caused by Dictionary>>= using a polymorphic type test #isDictionary. Squeak is unaffected: its #= uses a hardcoded class == test. The least disruptive fix I can think of is adding another type test #isIdentityDictionary in Dictionary that returns false but returns true for every identity dictionary class (like SmalllIdentityDictionary). Then only compare the associations if "self isIdentityDictionary = aDictionary isIdentityDictionary". Â I will open an issue.
The issue: https://pharo.fogbugz.com/f/cases/16760/Dictionary-breaks-when-comparing-ide...
Sent: Sunday, October 11, 2015 at 7:23 AM From: monty <monty2@programmer.net> To: pharo-dev@lists.pharo.org Subject: Re: [Pharo-dev] hash and Collections
Resending because the last was HTML'd:
Never use #newFrom: with associations from another dictonary if you reuse the first after. Â The bug is actually deeper than you know: dic1 := Dictionary newFrom:{'test' -> 4}. dic2 := IdentityDictionary newFrom: {'test' copy -> 4}. dic1 = dic2. dic2 = dic1. Â Depending on the order, they are equal or inequal. Â The bug is caused by Dictionary>>= using a polymorphic type test #isDictionary. Squeak is unaffected: its #= uses a hardcoded class == test. The least disruptive fix I can think of is adding another type test #isIdentityDictionary in Dictionary that returns false but returns true for every identity dictionary class (like SmalllIdentityDictionary). Then only compare the associations if "self isIdentityDictionary = aDictionary isIdentityDictionary". Â I will open an issue.
Hi Esteban, I understand your surprise, but it has to be like that. Two objects that are equals have to have the same hash value. This is part of the contract. And to comply with this rule with collections, the hash value has to reflect the content of the collection. Java has the same behavior. Cheers, Alexandre -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
On Oct 9, 2015, at 11:07 AM, Esteban Lorenzano <estebanlm@gmail.com> wrote:
but thatâs an error, I think. a collection has to have always same hash⦠no matter its size (because is not an array) and no matter his elements.
On 09 Oct 2015, at 15:21, Levente Uzonyi <leves@elte.hu> wrote:
You simply don't modify _objects_ which are used as keys in hashed collections. Or if you do so, you'll have to deal with the consequences yourself.
Levente
On Fri, 9 Oct 2015, Esteban Lorenzano wrote:
Hi,
Can anyone explain me how this is correct?
Collection>>#hash "Answer an integer hash value for the receiver such that, -- the hash value of an unchanged object is constant over time, and -- two equal objects have equal hash values"
| hash |
hash := self species hash. self size <= 10 ifTrue: [self do: [:elem | hash := hash bitXor: elem hash]]. ^hash bitXor: self size hash
I mean⦠a hash that changes when I add elements to the collection⦠how can this work?
Esteban
participants (8)
-
Alexandre Bergel -
Eliot Miranda -
Esteban Lorenzano -
Gabriel Cotelli -
Henrik Johansen -
Henrik Nergaard -
Levente Uzonyi -
monty