Trying to Build a Better Hashable

The standard example: You have a type that is uniquely identifiable by an id property and want to be able to use contains on a collection of this type, while not worrying so much about having duplicates. For a single struct, we can conform to Hashable and implement a == case to handle the object.

The reason I am returning id above instead of running it through a hash function is that id is already a unique identifier and an Int.

Read section below if you’d like a general overview of hashing

Hash Values

A hashValue is traditionally a value generated from an input by a hash function, which runs in constant time. The hashValue is then used internally as part of calculating object equality. Since the hash function output should be some bytes fewer, there is no way to avoid repeated output values… Meaning two different input values can potentially have the same hash output. The point to remember here is that if two types have different outputs, their input is definitely not the same.

The purpose of a hashValue is a quicker, constant time, implementation of proving inequality when hashValues are different. In the case of equal hashValues we only know they COULD be equivalent. So in these cases a function to compare the type is needed for checking definite equality, thus the need for the == function definition(and why Hashable requires conformance to the Equatable protocol).

Id Hashable Protocol

What if we have many different types that are uniquely identifable by id? We of course expand the previous implementation into it’s own protocol!

This by default works the same way as our first example, assuming that the type has a property id that is a unique identifer. We also replace the the Equatable == function with a generic one conforming to the IdHashable protocol. We could now rewrite the original implementation as such below:

If we decide we are going to change what constitutes the uniqueness of the type, to something more complex than an Int, to a String or something…

We could easily piggyback off of the hashValue implementation on the String struct. Although a sound way of implementing a hashValue, this defeats the purpose of using our custom protocol over the Hashable protocol since we need to implement a type specific equality function still… Since our id value can now be the same for two different string values.

For these cases our protocol seems a lot less useful,… since we need to implement == outside of the function. So we are doing just as much work as we’d be doing to implement Hashable, but we could improve it slightly by bringing the logic for == function into the type definition and leaving it with a default definition that compares id.

Now this seems more like Objective-C, but we don’t have to worry about including a function outside of the conforming type and can just implement id if you have a uniquely identifiable Int, while still having the option to also implement isEqual for types with true hash values.

Our conforming types now look like:

And our uniquely Identifying type looks like:

More to note on isEqual and global operator definitions, I recently found out that operators are eventually planned to be allowed inside of type definitions, see mention here in this swift-evolution thread.