Dictionary如何在Swift中使用Equatable协议？

Question

为了解决这个问题,我一直在玩一个实现Hashable Protocol的自定义结构.我正在尝试查看等效运算符overload(==)被调用多少次,具体取决于填充a时是否存在哈希冲突Dictionary.

更新

@matt编写了一个更清晰的自定义结构示例,该结构实现了Hashable协议并显示了调用的频率hashValue和==调用次数.我在下面复制他的代码.要查看我的原始示例,请查看编辑历史记录.

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的答案.它讨论集合,但细节以相同的方式应用于字典.

在散列集合中,只要存储桶的数量小于键空间,就会发生冲突.当您在未指定最小容量的情况下创建新集时,该集可能只有一个存储桶,因此当您插入第二个元素时,会发生冲突.然后,插入方法将使用称为加载因子的东西来决定是否应该增长存储.如果存储增长,则必须将现有元素迁移到新的存储缓冲区.当你在插入4时看到所有额外的hashValue调用时.

如果桶的数量等于或大于元素数量,您仍然会看到更多的==调用次数,这与桶指数计算的实现细节有关.在模运算之前,hashValue的位被混合或"混洗".这是为了减少具有错误哈希算法的类型的过度冲突.

Answer 2

嗯,这是你的答案:

https://bugs.swift.org/browse/SR-3330?focusedCommentId=19980&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-19980

实际发生了什么:

• 我们只在插入时哈希一个值.
• 我们不使用哈希来比较元素,只有==.使用哈希进行比较只有在存储哈希值时才合理,但这意味着每个词典的内存使用量都会增加.需要评估的折衷方案.
• 我们尝试在评估Dictionary是否适合该元素之前插入元素.这是因为元素可能已经在Dictionary中,在这种情况下我们不再需要任何容量.
• 当我们调整字典大小时,我们必须重新编写所有内容,因为我们没有存储哈希值.

所以你看到的是:

• 搜索关键字的一个哈希值
• 一些==(寻找空间)
• 集合中每个元素的哈希值(调整大小)
• 搜索键的一个哈希值(实际上完全是浪费,但考虑到它只发生在O重新分配后才发生)
• some =='s(在新缓冲区中搜索空格)

我们都完全错了.他们根本不使用哈希 - 只是 == - 来决定这是否是一个独特的关键.然后在收集增长的情况下进行第二轮调用.