Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Implementing a hash combiner in Swift

Tags:

swift

hash

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

like image 291
Benjohn Avatar asked Mar 06 '17 13:03

Benjohn


2 Answers

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

}
like image 170
Lilo Avatar answered Oct 23 '22 14:10

Lilo


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
    }
}
like image 34
Martin R Avatar answered Oct 23 '22 15:10

Martin R