How to implement the Hashable Protocol in Swift for an Int array (a custom string struct)
Update
Martin R writes:
As of Swift 4.1, the compiler can synthesize
Equatable
andHashable
for types conformance automatically, if all members conform to
Equatable/Hashable (SE0185). And as of Swift 4.2, a high-quality hash
combiner is built-in into the Swift standard library (SE-0206).Therefore there is no need anymore to define your own hashing
function, it suffices to declare the conformance:struct ScalarString: Hashable, ... {
private var scalarArray: [UInt32] = []
// ... }
Thus, the answer below needs to be rewritten (yet again). Until that happens refer to Martin R's answer from the link above.
Old Answer:
This answer has been completely rewritten after submitting my original answer to code review.
How to implement to Hashable protocol
The Hashable protocol allows you to use your custom class or struct as a dictionary key. In order to implement this protocol you need to
- Implement the Equatable protocol (Hashable inherits from Equatable)
- Return a computed
hashValue
These points follow from the axiom given in the documentation:
x == y
impliesx.hashValue == y.hashValue
where x
and y
are values of some Type.
Implement the Equatable protocol
In order to implement the Equatable protocol, you define how your type uses the ==
(equivalence) operator. In your example, equivalence can be determined like this:
func ==(left: ScalarString, right: ScalarString) -> Bool {
return left.scalarArray == right.scalarArray
}
The ==
function is global so it goes outside of your class or struct.
Return a computed hashValue
Your custom class or struct must also have a computed hashValue
variable. A good hash algorithm will provide a wide range of hash values. However, it should be noted that you do not need to guarantee that the hash values are all unique. When two different values have identical hash values, this is called a hash collision. It requires some extra work when there is a collision (which is why a good distribution is desirable), but some collisions are to be expected. As I understand it, the ==
function does that extra work. (Update: It looks like ==
may do all the work.)
There are a number of ways to calculate the hash value. For example, you could do something as simple as returning the number of elements in the array.
var hashValue: Int {
return self.scalarArray.count
}
This would give a hash collision every time two arrays had the same number of elements but different values. NSArray
apparently uses this approach.
DJB Hash Function
A common hash function that works with strings is the DJB hash function. This is the one I will be using, but check out some others here.
A Swift implementation provided by @MartinR follows:
var hashValue: Int {
return self.scalarArray.reduce(5381) {
($0 << 5) &+ $0 &+ Int($1)
}
}
This is an improved version of my original implementation, but let me also include the older expanded form, which may be more readable for people not familiar with reduce
. This is equivalent, I believe:
var hashValue: Int {
// DJB Hash Function
var hash = 5381
for(var i = 0; i < self.scalarArray.count; i++)
{
hash = ((hash << 5) &+ hash) &+ Int(self.scalarArray[i])
}
return hash
}
The &+
operator allows Int
to overflow and start over again for long strings.
Big Picture
We have looked at the pieces, but let me now show the whole example code as it relates to the Hashable protocol. ScalarString
is the custom type from the question. This will be different for different people, of course.
// Include the Hashable keyword after the class/struct name
struct ScalarString: Hashable {
private var scalarArray: [UInt32] = []
// required var for the Hashable protocol
var hashValue: Int {
// DJB hash function
return self.scalarArray.reduce(5381) {
($0 << 5) &+ $0 &+ Int($1)
}
}
}
// required function for the Equatable protocol, which Hashable inheirits from
func ==(left: ScalarString, right: ScalarString) -> Bool {
return left.scalarArray == right.scalarArray
}
Other helpful reading
- Which hashing algorithm is best for uniqueness and speed?
- Overflow Operators
- Why are 5381 and 33 so important in the djb2 algorithm?
- How are hash collisions handled?
Credits
A big thanks to Martin R over in Code Review. My rewrite is largely based on his answer. If you found this helpful, then please give him an upvote.
Update
Swift is open source now so it is possible to see how hashValue
is implemented for String
from the source code. It appears to be more complex than the answer I have given here, and I have not taken the time to analyze it fully. Feel free to do so yourself.
How to natively hash a struct without randomization?
You should make your own protocol, something like:
protocol Signable {
/// A signature that's stable across app launches
var signature: Signature { get }
}
Equatable
/Hashable
are standard protocols with very specific semantics (Equality implies substitutability, and Hashability is a heuristic, as a performance optimization of Equatable
). They're not catch-all bags of syntax for anything vaguely similar to equality checking or hashing.
Also beware: the randomly seeded behavior of Hasher
is intentional. It protects you against hash-flooding DoS attacks. You should be very careful circumventing this, because you'll be exposing yourself to this vector.
Using signature
to compare instances persisted across app launches seems fine. But I would not recommend using that to implement any kind of hashed data structures, which could be attacked to degenerate into linear-time-lookups.
Struct hash for different types
You can make a protocol containing all the shared data, so both S1
and S2
go through the same hasher.
I created a SharedData
protocol containing the shared properties (only data
in this case) and gave it a Hashable
implementation. Then S1
and S2
now conform to SharedData
. It looks like this:
protocol SharedData: Hashable {
var data: String { get }
}
extension SharedData {
func hash(into hasher: inout Hasher) {
hasher.combine(data)
}
}
struct S1: SharedData {
let data: String
let otherData: String
// ... Equality & Hash functions, both only use data
}
struct S2: SharedData {
let data: String
let otherData: Int
// ... Equality & Hash functions, both only use data
}
And the comparison looks like this:
print(S1(data: "hi", otherData: "there").hashValue)
print(S2(data: "hi", otherData: 1).hashValue)
let set: Set = [S1(data: "Hello", otherData: "world!").hashValue, S1(data: "abc", otherData: "123").hashValue]
let obj2 = S2(data: "Hello", otherData: 0)
print(set.contains(obj2.hashValue))
Prints:
-5068166682035457964 // <- these change every program execution
-5068166682035457964
true
Unfortunately it's not possible to do the following, yet:
let set: Set = [S1(data: "Hello", otherData: "world!"), S1(data: "abc", otherData: "123")]
Error:
Protocol 'SharedData' as a type cannot conform to 'Hashable'
I believe SE-0309 (Unlock existentials for all protocols) could fix this.
Make a swift protocol conform to Hashable
Deriving the protocol from Hashable
and using a type eraser might help here:
protocol SomeLocation: Hashable {
var name: String { get }
var coordinates: Coordinate { get }
}
struct AnyLocation: SomeLocation {
let name: String
let coordinates: Coordinate
init(_ location: L) {
name = location.name
coordinates = location.coordinates
}
}
You then can simply declare the protocol conformance on the structs, and if Coordinate
is already Hashable
, then you don't need to write any extra hashing code code, since the compiler can automatically synthesize for you (and so will do for new types as long as all their properties are Hashable
:
struct ShopLocation: SomeLocation, Decodable {
var name: String
var coordinates: Coordinate
}
struct CarLocation: SomeLocation, Decodable {
var name: String
var coordinates: Coordinate
}
If Coordinate
is also Codable
, then you also can omit writing any code for the encoding/decoding operations, the compile will synthesize the required methods (provided all other properties are already Codable
).
You can then use the eraser within the annotation class by forwardingn the initializer constraints:
final class LocationAnnotation: NSObject, MKAnnotation {
let location: AnyLocation
init(location: L) {
self.location = AnyLocation(location)
super.init()
}
override var hash: Int {
location.hashValue
}
override func isEqual(_ object: Any?) -> Bool {
(object as? LocationAnnotation)?.location == location
}
}
Make struct Hashable?
Simply return dbName.hashValue
from your hashValue
function. FYI - the hash value does not need to be unique. The requirement is that two objects that equate equal must also have the same hash value.
struct PetInfo: Hashable {
var petName: String
var dbName: String
var hashValue: Int {
return dbName.hashValue
}
static func == (lhs: PetInfo, rhs: PetInfo) -> Bool {
return lhs.dbName == rhs.dbName && lhs.petName == rhs.petName
}
}
Conforming to Hashable protocol?
You're missing the declaration:
struct DateStruct: Hashable {
And your ==
function is wrong. You should compare the three properties.
static func == (lhs: DateStruct, rhs: DateStruct) -> Bool {
return lhs.year == rhs.year && lhs.month == rhs.month && lhs.day == rhs.day
}
It's possible for two different values to have the same hash value.
Swift, how to implement Hashable protocol based on object reference?
If you are working with classes and not structs, you can use the ObjectIdentifier
struct. Note that you also have to define ==
for your class in order to conform to Equatable
(Hashable
requires it). It would look something like this:
class MyClass: Hashable { }
func ==(lhs: MyClass, rhs: MyClass) -> Bool {
return ObjectIdentifier(lhs) == ObjectIdentifier(rhs)
}
class MyClass: Hashable {
var hashValue: Int {
return ObjectIdentifier(self).hashValue
}
}
Related Topics
How to Load a Xib File in a Uiview
How to Obtain a Dynamic Table View Section Header Height Using Auto Layout
Uicollectionview: Must Be Initialized with a Non-Nil Layout Parameter
Detecting Collisions in Sprite Kit
Dynamic Height Issue for Uitableview Cells (Swift)
How to Get Uikeyboard Size with iOS
Make a Uibutton Programmatically in Swift
iOS Perform Action After Period of Inactivity (No User Interaction)
Arkit - Apply Cifilter to a Specific Vertices of Arfaceanchor
Ios: Serialize/Deserialize Complex JSON Generically from Nsobject Class
How to Overload an Assignment Operator in Swift
Lldb (Swift): Casting Raw Address into Usable Type
Cocoapods - 'Pod Install' Takes Forever
Why Does Apple Recommend to Use Dispatch_Once for Implementing the Singleton Pattern Under Arc