A Hash key needs `eql?` and `hash`, not `==`¶

Level: 201 · anyone whose value object works with == but keeps turning up twice in a Hash

One line: A Hash finds a key by calling hash and then eql? — never == — so a class that defines only == gets two keys for two equal points, and so do uniq, Set, tally, group_by and Array#-; defining eql? and hash together fixes all of them, Struct and Data come with both, a key mutated after insertion is lost until rehash, and 1 and 1.0 are == but not eql?, so {1 => :a}[1.0] is nil.

Ruby has two equalities for a reason. == is the one you write for your domain — it may convert, ignore case, or compare only some fields. eql? is the strict one a Hash uses after hash has narrowed the search to a bucket, and the contract is that two objects that are eql? must return the same hash. Object implements both by identity, so an unmodified class behaves as if every instance were unique, which is exactly what row 1 shows. The program below starts with a Pt that has only ==, measures what breaks, adds the pair, and then walks through the cases people trip over: mutable keys, numeric keys, string keys and compare_by_identity.

Verified output of eql_and_hash_for_hash_keys_rb.rb — regenerated by tools/run_examples.py, never hand-typed.

1. == alone: two equal points are two keys
   Pt.new(1, 2) == Pt.new(1, 2)               true
   Pt.new(1, 2).eql?(Pt.new(1, 2))            false
   Pt.new(1, 2).hash == Pt.new(1, 2).hash     false
   { Pt(1,2) => :a, Pt(1,2) => :b }.size      2
   h[Pt.new(1, 2)]                            nil
2. what == alone still does, and what it does not
   [Pt(1,2)].include?(Pt(1,2))  (uses ==)     true
   [Pt(1,2), Pt(1,2)].uniq.size               2
   ([Pt(1,2)] - [Pt(1,2)]).size               1
   Set[Pt(1,2), Pt(1,2)].size                 2
   [Pt(1,2), Pt(1,2)].tally.size              2
   [Pt(1,2), Pt(1,2)].group_by(&:itself).size 2
3. eql? and hash together fix it
   Pt.new(1, 2).eql?(Pt.new(1, 2))            true
   Pt.new(1, 2).hash == Pt.new(1, 2).hash     true
   { Pt(1,2) => :a, Pt(1,2) => :b }.size      1
   h[Pt.new(1, 2)]                            :b
   [Pt(1,2), Pt(1,2)].uniq.size               1
   Set[Pt(1,2), Pt(1,2)].size                 1
   [Pt(1,2), Pt(1,2)].tally                   {Pt(1,2) => 2}
4. Struct and Data get both for free
   S.new(1, 2).eql?(S.new(1, 2))              true
   { S(1,2) => 1, S(1,2) => 2 }.size          1
   { D(1,2) => 1, D(1,2) => 2 }.size          1
   S.new(1, 2) == S.new(1, 2.0)               true
   S.new(1, 2).eql?(S.new(1, 2.0))            false
5. an Array key works by value; a mutated key is lost until rehash
   { [1, 2] => :arr }[[1, 2]]                 :arr
   key = [1]; h = { key => :arr }; key << 2   (the key changed after insertion)
   h[[1, 2]]                                  nil
   h[key]                                     nil
   h.keys                                     [[1, 2]]
   h.rehash; h[[1, 2]]                        :arr
6. 1 and 1.0 are == but not eql?
   1 == 1.0                                   true
   1.eql?(1.0)                                false
   1.hash == 1.0.hash                         false
   { 1 => :int }[1.0]                         nil
   { 1 => :int, 1.0 => :float }               {1 => :int, 1.0 => :float}
   [1, 1.0].uniq.size                         2
   Set[1, 1.0].size                           2
7. a String key is copied and frozen
   s = +"key"; h = { s => 1 }                 (a mutable String as the key)
   h.keys.first.frozen?                       true
   s.frozen?                                  false
   s.equal?(h.keys.first)                     false
   s << "!"; h["key"]                         1
   h["key!"]                                  nil
8. compare_by_identity switches to equal?
   two "a" literals as keys, by identity      2
   the same String object twice               3
9. the rules
   hash returning a String                    TypeError: no implicit conversion of String into Integer
   eql? without hash: keys kept               2
   hash without eql?: keys kept               2
   Object.instance_method(:eql?).owner        Kernel
   Object.instance_method(:hash).owner        Kernel
   Object.instance_method(:==).owner          BasicObject

Reading the output¶

