Implementing the Hashable Protocol in Swift with the DJB hash function

Question

A while back I made a custom String struct (see github repo) because of the difficulties in dealing with Mongolian Unicode rendering when using Swift String or NSString (see this question and the accepted answer for more details). The struct is an array of UInt32 so that it represents a string of Unicode scalar values.

The most difficult part (see here and here for my StackOverflow questions at the time) was making it conform to the Hashable Protocol so that it could be used as a Dictionary key.

For all that I can tell, everything has been working fine. However, since there was not a lot of documentation and guidance available about implementing the Hashable Protocol, I wanted to make sure that I did it right. Here is the relevant code:

struct ScalarString: SequenceType, Hashable, CustomStringConvertible {
 private var scalarArray: [UInt32] = []
 // ...
 // hashValue needed to implement Hashable protocol
 var hashValue: Int {
 get {
 // 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
 }
 }
}
// Hashable also needs struct to conform to Equatable protocol
func ==(left: ScalarString, right: ScalarString) -> Bool {
 if left.length != right.length {
 return false
 }
 for var i = 0; i < left.length; ++i {
 if left.charAt(i) != right.charAt(i) {
 return false
 }
 }
 return true
}

Answer 1

The Hashable protocol has only one single requirement:

Axiom: x == y implies x.hashValue == y.hashValue.

So let's start with your implementation of ==:

// Hashable also needs struct to conform to Equatable protocol
func ==(left: ScalarString, right: ScalarString) -> Bool {
 if left.length != right.length {
 return false
 }
 for var i = 0; i < left.length; ++i {
 if left.charAt(i) != right.charAt(i) {
 return false
 }
 }
 return true
}

Looking up the definitions of length and charAt() it is clear that here simply the left.scalarArray and right.scalarArray arrays are checked for equality. So the operator can equivalently but simpler be implemented as

// Hashable also needs struct to conform to Equatable protocol
func ==(left: ScalarString, right: ScalarString) -> Bool {
 return left.scalarArray == right.scalarArray
}

From this representation it becomes obvious that your hashValue implementation is correct: It is computed from the scalarArray property, so equal objects have the same hash value.

The hashValue computed property can be simplified using reduce(), note also that for a read-only property, you need not put the getter method inside a get { } block:

// hashValue (to implement Hashable protocol)
var hashValue: Int {
 return self.scalarArray.reduce(5381) {
 (0ドル << 5) &+ 0ドル &+ Int(1ドル)
 }
}

A different question would be how "good" the hash is. The Swift language does not make any requirements here. Always returning 0 would be valid, but of course ineffective when building large dictionaries.

It may be interesting in this context that the hash value of the Foundation type NSArray is simply the number of elements, regardless of the contents.

In your case, the DJB hash function is a well-known hash method for strings, so I do not see any reasons not to use it.

---

Update: As of Swift 4.1, the compiler can synthesize Equatable and Hashable 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] = []
 // ...
}

• Suragch: After your review, I've been meaning to rewrite my former SO answer. I finally got around to it today. If you have time, I would be grateful if you would look it over to make sure that there are no glaring errors and that I did not misunderstand anything in your answer. Here is the link.