我的自定义结构实现了Hashable Protocol。但是,当在键中插入键时发生哈希冲突时Dictionary,不会自动处理它们。我该如何克服这个问题?
Dictionary
我之前曾问过这个问题, 如何在Swift中为Int数组(自定义字符串struct)实现哈希协议。后来我添加了自己的答案,似乎很有效。
但是,最近我hashValue在使用时发现了一个细微的碰撞问题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 }
请注意,为了使等式运算符(==)重载,以使其符合Hashable协议所要求的Equatable协议,它具有全局功能。
微妙的字典关键问题
如果我创建一个Dictionarywith MyStructure作为键
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个键的字典中仅发生一次,则很容易错过。(花了我一段时间才注意到这个问题。)
collision1
collision2
字典文字的明显问题
但是,如果我用字典文字重复此操作,则问题将变得更加明显,因为会引发致命错误。
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说,处理哈希冲突的一种方法是
认为哈希码是非唯一的,并对实际数据使用相等比较器来确定唯一性。
我认为问题是快速可哈希协议哈希函数是否需要返回唯一值?在撰写本文时尚未得到足够的答复。
阅读完SwiftDictionary问题后,如何处理哈希冲突?),我认为Swift会自动处理与的哈希冲突Dictionary。但是显然,如果我使用的是自定义类或结构,那是不对的。
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 }