Swift 4.2 moves hash construction into the standard library

Making a type a dictionary key should require an understanding of the type's equality. Swift's old hashing interface also required its author to choose a way of mixing component hashes into an integer. That second task calls for knowledge that has little to do with the domain represented by the type.

Swift 4.2 changes that division of work. Its September 17 release announcement includes SE-0206, which introduces Hasher and a new hash(into:) requirement. A type supplies the components that matter to equality. The standard library supplies the hash-function implementation.

The Hashable proposal by Karoy Lorentey and Vincent Esche explains why this is a collection-design change as well as a shorter conformance spelling. Set and Dictionary depend on the distribution of hash values. Moving mixing into a common implementation gives the library more control over that distribution and over the cost of composing hashes.

I like Swift's collection model because ordinary value operations have clear rules. A standard hashing mechanism fits that preference. A domain type should identify which of its values determine equality without needing a private assortment of multipliers and bitwise operators.

Equality selects the components

The new method receives a mutable Hasher. Its implementation combines the essential components of the value into that existing state. It does not create its own hasher or return an integer hash.

For a point with two coordinates, equality and hashing can describe the same two stored values. This example follows the mechanism in SE-0206.

struct Point: Hashable {
    let x: Int
    let y: Int

    static func == (lhs: Point, rhs: Point) -> Bool {
        return lhs.x == rhs.x && lhs.y == rhs.y
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(x)
        hasher.combine(y)
    }
}

The important requirement is agreement between the methods. Values considered equal must feed the same values into the hasher in the same order. Hashing does not get to use an extra field that equality ignores, because two equal instances could then receive different hashes.

The type author still has substantive work to do when equality is customized. A standard mixing algorithm cannot decide which fields are essential to the domain's equality relation. That decision remains with the type. The new API removes the separate obligation to invent a suitable hash function.

When all stored properties meet the synthesis requirements, the compiler can generate the conformance. Swift 4.1 introduced synthesis for suitable types, and the new proposal extends its relationship with the hashing requirements. Manual code remains useful when equality deliberately differs from a comparison of all stored properties.

A synthesized implementation and a hand-written implementation should therefore be selected according to the intended equality. The point example writes both methods to show the relationship. For a struct whose equality is exactly its hashable stored properties, synthesis can remove those definitions.

A returned integer hides how it was produced

The old hashValue requirement asks a type to return an integer. That makes a small conformance appear easy, while leaving the quality of the returned value unspecified by its construction. Combining two integers with a few operators can create clustering or predictable collisions.

SE-0206 examines an earlier GridPoint example that used an exclusive-or and a multiplication constant. The authors explain that it can behave acceptably for small trusted coordinates while allowing many unequal points with the same hash. The implementation also requires readers to understand operator precedence and overflow behavior merely to assess a dictionary key.

That matters because hash-table performance relies on values spreading usefully across the table. The proposal describes average constant-time lookup, insertion and removal with a suitable hash function. Poor distribution can instead make operations proportional to the number of stored elements. Deliberately chosen collisions can therefore turn a collection implementation detail into an application's responsiveness problem.

The new method does not make collisions impossible. Any integer result can represent more than one input. It lets the standard library select and maintain a common algorithm suited to the collections that consume it. Individual domain types no longer need to independently reproduce that work.

Simply exposing Hasher while retaining only hashValue would leave important control inside each type's implementation. A type could initialize and finalize its own hasher and return the result, but the caller would receive only that finished integer. The new protocol lets components contribute to a state owned by the larger operation.

Nested values can share a hashing operation

The proposal's rectangle example explains the performance consequence. A rectangle contains two points, and each point contains coordinates. With separate hashValue calculations, obtaining each point's hash initializes and finalizes an independent hashing operation before the rectangle combines the results.

Using hash(into:) lets the rectangle combine each point into the same hasher. Each point then contributes its own coordinates to that existing state. Finalization can occur once after the complete value has contributed its components.

That removes repeated finalization from the composition. SE-0206 describes finalization as relatively expensive for its implementation and contrasts the two operation counts. The useful conclusion does not depend on treating its illustrative cost model as an application benchmark. Passing shared hashing state avoids doing the completion work at every nested component.

This also preserves information for the common mixing implementation. A nested value supplies its essential components through the same protocol used by a simple value. The collection does not need to know the point's fields, and the rectangle does not need to implement the point's mixing algorithm.

My preference is for that responsibility to follow the value's structure. A point knows its coordinates, while a rectangle knows which points define it. Passing a hasher through those relationships makes the composition explicit without requiring each layer to manufacture an intermediate hash integer.

Hash values are execution-local results

Hasher uses random seeding, and the proposal states that hash values can change across executions even for the same input. It also reserves the library's ability to change the hash algorithm. An application must not save these hash values as persistent identifiers.

This is a direct consequence of using hashes for collection operations rather than as durable names. Within the documented conditions of an execution, feeding the same byte sequence produces the same result. Across executions, a new seed may produce another integer. A stored hash cannot establish that a later value is the same domain object.

Randomization also makes hash values harder to predict for deliberate collision construction. The proposal identifies this as a reason for the policy. It does not turn an ordinary Hashable conformance into a general cryptographic integrity API. Its purpose is the behavior and reliability of hashed collections.

The library retains control over Hasher's implementation, including its internal layout. SE-0206 treats that as preparation for replacing the algorithm without asking every Hashable type to change its source. That is particularly relevant if a weakness appears in the selected algorithm.

The release announcement describes Swift 4.2 as moving toward a stabilized ABI. It does not declare ABI stability complete. Hasher's design can support future implementation flexibility while the release as a whole still has binary-compatibility work ahead of it.

The proposal also considers a generic hasher protocol that would let callers substitute their own algorithm. It rejects that additional generality because of its API and performance costs. A concrete Hasher gives the compiler more specific information about the operation, including its side effects. The chosen interface concentrates implementation work on the standard collection use case.

Existing conformances have a migration path

Adding a protocol requirement could otherwise break every existing manual conformance. The proposal uses synthesis to supply the missing requirement from an existing hashValue implementation. In the other direction, a type that implements hash(into:) can receive a generated hashValue.

This supports source migration, but retaining an old mixing expression does not give it all the quality of combining the original components separately. SE-0206 makes that limitation explicit in its migration discussion. A mechanical wrapper around an old result preserves more of the old design than a deliberate rewrite does.

Swift 4.2 also adds collection operations including allSatisfy, in-place conditional removal and last-element searches. Those are useful individual APIs, while the hashing change alters a shared protocol beneath Set and Dictionary. The release ships with Xcode 10 and provides official Ubuntu binaries, including Ubuntu 18.04.

For a custom dictionary key, the new implementation task is concrete. Establish which components define equality, combine those components in a consistent order, and leave initialization and finalization to the surrounding hashing operation. The standard library can then apply its common hashing policy across that type and the values containing it.