Hashable in Swift

A type is hashable when it conforms to the Hashable protocol. Hashability has a straightforward purpose: the ability of a type to generate an integer based on its content. But why is that useful? You will explore hashing in this section.

Put some Point instances to work in a set and a dictionary to see the error that you get:

Listing 25.12  Verifying Hashable conformance

...
let pointRange = c..<d                                     {{x 2, y 6, nil},...
pointRange.contains(a)                                     true
pointRange.contains(Point(x: -1, y: -1))                   false

let points: Set = [a, b, c]
points.intersection([b, c, d])

let pointNames: [Point:String] = [
    Point(x: 0, y: 0): "origin",
    a: "a",
]

Here you define a Set of Point instances and call its intersection(_:) method. You also create a dictionary whose keys are Points and use it to give names to some points. The compiler emits two errors: Generic struct 'Set' requires that 'Point' conform to 'Hashable' and Type 'Point' does not conform to protocol 'Hashable'.

That is straightforward enough. You must make Point conform to Hashable for either of these uses of the type to be legal.

Similar to Equatable, the compiler will happily synthesize implementations of Hashable’s requirements for structs with all hashable stored properties and enums with no associated values (or all hashable associated values). Update Point to conform to Hashable:

Listing 25.13  Conforming to Hashable

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

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

Because Point is Hashable now, the compiler can understand all these uses of Point.

CUSTOM HASHING

Unfortunately, the free implementation that the compiler has synthesized for Point is problematic. To understand why, you need to learn a little bit about hashes.

In Swift, the hash of an instance is an integer that is generated from the instance’s data. Comparing the hashes of two instances of a type can be a very fast way to check whether the instances are different – often much faster than comparing the instances using the == operator.

Consider how long it could take to compare two instances of String for equality: The program must advance along the complete length of at least one of the strings, comparing the Character at each index to the Character at the same index of the other string. If the program gets to the very end of the strings without encountering a difference, the strings are the same. By contrast, comparing two integers is blazing fast, and modern CPUs are often designed to make it even faster.

If you want to know whether two strings are equal, you can first check their hashes, which takes nearly no time at all. If their hashes are different, then you know the strings are different.

But, because strings can be larger and more complex than integers, it is possible for two different strings to have the same hash. So, if two strings’ hashes are the same, you have not learned anything, and you must proceed with a complete equality check to be sure.

(As an aside: Because an equality check is a necessary backup plan when comparing the hashes of instances, Hashable inherits from Equatable.)

An ideal hashing algorithm is one that is fast to compute and unlikely to collide with another instance’s hash – but does not need to guarantee that two hashes will never be the same.

To make lookups and comparisons as fast as possible, dictionaries use hashes as an initial check to ensure that dictionary keys are unique, and sets use hashes as an initial check to ensure the uniqueness of their contents. Adding lots of instances with the same hash value would force these types to fall back on equality checks to ensure uniqueness, which can be much slower.

Fortunately, Swift has a safe, fast hashing algorithm built in. All you have to do is tell Swift which properties of an instance should participate in the computation of its hash. Swift calls these properties that contribute to an equality comparison the instance’s essential components.

Your current implementation of the == operator uses only the x and y properties of a Point. However, the compiler-synthesized hash of a Point uses all the instance’s stored properties. And that is the source of the problem: If one property is not relevant to an instance’s uniqueness, then it should not be an essential component for hashing.

To control which properties of an instance will contribute to its hash, you must provide your own implementation of the Hashable requirement. That requirement is an implementation of a method called hash(into:). Implement it in your Point extension:

Listing 25.14  Producing your own hash

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

    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)
    }
}

When Swift needs to compute your object’s hash, it will call hash(into:) and pass in a reference to an instance of the Hasher struct as its argument. Hasher implements Swift’s hashing algorithm, and your job is to tell it which properties to include by passing them to its combine(_:) method.

That is all! Point is now stylishly Hashable.

Written by

XR Developer responsible for end-to-end development of XR solutions spanning multiple domains, by using various XR and WebXR libraries.

Leave a Reply