在Swift中实现哈希组合器

Question

我正在扩展一个符合Hashable协议的struct。我将使用DJB2哈希组合器来实现这一点。

为了方便编写其他内容的哈希函数，我想扩展Hashable协议，使我的哈希函数可以像这样编写：

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

但是当我尝试为 Hashable 编写扩展以实现`combineHash(with:)` 时，代码如下：

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

...然后我收到了这个编译错误：

/Users/benjohn/Code/Nice/nice/nice/CombineHash.swift:12:43: 协议 'Hashable' 只能用作泛型约束，因为它具有 Self 或相关类型要求。

这是Swift不允许我这样做，还是我只是做错了，得到一个无用的错误消息？

---

另外提一句： JAL 的评论链接到一个由 Martin 写的 Swift 哈希函数的代码审查，Martin 在下面的被接受的答案中提供。在讨论中，他提到了另一种哈希组合器，它基于c++ boost库中的组合器。这个讨论确实值得一读。替代组合器在测试的数据上有更少的冲突。

- Benjohn

---

在 Code Review Stack Exchange 相关 - JAL

@JAL 不错 - 里面有很有用的信息！特别是Swift的哈希值类型是有符号整数这一点，所以按照这里给出的代码，我的代码性能会很差！ - Benjohn

是的，我曾经遇到过类似的问题。Martin对Boost哈希组合函数的Swift翻译是一个非常好的函数，值得放入你的工具箱中。 - JAL

@Benjohn：只有带符号整数的右移操作会保留符号位，而左移则没有问题。 - Martin R

@MartinR 哦，好的，我的原始哈希函数还不错吧？ :-) 直到现在我才注意到你也就Jal链接的哈希函数写了代码审查！你们两个就像是一个哈希犯罪打击组，防止碰撞并保持大O期望值 - 我为此感谢你们！ - Benjohn

Answer 1

使用苹果开发者文档中的hash(into:)方法：

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

}

- Lilo

Answer 2

如果 P 是一个具有 Self 或关联类型要求的协议，则无法定义类型为 P 的参数。在这种情况下，它是从中继承了 Hashable 的 Equatable 协议，该协议具有 Self 要求：

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

你可以定义一个通用的方法来实现这个功能：

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

- Martin R