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

Question

TLDR

我的自定义结构实现了Hashable Protocol.但是,当在a中插入密钥时发生散列冲突时Dictionary,它们不会自动处理.我该如何克服这个问题？

背景

我之前曾问过这个问题 如何在Swift中为Int数组(自定义字符串结构)实现Hashable Protocol.后来我添加了自己的答案,这似乎有效.

但是,最近我hashValue在使用a时发现了碰撞的微妙问题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
}

请注意全局函数重载相等运算符(==)以符合Hasable Protocol所需的Equatable Protocol.

微妙的词典关键问题

如果我创建一个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个键的字典中,那么它很容易被遗漏.(我花了很长时间才注意到这个问题.)

Dictionary字面的明显问题

但是,如果我用字典文字重复这一点,问题会变得更加明显,因为会抛出致命的错误.

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 hashable协议哈希函数需要返回唯一值吗？在撰写本文时尚未得到充分的回答.

阅读Swift Dictionary问题后如何处理哈希冲突？我假设Swift自动处理哈希冲突Dictionary.但是,如果我使用自定义类或结构,显然不是这样.

这个评论让我觉得答案是如何实现Equatable协议,但我不确定如何更改它.

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

是为每个字典键查找调用此函数还是仅在存在哈希冲突时调用此函数？(更新:看到这个问题)

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

Answer 1

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

请注意全局函数重载相等运算符(==)以符合Hasable Protocol所需的Equatable Protocol.

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

哈希表(例如Swift词典或集合)需要单独的相等和哈希实现.

hash让你接近你正在寻找的对象; 平等为您提供您正在寻找的确切对象.

您的代码使用相同的哈希和相等实现,这将保证冲突.

要解决此问题,请实现相等以匹配确切的对象值(但是您的模型定义了相等性).例如:

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

Answer 2

我认为你已经拥有了所需的所有拼图——你只需要将它们组合在一起即可。你有很多很棒的资源。

哈希冲突是可以的。如果发生哈希冲突，将检查对象是否相等（仅针对具有匹配哈希的对象）。因此，对象的Equatable一致性需要基于 以外的东西hashValue，除非您确定哈希值不会发生冲突。

这就是符合的对象Hashable也必须符合的确切原因Equatable。当哈希无法解决问题时，Swift 需要一种更针对特定领域的比较方法。

在同一篇NSHipster 文章中，您可以看到 Mattt在他的示例类中isEqual:是如何实现的。具体来说，他有一种方法可以检查一个人的其他属性（出生日期、全名）以确定平等。hashPersonisEqualToPerson:

- (BOOL)isEqualToPerson:(Person *)person {
  if (!person) {
    return NO;
  }

  BOOL haveEqualNames = (!self.name && !person.name) || [self.name isEqualToString:person.name];
  BOOL haveEqualBirthdays = (!self.birthday && !person.birthday) || [self.birthday isEqualToDate:person.birthday];

  return haveEqualNames && haveEqualBirthdays;
}

在检查相等性时，他不使用哈希值 - 他使用特定于他的 person 类的属性。

同样，Swift 不允许您简单地使用对象作为字典键——通过协议继承隐式地使用——键也Hashable必须符合。Equatable对于标准库 Swift 类型，这已经得到处理，但对于您的自定义类型和类，您必须创建自己的==实现。这就是为什么 Swift 不会自动处理与自定义类型的字典冲突 - 你必须Equatable自己实现！

作为告别的想法，Mattt 还指出，您通常可以进行身份​​检查，以确保您的两个对象位于不同的内存地址，因此是不同的对象。在 Swift 中，会像这样：

if person1 === person2 {
    // ...
}

这里不保证person1和person2具有不同的属性，只是它们在内存中占据不同的空间。相反，在较早的isEqualToPerson:方法中，不能保证具有相同姓名和出生日期的两个人实际上是同一个人。因此，您必须考虑什么对您的特定对象类型有意义。这也是 Swift 不Equatable为您实现自定义类型的另一个原因。