Ruby Language Overriding hash function


Example

Ruby hashes use the methods hash and eql? to perform the hash operation and assign objects stored in the hash to internal hash bins. The default implementation of hash in Ruby is the murmur hash function over all member fields of the hashed object. To override this behavior it is possible to override hash and eql? methods.

As with other hash implementations, two objects a and b, will be hashed to the same bucket if a.hash == b.hash and will be deemed identical if a.eql?(b). Thus, when reimplementing hash and eql? one should take care to ensure that if a and b are equal under eql? they must return the same hash value. Otherwise this might result in duplicate entries in a hash. Conversely, a poor choice in hash implementation might lead many objects to share the same hash bucket, effectively destroying the O(1) look-up time and causing O(n) for calling eql? on all objects.

In the example below only the instance of class A is stored as a key, as it was added first:

class A
  def initialize(hash_value)
    @hash_value = hash_value
  end
  def hash
    @hash_value # Return the value given externally
  end
  def eql?(b)
    self.hash == b.hash
  end
end

class B < A
end

a = A.new(1)
b = B.new(1)

h = {}
h[a] = 1
h[b] = 2

raise "error" unless h.size == 1
raise "error" unless h.include? b
raise "error" unless h.include? a