1. Two Pt(1,2) are == but not eql?, and their hash values differ, so a Hash literal with both keeps two entries, and looking up a third Pt(1,2) finds nothing.
2. Array#include? uses == and works. Everything that dedupes through a hash table — uniq, -, Set, tally, group_by — treats the two points as different.
3. alias eql? == plus def hash = [x, y].hash makes the pair agree with ==; the same literal now has one key (the second value, :b, wins), lookup finds :b, and uniq, Set and tally all collapse the pair. Building hash from an Array of the fields is the idiom: Array#hash already combines its elements.
4. Struct and Data define both from their members, so two equal instances are one key. Note the strictness: S.new(1, 2) == S.new(1, 2.0) is true because member == accepts 2 == 2.0, but eql? is false, because 2.eql?(2.0) is.
5. An Array key works by value. But a Hash remembers where it filed a key, and key << 2 changes the key's hash after filing: neither h[[1, 2]] nor h[key] finds it, although h.keys shows it there. rehash re-files every key and lookup works again. (A String key is protected from this by row 7; an Array key is not.)
6. 1 == 1.0 but 1.eql?(1.0) is false and their hashes differ, so {1 => :int}[1.0] is nil, a Hash holds 1 and 1.0 as separate keys, and uniq and Set keep both.
7. A String key is special-cased: the Hash stores a frozen copy, so h.keys.first is frozen, the original is not, they are different objects, and appending to the original leaves h["key"] intact.
8. compare_by_identity makes the Hash use equal? instead of hash/eql?: two "a" literals are two different String objects and so two keys, while the same object assigned twice is one.
9. hash must return an Integer (TypeError otherwise); eql? without hash, or hash without eql?, leaves two keys — both halves are needed. eql? and hash are defined in Kernel; == is defined in BasicObject.

Compared with Python¶

Python's dict runs the same two-step lookup with __hash__ and __eq__, and the differences are all in what happens when one half is missing. Row 1: defining __eq__ without __hash__ sets the class's __hash__ to None, so hash(Pt(1, 2)) and any attempt to use it as a key raise TypeError — Python refuses the unhashable key outright, where Ruby quietly keeps two. Row 2: in on a list uses == and works, and set, Counter and dict.fromkeys fail the same way the dict did. Row 3: a subclass adding __hash__ fixes everything, and dict.fromkeys is the uniq that keeps order. Row 4: a @dataclass with the default eq=True is unhashable for the same reason; frozen=True (or unsafe_hash=True) restores the hash, and a namedtuple is a tuple and hashes by value — with one twist, NT(1, 2) and NT(1, 2.0) are equal and hash alike, where Ruby's Struct says eql? is false. Row 5: a tuple key works by value and a list is refused before it can be mutated; a custom key mutated after insertion is lost just as in Ruby, and since there is no rehash, the fix is to rebuild the dict. Row 6 is the largest difference: hash(1) == hash(1.0) is True, so {1: 'int'}[1.0] finds the entry, {1: 'int', 1.0: 'float'} collapses to {1: 'float'} (the first key object stays, the last value wins), and {1, 1.0, True} has one element — the Python library's comparing int and float ↗ measures this. Row 7: str is immutable, so a dict stores the very object you passed. Row 8: there is no compare_by_identity; keying by id(obj) is the idiom. Row 9: a __hash__ returning a str is a TypeError at lookup time, and vars(Pt)['__hash__'] is None — the marker Python wrote when it saw __eq__.

Verified output of eql_and_hash_for_hash_keys_py.py — regenerated by tools/run_examples.py, never hand-typed.

1. __eq__ alone: the class becomes unhashable
   Pt(1, 2) == Pt(1, 2)                       True
   Pt.__hash__ is None                        True
   hash(Pt(1, 2))                             TypeError
   {Pt(1,2): 'a', Pt(1,2): 'b'}               TypeError
2. what __eq__ alone still does, and what it does not
   Pt(1, 2) in [Pt(1, 2)]  (uses ==)          True
   set([Pt(1,2), Pt(1,2)])                    TypeError
   Counter([Pt(1,2), Pt(1,2)])                TypeError
   dict.fromkeys([Pt(1,2), Pt(1,2)])          TypeError
3. __eq__ and __hash__ together fix it
   Pt2(1, 2) == Pt2(1, 2)                     True
   hash(Pt2(1, 2)) == hash(Pt2(1, 2))         True
   len({Pt2(1,2): 'a', Pt2(1,2): 'b'})        1
   d[Pt2(1, 2)]                               'b'
   len(set(pair))                             1
   len(dict.fromkeys(pair))  (uniq)           1
   Counter(pair)                              {Pt(1,2): 2}
