如何在Swift中处理字典的哈希冲突

Question

我的自定义结构实现了Hashable
Protocol
。但是，当在键中插入键时发生哈希冲突时Dictionary，不会自动处理它们。我该如何克服这个问题？

背景

我之前曾问过这个问题，
如何在Swift中为Int数组（自定义字符串struct）实现哈希协议。后来我添加了自己的答案，似乎很有效。

但是，最近我hashValue在使用时发现了一个细微的碰撞问题Dictionary。

最基本的例子

我已将代码简化为以下示例。

定制结构

struct MyStructure: Hashable {

    var id: Int

    init(id: Int) {
        self.id = id
    }

    var hashValue: Int {
        get {
            // contrived to produce a hashValue collision for id=1 and id=2
            if id == 1 {
                return 2 
            }
            return id
        }
    }
}

func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
    return lhs.hashValue == rhs.hashValue
}

请注意，为了使等式运算符（==）重载，以使其符合Hashable协议所要求的Equatable协议，它具有全局功能。

微妙的字典关键问题

如果我创建一个Dictionarywith MyStructure作为键

var dictionary = [MyStructure : String]()

let ok = MyStructure(id: 0)            // hashValue = 0
let collision1 = MyStructure(id: 1)    // hashValue = 2
let collision2 = MyStructure(id: 2)    // hashValue = 2

dictionary[ok] = "some text"
dictionary[collision1] = "other text"
dictionary[collision2] = "more text"

print(dictionary) // [MyStructure(id: 2): more text, MyStructure(id: 0): some text]
print(dictionary.count) // 2

相等的哈希值会导致collision1密钥被密钥覆盖collision2。没有警告。如果这样的冲突在带有100个键的字典中仅发生一次，则很容易错过。（花了我一段时间才注意到这个问题。）

字典文字的明显问题

但是，如果我用字典文字重复此操作，则问题将变得更加明显，因为会引发致命错误。

let ok = MyStructure(id: 0)            // hashValue = 0
let collision1 = MyStructure(id: 1)    // hashValue = 2
let collision2 = MyStructure(id: 2)    // hashValue = 2

let dictionaryLiteral = [
    ok : "some text",
    collision1 : "other text",
    collision2 : "more text"
]
// fatal error: Dictionary literal contains duplicate keys

题

我的印象是，不必hashValue总是返回唯一值。例如，马特·汤普森（Matt
Thompson）说，

关于实现自定义哈希函数的最常见误解之一来自……认为哈希值必须是不同的。

尊敬的SO用户@Gaffa说，处理哈希冲突的一种html" target="_blank">方法是

认为哈希码是非唯一的，并对实际数据使用相等比较器来确定唯一性。

我认为问题是快速可哈希协议哈希函数是否需要返回唯一值？在撰写本文时尚未得到足够的答复。

阅读完SwiftDictionary问题后，如何处理哈希冲突？)，我认为Swift会自动处理与的哈希冲突Dictionary。但是显然，如果我使用的是自定义类或结构，那是不对的。

func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
    return lhs.hashValue == rhs.hashValue
}

是否为每个字典键查找或仅在发生哈希冲突时才调用此函数？（更新：请参阅此问题）

当（且仅当）哈希冲突发生时，我该怎么做才能确定唯一性？

Answer 1

func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
return lhs.hashValue == rhs.hashValue
}

请注意，为了使等式运算符（==）重载，以使其符合Hashable协议所要求的Equatable协议，它的全局功能。

您的问题是不正确的 相等 实现。

哈希表（例如Swift字典或Set）需要单独的 相等 和 哈希 实现。

哈希 使您靠近要查找的对象； 平等为 您提供了您正在寻找的确切对象。

您的代码对 哈希 和 相等 使用相同的实现，这将确保发生冲突。

要解决此问题，请实现 相等性 以匹配确切的对象值（但是您的模型定义了相等性）。例如：

func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
    return lhs.id == rhs.id
}