1

我需要使自定义结构符合，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:)方法为属性相同但相反的两个实例生成相同的哈希？

4

2 回答 2

2

这就是哈希的工作方式

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)
    }
于 2019-07-09T04:59:57.723 回答
0

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

苹果的hash(into:)文档说：

用于散列的组件必须与类型的 == 运算符实现中比较的组件相同。

如果它是简单的一对一属性比较（就像所有代码示例所示！），那一切都很好，但是如果您的==方法具有像我这样的条件逻辑怎么办？您如何将其转换为一个值（或多个值）以供散列器使用？

我一直在关注这个细节，直到 Tiran 建议给哈希器提供一个恒定值（比如 2）仍然可以工作，因为==无论如何哈希冲突都会得到解决。你当然不会在生产环境中这样做，因为你会失去哈希查找的所有性能优势，但对我来说，如果你不能让你的哈希参数与你的操作数完全相同==，那么哈希相等逻辑更具包容性（而不是更少）。

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

最后，我意识到我可以在这两种情况下使用完全相同的逻辑，从而避免哈希冲突——好吧，除了由不完美的哈希算法引起的任何冲突。我添加了一个新的私有常量MultiplicationQuestion并将其初始化如下：

uniqueOperands = Set([leftOperand, rightOperand])

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

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

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

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

我已经测试了性能，它与按位运算相当。不仅如此，我的代码在这个过程中也变得更加简洁易读。似乎是双赢的。

于 2019-07-10T05:33:04.670 回答