Implementing a hash combiner in Swift

Question

I'm extending a struct conform to Hashable. I'll use the DJB2 hash combiner to accomplish this.

To make it easy to write hash function for other things, I'd like to extend the Hashable protocol so that my hash function can be written like this:

extension MyStruct: Hashable {
  public var hashValue: Int {
    return property1.combineHash(with: property2).combineHash(with: property3)
  }
}

But when I try to write the extension to Hashable that implements `combineHash(with:), like this:

extension Hashable {
  func combineHash(with hashableOther:Hashable) -> Int {
    let ownHash = self.hashValue
    let otherHash = hashableOther.hashValue
    return (ownHash << 5) &+ ownHash &+ otherHash
  }
}

… then I get this compilation error:

/Users/benjohn/Code/Nice/nice/nice/CombineHash.swift:12:43: Protocol 'Hashable' can only be used as a generic constraint because it has Self or associated type requirements

Is this something that Swift won't let me do, or am I just doing it wrong and getting an unhelpful error message?

Aside A comment from JAL links to a code review of a swift hash function that is also written by Martin who provides the accepted answer below! He mentions a different hash combiner in that discussion, which is based on one in the c++ boost library. The discussion really is worth reading. The alternative combiner has fewer collisions (on the data tested).

[Related on Code Review Stack Exchange](http://codereview.stackexchange.com/q/148763/73433) — JAL, Mar 06 '17 at 14:03
@JAL Nice one – useful info in there! Particularly the point that Swift's hash value type is a signed int, so my code would perform poorly as given here! — Benjohn, Mar 06 '17 at 14:09
Yes, I had a similar issue. Martin's Swift translation of the Boost hash combine function is a great function to have in your toolbox. — JAL, Mar 06 '17 at 14:11
@Benjohn: Only right-shifts of signed integers preserve the sign bit. Your left-shifts are unproblematic. — Martin R, Mar 06 '17 at 14:20
@MartinR Ah, okay, my original hash isn't that bad? :-) I hadn't noticed until now that you also wrote the code review regarding the hash that Jal linked to! The two of you are like a hash-crime fighting duo, preventing collisions and maintaining big O expectations – I thank you for it! — Benjohn, Mar 06 '17 at 14:30

score 16 · Answer 1 · edited Oct 10 '19 at 06:21

Use the method hash(into:) from the Apple Developer Documentation:

https://developer.apple.com/documentation/swift/hashable

struct GridPoint {
    var x: Int
    var y: Int
}

extension GridPoint: Hashable {

    static func == (lhs: GridPoint, rhs: GridPoint) -> Bool {
        return lhs.x == rhs.x && lhs.y == rhs.y
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(x)
        hasher.combine(y)
    }

}

score 8 · Accepted Answer · answered Mar 06 '17 at 13:44

You cannot define a parameter of type P if P is a protocol which has Self or associated type requirements. In this case it is the Equatable protocol from which Hashable inherits, which has a Self requirement:

public static func ==(lhs: Self, rhs: Self) -> Bool

What you can do is to define a generic method instead:

extension Hashable {
    func combineHash<T: Hashable>(with hashableOther: T) -> Int {
        let ownHash = self.hashValue
        let otherHash = hashableOther.hashValue
        return (ownHash << 5) &+ ownHash &+ otherHash
    }
}

Implementing a hash combiner in Swift

2 Answers2

Linked