4. dataclasses: frozen ones are hashable, mutable ones are not
   S.__hash__ is None  (eq=True, frozen=False) True
   {S(1, 2): 1}                               TypeError
   len({D(1,2): 1, D(1,2): 2})  (frozen=True) 1
   len({NT(1,2): 1, NT(1,2): 2})  (namedtuple) 1
   NT(1, 2) == NT(1, 2.0)                     True
   hash(NT(1, 2)) == hash(NT(1, 2.0))         True
5. a tuple key works by value; a list cannot be a key; a mutated key is lost
   {(1, 2): 'tuple'}[(1, 2)]                  'tuple'
   {[1, 2]: 'list'}                           TypeError
   key = Pt2(1, 2); d = {key: 'here'}; key.x = 9 (the key changed after insertion)
   d.get(Pt2(9, 2))                           None
   d.get(key)                                 None
   list(d)                                    [Pt(9,2)]
   rebuilt: {k: v for k, v in d.items()}; d.get(Pt2(9, 2)) 'here'
6. 1 and 1.0 are == and hash alike
   1 == 1.0                                   True
   hash(1) == hash(1.0)                       True
   {1: 'int'}[1.0]                            'int'
   {1: 'int', 1.0: 'float'}                   {1: 'float'}
   len(dict.fromkeys([1, 1.0]))               1
   len({1, 1.0})                              1
   len({1, 1.0, True})                        1
7. a str key is immutable, so it is stored as is
   s = 'key'; d = {s: 1}                      (a str is immutable)
   list(d)[0] is s                            True
   d['key']                                   1
8. no compare_by_identity: key by id() instead
   the same str object twice, keyed by id()   1
   a second object                            2
9. the rules
   __hash__ returning a str                   TypeError
   __hash__ without __eq__: keys kept         2
   hasattr(object, '__eq__')                  True
   hasattr(object, '__hash__')                True
   vars(Pt)['__hash__']  (set by defining __eq__) None

Try it¶

Write a Word class that compares case-insensitively: ==, eql? and hash all work on the downcased text. Count %w[Ruby ruby RUBY python Python] with Hash.new(0) and show Word.new("rUbY") finds the count; print which spelling the Hash kept as the key, and put three spellings of one word into a Set.
Take the Pt from the program, insert one as a key, mutate its x, and show h.key?(pt) is false until h.rehash. Then rewrite Pt as Data.define(:x, :y) and show the mutation is no longer possible (NoMethodError on x=), which is why immutable keys are the safe default.

Solution to 1

eql_and_hash_for_hash_keys_kata_rb.rb in full — pasted here by tools/run_examples.py from the file CI runs.

# Exercise 1: a case-insensitive Word as a Hash key. eql? and hash agree on
# the downcased text, so Hash.new(0) counts "Ruby", "ruby" and "RUBY" as one.

class Word
  attr_reader :text

  def initialize(text) = @text = text
  def ==(other) = other.is_a?(Word) && text.casecmp?(other.text)
  alias eql? ==
  def hash = text.downcase.hash
  def inspect = "Word(#{text})"
end

counts = Hash.new(0)
%w[Ruby ruby RUBY python Python].each { |w| counts[Word.new(w)] += 1 }

puts "counts                     #{counts.inspect}"
puts "counts[Word.new(\"rUbY\")]   #{counts[Word.new('rUbY')]}"
puts "the key kept the first spelling seen:"
puts "counts.keys.map(&:text)    #{counts.keys.map(&:text).inspect}"
puts "Word(\"a\").eql?(Word(\"A\"))  #{Word.new('a').eql?(Word.new('A'))}"
puts "same hash?                 #{Word.new('a').hash == Word.new('A').hash}"
puts "as a Set                   #{Set[Word.new('Go'), Word.new('go'), Word.new('GO')].inspect}"

Verified output of eql_and_hash_for_hash_keys_kata_rb.rb — regenerated by tools/run_examples.py, never hand-typed.

counts                     {Word(Ruby) => 3, Word(python) => 2}
counts[Word.new("rUbY")]   3
the key kept the first spelling seen:
counts.keys.map(&:text)    ["Ruby", "python"]
Word("a").eql?(Word("A"))  true
same hash?                 true
as a Set                   Set[Word(Go)]

A Hash key needs eql? and hash, not ==¶

Reading the output¶

Compared with Python¶

Try it¶

See also¶

A Hash key needs `eql?` and `hash`, not `==`¶