时间戳

首页 > 解决方案 > 具有可互换属性的可散列结构？

swift - 具有可互换属性的可散列结构？

问题描述

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

这是一个简化的示例来说明问题：

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

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

我尝试如下定义一致性，因为我知道在我定义的相等性和内置的 Hasher 将要做什么Hashable之间存在冲突：==

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:)方法为属性相同但相反的两个实例生成相同的哈希？

标签： swifthashable

解决方案

这就是哈希的工作方式

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

然而，底层散列算法被设计为表现出雪崩效应：种子或输入字节序列的微小变化通常会导致生成的散列值发生剧烈变化。

所以这里的问题是 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)
    }

推荐阅读