具有可互换属性的可哈希结构？

Question

我需要使自定义结构符合 Hashable 以便我可以将其用作字典键类型。但挑战在于，为了识别唯一实例，结构的两个属性是可以互换的。

这里有一个简单的例子来说明这个问题：

struct MultiplicationQuestion {
    let leftOperand: Int
    let rightOperand: Int
    var answer: Int { return leftOperand * rightOperand }
}

识别唯一性 MultiplicationQuestion 的两个重要属性是 leftOperand 和 rightOperand，但它们的顺序无关紧要，因为“1 x 2”是与“2 x 1”基本相同的问题。（由于我不会在这里详述的原因，它们需要作为单独的属性保留。）

我尝试按如下方式定义 Hashable 一致性，我知道我为 == 定义的相等性与内置 Hasher 将要执行的操作之间存在冲突：

extension MultiplicationQuestion: Hashable {
    static func == (lhs: MultiplicationQuestion, rhs: MultiplicationQuestion) -> Bool {
        return (lhs.leftOperand == rhs.leftOperand && lhs.rightOperand == rhs.rightOperand) || (lhs.leftOperand == rhs.rightOperand && lhs.rightOperand == rhs.leftOperand)
    }
    func hash(into hasher: inout Hasher) {
        hasher.combine(leftOperand)
        hasher.combine(rightOperand)
    }
}

我通过创建两组问题并对它们执行各种操作来测试它：

var oneTimesTables = Set<MultiplicationQuestion>()
var twoTimesTables = Set<MultiplicationQuestion>()
for i in 1...5 {
    oneTimesTables.insert( MultiplicationQuestion(leftOperand: 1, rightOperand: i) )
    twoTimesTables.insert( MultiplicationQuestion(leftOperand: 2, rightOperand: i) )
}

let commonQuestions = oneTimesTables.intersection(twoTimesTables)
let allQuestions = oneTimesTables.union(twoTimesTables)

希望的结果（一厢情愿）是 commonQuestions 包含一个问题 (1 x 2)，而 allQuestions 包含九个问题，已删除重复项。

然而，

实际结果是不可预测的。如果我运行游乐场多次，我会得到不同的结果。大多数时候，commonQuestions.count 是 0，但有时是 1。大多数时候，allQuestions.count 是 10，但有时是 9。（我不确定我在期待什么，但这种不一致确实令人惊讶！）

如何使 hash(into:) 方法为两个属性相同但相反的实例生成相同的散列？

Answer 1

这就是 Hasher 的工作原理

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

However, the underlying hash algorithm is designed to exhibit avalanche effects: slight changes to the seed or the input byte sequence will typically produce drastic changes in the generated hash value.

所以这里的问题在 hash(into:) func

由于顺序很重要 combine 操作不可交换。您应该找到一些其他函数作为此结构的哈希。在你的情况下，最好的选择是

    func hash(into hasher: inout Hasher) {
        hasher.combine(leftOperand & rightOperand)
    }

正如@Martin R 指出的那样，为了减少碰撞，最好使用 ^

    func hash(into hasher: inout Hasher) {
        hasher.combine(leftOperand ^ rightOperand)
    }

Answer 2

（和评论）对我帮助很大，我已将其标记为正确。尽管如此，我认为值得添加另一个答案来分享我学到的一些东西并提出另一种解决问题的方法。

Apple 的 hash(into:) documentation 说：

The components used for hashing must be the same as the components compared in your type’s == operator implementation.

如果它是一个简单的 one-to-one 属性比较（如所有代码示例所示！），那很好，但是如果您的 == 方法具有像我一样的条件逻辑怎么办？您如何将其转化为一个（或多个）值以提供给哈希器？

我一直被这个细节所困扰，直到 Tiran 建议向散列器提供一个常量值（如 2）仍然有效，因为散列冲突无论如何都由 == 解决。你当然不会在生产中这样做，因为你会失去哈希查找的所有性能优势，但 take-home 对我来说是，如果你不能使你的哈希参数完全与您的 == 操作数相同，使哈希相等逻辑 包含更多 （不少于）。

Tiran Ut 的答案中的解决方案之所以有效，是因为按位运算不关心操作数的顺序，就像我的 == 逻辑一样。有时，两个完全不同的对可能会生成相同的值（导致有保证的哈希冲突），但在这些情况下唯一真正的后果是对性能的小打击。

虽然最后，我意识到我可以在两种情况下使用完全相同的逻辑，从而避免散列冲突——好吧，除了由不完善的散列算法引起的冲突反正。我在 MultiplicationQuestion 中添加了一个新的私有常量并初始化如下：

uniqueOperands = Set([leftOperand, rightOperand])

排序数组也可以，但 Set 似乎是更优雅的选择。由于 Set 没有顺序，因此 ==（使用 && 和 ||）的冗长条件逻辑已经巧妙地封装在 Set 类型中。

现在，我可以使用完全相同的值来测试相等性并提供给哈希器：

static func ==(lhs: MultiplicationQuestion, rhs: MultiplicationQuestion) -> Bool {
    return lhs.uniqueOperands == rhs.uniqueOperands
}

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

我已经测试了性能，它与按位运算相当。不仅如此，我的代码在这个过程中变得更加简洁和可读。好像是 win-win.

具有可互换属性的可哈希结构？

Hashable struct with interchangeable properties?

hashable

swift