Ruby hash equlity


#1

Based on the description of Hash#==

" Equality—Two hashes are equal if they each contain the same
number of keys and if each key-value pair is equal to (according to
+Object#==+) the corresponding elements in the other hash."

I am having problems understanding the following:

$ irb
irb(main):001:0> VERSION
=> “1.8.5”
irb(main):002:0> a={:c => nil, :d => nil}
=> {:c=>nil, :d=>nil}
irb(main):003:0> b={:d => nil, :c => nil}
=> {:c=>nil, :d=>nil}
irb(main):004:0> # As expected this is true
irb(main):005:0* a == b
=> true
irb(main):006:0> c={:a => nil, a => nil, :b => nil}
=> {:b=>nil, :a=>nil, {:c=>nil, :d=>nil}=>nil}
irb(main):007:0> d={:b => nil, b => nil, :a => nil}
=> {:b=>nil, {:c=>nil, :d=>nil}=>nil, :a=>nil}
irb(main):008:0> # Unexpectedly false
irb(main):009:0* c == d
=> false

Shouldn’t they be equivalent ?

Thanks,

Mike


#2

On Feb 8, 2:29 pm, removed_email_address@domain.invalid wrote:

irb(main):005:0* a == b
=> true
irb(main):006:0> c={:a => nil, a => nil, :b => nil}
=> {:b=>nil, :a=>nil, {:c=>nil, :d=>nil}=>nil}
irb(main):007:0> d={:b => nil, b => nil, :a => nil}
=> {:b=>nil, {:c=>nil, :d=>nil}=>nil, :a=>nil}
irb(main):008:0> # Unexpectedly false
irb(main):009:0* c == d
=> false

Shouldn’t they be equivalent ?

Let’s make your example a little bit simpler to get at the core of the
matter:
a = {}
b = {}
p a==b
#=> true

c = {1=>a}
d = {1=>b}
p c==d
#=> true

e = {a=>1}
f = {b=>1}
p e==f
#=> false

Apparently it’s enough for two values to be #== to one another, but
it’s not good enough for two keys to be #== to one another.


#3

On Feb 8, 3:00 pm, “Phrogz” removed_email_address@domain.invalid wrote:

=> {:c=>nil, :d=>nil}
irb(main):009:0* c == d

Apparently it’s enough for two values to be #== to one another, but
it’s not good enough for two keys to be #== to one another.

To take it one step further, think about it this way:
p c[1] == d[1]
#=> true

p e[a] == f[a]
#=> false

If you wanted the functionality you were expecting, then for these two
hashes:
x = { m=>1, n=>2, o=>3 }
y = { g=>1, h=>2, k=>3 }
testing for equality would have to do something like:

class Hash

Ouch! O(n^2) performance

Very bad for hashes with many keys

def sort_of_equal( other )
equal = true
self.each{ |k,v|
found_key=false
other.each{ |k2,v2|
found_key ||= ( ( k==k2 ) && ( v==v2 ) )
}
equal &&= found_key
}
equal
end
end

p e.sort_of_equal( f )
#=> true


#4

Finally, here’s a slightly better version. It’s still O(n^2) in the
worst case, but should perform much better under common circumstances
(in case someone actually needed this functionality):

class Hash

Ouch! O(n^2) performance

Bad for hashes with many keys

def sort_of_equal( other )
equal = true
self.each{ |k,v|
unless found_key = (other[k]==v)
other.each{ |k2,v2|
break if found_key = ( ( k==k2 ) && ( v==v2 ) )
}
end
equal &&= found_key
}
equal
end
end

Note that this will still not work if you have nested hashes that you
want to treat like this. You’d need to override Hash#== fully, or put
in tests based on key and value type.


#5

Thanks Phrogz, but yes my problem would require nested hashes and
would have
to be reasonably efficient. Let me explain… I started with the
problem of comparing
sets that may have sets as members:

irb(main):017:0> require ‘set’
=> false
irb(main):018:0> Set[:a, :b] == Set[:a, :b]
=> true
irb(main):019:0> Set[:a, :b, Set[:c, :d]] == Set[:a, :b, Set[:c, :d]]
=> false

Suprisingly it didn’t work. So I looked at how sets were implemented -
basically
hashes where the set members are the keys and the values are true.

I still believe that hash equality should be as the ‘ri’ manual
describes. I’m going
to examine the ruby ‘C’ code to see exactly why…

Mike