Dictionary如何在Swift中使用Equatable协议？ [英] How does Dictionary use the Equatable protocol in Swift?
问题描述
为了解决此问题，我一直在玩一个实现Hashable协议的自定义结构体。我试图看到等价运算符重载（ == ）被调用多少次，这取决于是否有一个哈希冲突，当填充一个字典。
In order to solve this question, I have been playing around with a custom struct that implements the Hashable Protocol. I'm trying to see how many times the equivalency operator overload (==) gets called depending on if there is a hash collision or not when populating a Dictionary.
更新
@matt 写了一个更清晰的自定义结构实例，它实现了Hashable协议，并显示了 hashValue 和 == 调用。我正在复制以下他的代码。要查看我的原始示例，请查看修改历史记录。
@matt wrote a much cleaner example of a custom struct that implements the Hashable protocol and shows how often hashValue and == get called. I am copying his code below. To see my original example, check out the edit history.
struct S : Hashable {
static func ==(lhs:S,rhs:S) -> Bool {
print("called == for", lhs.id, rhs.id)
return lhs.id == rhs.id
}
let id : Int
var hashValue : Int {
print("called hashValue for", self.id)
return self.id
}
init(_ id:Int) {self.id = id}
}
var s = Set<S>()
for i in 1...5 {
print("inserting", i)
s.insert(S(i))
}
这将产生结果：
/*
inserting 1
called hashValue for 1
inserting 2
called hashValue for 2
called == for 1 2
called hashValue for 1
called hashValue for 2
inserting 3
called hashValue for 3
inserting 4
called hashValue for 4
called == for 3 4
called == for 1 4
called hashValue for 2
called hashValue for 3
called hashValue for 1
called hashValue for 4
called == for 3 4
called == for 1 4
inserting 5
called hashValue for 5
*/
由于Hashable使用Equatable来区分哈希冲突（我认为无论如何），我会期望 func ==（）只有当有哈希冲突时被调用。但是，在上面的@ matt的例子中，根本没有哈希冲突，而$ code> == 仍在被调用。在我的其他实验中，强制哈希冲突（见这个问题的编辑历史）， == 似乎被称为随机数。
Since Hashable uses Equatable to differentiate hash collisions (I assume anyway), I would expect func ==() only to be called when there are hash collisions. However, there are no hash collisions at all in @matt's example above and yet == is still being called. In my other experiments forcing hash collisions (see this question's edit history), == seemed to be called a random number of times.
这里发生了什么？
推荐答案
嗯，有你的答案：
实际发生的情况：
What's actually happening:
- 我们在插入时仅对值进行一次哈希。
- 我们不使用哈希值来比较元素，只能使用==。使用哈希进行比较只适用于您存储哈希值，但
意味着每个词典的更多内存使用。
需要评估的妥协。 - 在评估Dictionary是否适合该元素之前，我们尝试插入该元素。这是因为元素可能已经在
Dictionary中，在这种情况下，我们不再需要更多的容量。 - 当我们调整Dictionary的大小时，我们必须重新整理所有内容因为我们没有存储哈希值。
- We hash a value only once on insertion.
- We don't use hashes for comparison of elements, only ==. Using hashes for comparison is only reasonable if you store the hashes, but that means more memory usage for every Dictionary. A compromise that needs evaluation.
- We try to insert the element before evaluating if the Dictionary can fit that element. This is because the element might already be in the Dictionary, in which case we don't need any more capacity.
- When we resize the Dictionary, we have to rehash everything, because we didn't store the hashes.
所以你看到的是：
这篇关于Dictionary如何在Swift中使用Equatable协议？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
