Implementing the Hashable Protocol in Swift with the DJB hash function

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

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] = []

    // ...
}

StackExchange Code Review Q#111545, answer score: 6