简述
我的自定义结构实现了Hashable Protocol。然而,在向Dictionary
中插入键时发生哈希冲突时,它们不会自动处理。我该如何解决这个问题?
背景
我以前曾在这里问过这个问题——如何为Int数组(自定义字符串结构)在Swift中实现Hashable Protocol。后来我添加了自己的答案,似乎是有效的。
然而,最近我发现使用Dictionary
时存在hashValue
冲突的微妙问题。
最基本的示例
我已将代码简化到以下示例:
自定义结构
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
}
请注意全局函数可以重载相等运算符(==),以符合Equatable Protocol的要求,该协议是Hashable Protocol所必需的。
微妙的字典键问题
如果我使用MyStructure
作为键创建一个Dictionary
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
并不总是需要返回一个唯一的值,比如Mattt Thompson所说的:
关于实现自定义哈希函数的最常见错误之一就是......认为哈希值必须是唯一的。
而备受尊敬的SO用户@Gaffa则表示,处理哈希冲突的一种方法是
认为哈希码不是唯一的,并使用等值比较器来确定唯一性。
在我看来,截至撰写本文时,Swift中的可哈希协议哈希函数是否需要返回唯一值的问题还没有得到足够的解答。
在阅读了Swift Dictionary
问题如何处理哈希冲突?之后,我假设Swift会自动处理Dictionary
中的哈希冲突。但是,如果我使用自定义类或结构,则显然不是这样。
这个评论让我想到答案可能在如何实现可比较协议上,但我不确定该如何更改它。
func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
return lhs.hashValue == rhs.hashValue
}
这个函数是在每次字典键查找时都被调用,还是只有在哈希冲突时才被调用?(更新:请参见此问题)
当且仅当发生哈希冲突时,我应该怎么做才能确定唯一性?
1
和2
只是为了演示冲突,对吗? - mfaani