swift - Dictionary 在 Swift 中如何使用 Equatable 协议(protocol)？

Question

为了解决this question ，我一直在玩弄一个实现 Hashable 协议(protocol)的自定义结构。我试图查看等价运算符重载 ( == ) 被调用的次数，具体取决于填充 Dictionary 时是否存在哈希冲突。 .

更新

@matt编写了一个更简洁的自定义结构示例，该示例实现了 Hashable 协议(protocol)并显示了 hashValue 的频率。和 ==被叫到。我正在复制his code以下。要查看我的原始示例，请查看 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 的示例中根本没有散列冲突，但是 ==仍在被调用。在我的其他强制散列冲突的实验中(请参阅此问题的编辑历史)，==似乎被随机调用了几次。

这是怎么回事？

Answer 1

我正在从 bugs.swift.org 复制我的答案这里。它谈论集合，但细节以同样的方式适用于字典。

In hashed collections, collisions can occur whenever the number of buckets is smaller than the keyspace. When you're creating a new Set without specifying a minimum capacity, the set might have only one bucket, so when you're inserting the second element, a collision occurs. The insert method will then decide if the storage should be grown, using something called a load factor. If the storage was grown, the existing elements have to be migrated over to the new storage buffer. That's when you're seeing all those extra calls to hashValue when inserting 4.

The reason you're still seeing more calls to == than you would expect if the number of buckets is equal or higher to the number of elements has to do with an implementation detail of the bucket index calculation. The bits of the hashValue are mixed or "shuffled" before the modulo operation. This is to cut down on excessive collisions for types with bad hash algorithms.