19

TLDR

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

背景

我之前曾问过这个问题 How to implement the Hashable Protocol in Swift for an Int array (a custom string 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 Protocol 。

微妙的字典关键问题

如果我创建一个DictionarywithMyStructure作为键

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总是返回一个唯一的值。例如，马特汤普森说，

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

受人尊敬的 SO 用户@Gaffa 说，处理哈希冲突的一种方法是

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

在我看来，快速哈希协议哈希函数是否需要返回唯一值？在撰写本文时尚未得到充分回答。

阅读 SwiftDictionary问题后如何处理哈希冲突？，我假设 Swift 会自动处理与Dictionary. 但如果我使用自定义类或结构，显然情况并非如此。

这个评论让我觉得答案在于 Equatable 协议是如何实现的，但我不确定我应该如何改变它。

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

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

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

4

4 回答 4

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

请注意重载等式运算符 (==) 的全局函数，以符合 Hashable 协议所要求的 Equatable 协议。

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

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

hash让你接近你正在寻找的对象；平等让你得到你正在寻找的确切对象。

您的代码对hash和equal使用相同的实现，这将保证发生冲突。

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

func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
    return lhs.id == rhs.id
}
于 2015-07-28T03:08:31.077 回答
4

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

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

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

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

- (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为您实现自定义类型的另一个原因。

于 2015-07-27T23:58:51.137 回答
3

相等的散列值导致collision1 键被collision2 键覆盖。没有警告。如果这样的冲突在有 100 个键的字典中只发生一次，那么它很容易被遗漏。

哈希冲突与它无关。（哈希冲突从不影响结果，只会影响性能。）它的工作方式与记录的完全一致。

Dictionary操作对键的相等( ==) 起作用。字典不包含重复的键（意味着相等的键）。当您使用键设置值时，它会覆盖任何包含相等键的条目。当你得到一个带下标的条目时，它会找到一个键值等于你给的东西，不一定相同。等等。

collision1和collision2相等 ( ==)，基于您定义==运算符的方式。因此，使用 key 设置条目collision2必须覆盖任何带有 key 的条目collision1。

PS 同样的事情也适用于其他语言的字典。例如，在 Cocoa 中，NSDictionary不允许重复键，即isEqual:. 在 Java 中，Maps 不允许重复键，即.equals().

于 2015-07-28T03:25:55.113 回答
1

您可以在此页面的答案和此答案中看到我的评论。我认为所有答案仍然以非常混乱的方式编写。

tl; dr 0)您不需要在 hashValues 之间编写实现 isEqual 即 ==。1)只提供/返回hashValue。2)Equatable像往常一样实施

0)为了符合hashable你必须有一个计算值命名hashValue并给它一个适当的值。与 equatable协议不同，hashValues的比较已经存在。你不需要写：

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

1） 然后它使用hashValue来检查该 hashValue 的索引（通过其对数组计数的模计算）是否存在正在查找的键。它在该索引的键/值对数组中查找。

2） 但是，作为故障保险，即如果有匹配的哈希值，您将回退到常规==函数。（从逻辑上讲，由于故障安全，您需要它。但您也需要它，因为 Hashable 协议符合 Equatable ，因此您必须为 . 编写实现==。否则您会收到编译器错误）

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

结论：

您必须包含 Snippet B，排除 Snippet A，同时还拥有一个hashValue属性

于 2016-11-18T20:21:09.497 回答