小编典典

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

swift

TLDR

我的自定义结构实现了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说,处理哈希冲突的一种方法是

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

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

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

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

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

当(且仅当)哈希冲突发生时,我该怎么做才能确定唯一性?


阅读 338

收藏
2020-07-07

共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
}
2020-07-07