# Hashable / Hasher By [Mattt](https://nshipster.com/authors/mattt). Published 2018-08-13. Canonical URL: When you make a Genius Bar reservation at an Apple Store, you’re instructed to show up at a particular time of day and check in with the concierge. After directing you to pull up a stool, the concierge adds you to the queue and makes a note about how to identify you. According to anonymous reports from former retail employees, there are strict guidelines about how customers can be described. Nothing about their physical appearance is used: age, gender, ethnicity, height — not even hair color. Instead, all customers are described by their clothing, as in “Person with black turtleneck, jeans, and glasses”. This practice of describing customers has a lot in common with a hashing function in programming. Like any good hashing function, it’s consistent and easy to compute, and can be used to quickly find what (or who) you’re looking for. Much better than a queue, I think you’ll agree! Our topic this week is `Hashable` and its new related type, `Hasher`. Together, they comprise the functionality underlying two of Swift’s most beloved collection types: `Dictionary` and `Set`. --- Let’s say you have a [**list**](https://en.wikipedia.org/wiki/List_\(abstract_data_type\)) of objects that can be compared for equality with one another. To find a particular object in that list, you iterate all the elements until you find a match. As you add more elements to the array, the average amount of time necessary to find any one of them increases linearly (`O(n)`). If you instead store those objects in a [**set**](https://en.wikipedia.org/wiki/Set_\(abstract_data_type\)), you can theoretically find any one of them in constant time (`O(1)`) — that is, a lookup on a set with 10 elements takes the same amount of time as a lookup on a set with 10,000*. How does this work? Instead of storing objects sequentially, a set computes a hash as an index based on the contents of the object. When you perform a lookup of an object in a set, you use the same function to compute a new hash and look for the object there. * Two objects produce a hash collision when they have the same hash value but aren’t equal. When a collision occurs on insertion, they’re stored in a list at that address. The higher the rate of collision between objects, the more linear the performance of a hash collection becomes. ## Hashable In Swift, `Array` provides the standard interface for lists and `Set` for sets. In order for an object to be stored in a `Set`, its type must conform to `Hashable` (and by extension, `Equatable`). Swift’s standard [map](https://en.wikipedia.org/wiki/Associative_array) interface, `Dictionary` has a similar constraint on its associated `Key` type. In previous versions of the language, it took quite a bit of [boilerplate code](https://nshipster.com/swift-gyb/) to satisfy the requirements for storing a custom type in a `Set` or `Dictionary`. Consider the following `Color` type, which represents a color using 8-bit values for red, green, and blue intensity: ```swift struct Color { let red: UInt8 let green: UInt8 let blue: UInt8 } ``` To conform to `Equatable`, you had to provide an implementation for the `==` operator. To conform to `Hashable`, you had to provide an implementation of the computed `hashValue` property: ```swift // Swift < 4.1 extension Color: Equatable { static func ==(lhs: Color, rhs: Color) -> Bool { return lhs.red == rhs.red && lhs.green == rhs.green && lhs.blue == rhs.blue } } extension Color: Hashable { var hashValue: Int { return self.red.hashValue ^ self.green.hashValue ^ self.blue.hashValue } } ``` For most developers, implementing `Hashable` was a speed bump on the way to getting real work done, so they’d simply [`XOR`](https://en.wikipedia.org/wiki/Exclusive_or) over all the stored properties and call it a day. One downside to this approach is its high rate of hash collisions. Because XOR is [commutative](https://en.wikipedia.org/wiki/Commutative_property), colors as different as cyan and yellow produce a hash collision: ```swift // Swift < 4.2 let cyan = Color(red: 0x00, green: 0xFF, blue: 0xFF) let yellow = Color(red: 0xFF, green: 0xFF, blue: 0x00) cyan.hashValue == yellow.hashValue // true, collision ``` Most of the time, this isn’t a problem; modern computers are so powerful that you have to get a lot of implementation details wrong in order to notice any decrease in performance. But that’s not to say that details don’t matter — they often matter immensely. More on that later. ## Automatic Synthesis of Hashable Conformance As of Swift 4.1, the compiler automatically synthesizes conformance to the `Equatable` and `Hashable` protocols for types that adopt these protocols in their declaration if their members also conform to those protocols. In addition to being a huge boost to developer productivity, this can drastically reduce the size of a codebase. For instance, our `Color` example from before — is now ⅓ of its original size: ```swift // Swift >= 4.1 struct Color: Hashable { let red: UInt8 let green: UInt8 let blue: UInt8 } ``` Despite these unambiguous improvements to the language, there was still a lingering question about some of the implementation details. In his Swift Evolution proposal [SE-0185: Synthesizing Equatable and Hashable conformance](https://github.com/apple/swift-evolution/blob/master/proposals/0185-synthesize-equatable-hashable.md), [Tony Allevato](https://github.com/allevato) offered this note about hashing functions: > The choice of hash function is left as an implementation detail, not a fixed part of the design; as such, users should not depend on specific characteristics of its behavior. The most likely implementation would call the standard library’s `_mixInt` function on each member’s hash value and then combine them with exclusive-or (`^`), which mirrors the way `Collection` types are hashed today. Fortunately, it didn’t take long for Swift to settle on a hash function. We got our answer in the very next release: ## Hasher Swift 4.2 refines `Hashable` even further by introducing the `Hasher` type and adopting a new universal hashing function. From the Swift Evolution proposal, [SE-0206: Hashable Enhancements](https://github.com/apple/swift-evolution/blob/master/proposals/0206-hashable-enhancements.md): > With a good hash function, simple lookups, insertions and removals take constant time on average. However, when the hash function isn’t carefully chosen to suit the data, the expected time of such operations can become proportional to the number of elements stored in the table. As [Karoy Lorentey](https://github.com/lorentey) and [Vincent Esche](https://github.com/regexident) note, the main draw of hash-based collections like `Set` and `Dictionary` is their ability to look up values in constant time. If the hash function doesn’t produce an even distribution of values, these collections effectively become linked lists. Swift 4.2 implements hashing based on the [SipHash](https://en.wikipedia.org/wiki/SipHash) family of pseudorandom functions, specifically [SipHash-1-3 and SipHash-2-4](https://github.com/apple/swift/blob/master/stdlib/public/core/SipHash.swift), with 1 or 2 rounds of hashing per message block and 3 or 4 rounds of finalization, respectively. Now if you want to customize how your type implements `Hashable`, you can override the `hash(into:)` method instead of `hashValue`. The `hash(into:)` method passes a `Hasher` object by reference, which you call `combine(_:)` on to add the essential state information of your type. ```swift // Swift >= 4.2 struct Color: Hashable { let red: UInt8 let green: UInt8 let blue: UInt8 // Synthesized by compiler func hash(into hasher: inout Hasher) { hasher.combine(self.red) hasher.combine(self.green) hasher.combine(self.blue) } // Default implementation from protocol extension var hashValue: Int { var hasher = Hasher() self.hash(into: &hasher) return hasher.finalize() } } ``` By abstracting away low-level bit manipulation details, developers automatically take advantage of Swift’s built-in hashing function, which has the extra benefit of not reproducing the collisions we had with our original `XOR`-based implementation: ```swift // Swift >= 4.2 let cyan = Color(red: 0x00, green: 0xFF, blue: 0xFF) let yellow = Color(red: 0xFF, green: 0xFF, blue: 0x00) cyan.hashValue == yellow.hashValue // false, no collision ``` ### Customizing Hash Function By default, Swift uses a universal hash function that reduces a sequence of bytes to a single integer. However, you can improve on this by tailoring your hash function to your domain. For example, if you were writing a program to play a board game like chess or go, you might implement [Zobrist hashing](https://en.wikipedia.org/wiki/Zobrist_hashing) to quickly store the game state. ### Guarding Against Hash-Flooding Selecting a cryptographic algorithm like SipHash helps protect against hash-flooding DoS attacks, which deliberately try to generate hash collisions in an attempt to enforce the worst case of hashing data structures and cause a program to slow to a halt. [This caused a bunch of problems for the web in the early 2010’s.](https://arstechnica.com/information-technology/2011/12/huge-portions-of-web-vulnerable-to-hashing-denial-of-service-attack/) To make things even safer, `Hasher` generates random seed values each time an app is launched, to make hash values even less predictable. > You shouldn’t rely on specific hash values or save them across executions. On the rare occasion that you would need deterministic behavior, you can set the environment variable `SWIFT_DETERMINISTIC_HASHING` to disable random hash seeds. --- The challenge of programming analogies is they normalize antisocial behavior by way of edge cases. We excel as software engineers when we can think through all the ways that an attacker might leverage a particular behavior to some sinister end — as in the case of hash-flooding DoS attacks. But by doing so, we risk failing as humans when we apply that knowledge AFK. That is to say… I’m not in any way encouraging you, dear reader, to coordinate outfits with your besties the next time you visit your local Apple retailer in an attempt to sow confusion and discord among Geniuses. Please don’t. Instead, please let your takeaway be this: If you’re waiting at the Genius Bar, stay away from anyone wearing the same color shirt as you. It’ll make things a lot easier for everyone.