CODEWITHSUNDEEP
swifthash
Benjohn
Benjohn

Reputation: 13887

Implementing a hash combiner in Swift

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).

Upvotes: 6

Views: 4815

Answers (2)

Lilo
Lilo

Reputation: 2734

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

}

Upvotes: 17

Martin R
Martin R

Reputation: 540145

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

Upvotes: 8

Related Questions