Why does Hashable require Equatable?

Evolution Discussion
6

Hashable extends Equatable because hashing is a meaningless operation without equality: the requirements on hash values are defined in terms of equal and non-equal elements.

From a practical viewpoint, without Equatable, you may be able to add elements to a Dictionary or a Set, but you wouldn't be able to look them up later. This eliminates the primary purpose of these data structures.

When you calculate a hash, you're distilling the original value to a fixed-width sequence of bits that can be used as a direct evidence of inequality. Two equal elements must always produce the same hash value, so if we have two items with different hash values, then we are guaranteed to have two unequal items. The sole purpose of hash values is to serve as such evidence. If equality has no meaning, then there is no such thing as a hash.

The original code above violates the basic Hashable requirement. For example:

let a = Foo(n: 1, m: 2)
let b = Foo(n: -2, m: -1)
print(a == b) // ⟹ true
print(a.hashValue == b.hashValue) // ⟹ (usually!) false

This is a serious error that can produce all sorts of weird behavior -- including phantom and/or duplicate Dictionary keys. Unfortunately it is extremely difficult for Set and Dictionary to reliably catch this error. Sometimes they get lucky and notice an unexpected duplicate key while they're resizing themselves, in which case they can (and do!) trap with an error message that indicates the issue. Unfortunately, there is no guarantee this will occur during testing. (The current development snapshots catch this a little more often, especially in debug builds, but it simply isn't feasible to include full Hashable validation in the standard collection types.) The easiest way to not run into issues like this is to let the compiler synthesize Equatable and Hashable for you.

Of course, compiler synthesis is only appropriate when the type is the straightforward case. Judging by your definition for Foo.==, this is probably not the case here. Assuming you meant to express that Foo.m and Foo.n should be considered interchangeable, then this thread from last week will probably come useful -- it includes a direct example of how to do that sort of thing correctly.

Additional notes:

  • It is a good idea to treat explicit manually conformances of Equatable and Hashable as a code smell. Unfortunately, they are sometimes unavoidable; if you must manually implement them, make sure the implementations are carefully peer-reviewed and fully tested.
  • Be careful about the use of * in Foo.==. The definition as written considers Foo(n: 6, m: -7) to be equal to Foo(n: -1, m: 42), which may not be what you intended. The multiplication may also overflow.
  • On the other hand, if the definition of Foo.== above is indeed exactly what you want/need, then here is a matching implementation of Hashable:
    extension Foo: Hashable {
  func hash(into hasher: inout Hasher) {
    hasher.combine(n * m)
  }
}
    The trick is to always feed hasher the exact same values that you compare in ==. (Don't try to optimize hashing by only including some of them -- it'll most likely only slow things down. In addition, it will definitely make the code harder to understand/review/maintain, so it'll be more likely for bugs to creep in.)
  • Don't implement hashValue in new code. Implement hash(into:) instead; it's a lot easier and it frequently performs better.
24 Likes