How is synthesized Hashable implemented?

Development Compiler
2

The hash function in Swift 4.2 is SipHash-1-3; however, this is an implementation detail that is subject to change in any release. (Note that hashing changed considerably between Swift 4.1 and 4.2. I'm going to concentrate on Swift 4.2 here. Swift 4.1 uses a less robust algorithm to generate hash values, but compiler synthesis works in a roughly similar way.)

The new Hasher API (introduced by SE-0206, implemented in 4.2) exposes the standard hash function as public API. It has been carefully designed to prevent exposing the underlying algorithm; for example, the seed value is not user-selectable, so e.g. you can’t use Hasher to produce repeatable-looking hashes that may break later in a new version of the standard library.

SE-0206 also adds a new requirement to Hashable that is better suited to universal hash functions such as SipHash. Automatically generated Hashable conformances now implement this new hash(into:) requirement. hashValue is still generated, of course, but the implementation simply forwards the actual job of hashing to hash(into:). (See below.)

Automatic synthesis of Hashable conformance is relatively easy for structs: the compiler generates a hash(into:) implementation that simply feeds all stored properties into the supplied hasher:

struct Dog {
  let name: String
  let breed: String
  let age: Int
}

extension Dog: Hashable {
  func hash(into hasher: inout Hasher) { // Generated automatically
    hasher.combine(name)
    hasher.combine(breed)
    hasher.combine(age)
  }
}

Note that the order in which properties are fed to the hasher is significant. Synthesized implementations currently follow declaration order, but this may change before the ABI stabilizes. (In case we need to do something special for resilient structs, for example.)

Hashable synthesis is a bit more complicated for enums, because hash(into:) needs to ensure that two different cases never feed the same data to the hasher. Fortunately, there is an easy trick for doing this: we simply feed the hasher with a distinguishing value that is unique to each case. For cases with associated values, we feed those to the hasher, too.

enum List<T> {
  case empty
  indirect case node(value: T, rest: List<T>)
}

extension List: Hashable where T: Hashable {
  func hash(into hasher: inout Hasher) { // Generated automatically
    switch self {
      case .empty:
        hasher.combine(0) // discriminator
      case let .node(value: value, rest: rest):
        hasher.combine(1) // discriminator
        hasher.combine(value)
        hasher.combine(rest)
    }
  }
}

The discriminator value is currently assigned sequentially to each case in the enum, in declaration order. However, it is not wise to write code that relies on this. (We may need to change it to some other scheme to e.g. better support extensible enums.)

As for the old hashValue requirement, the compiler always synthesizes it the same way, in terms of the hash(into:) definition:

extension Dog {
  var hashValue: Int {
    var hasher = Hasher()
    self.hash(into: &hasher)
    return hasher.finalize()
  }
}

(Actually, this is implemented by a function in the stdlib; the generated hashValue consists of a call to it. But it boils down to the same code.)

The code that implements automatic Hashable (and Equatable) synthesis lives in lib/Sema/DerivedConformanceEquatableHashable.cpp. Look there for the nitty gritty details, including how hash(into:) is generated for types that only implement hashValue.

15 Likes