哈希冲突是如何处理的？

Question

我最近学习了一些哈希值的知识，也听说了哈希碰撞的问题。
因此，我想知道：如何处理这些问题？

例如，Swift的Dictionary使用其键的哈希值。我猜它通过哈希查找其值。那么，如果具有相同哈希的不同键，Swift的Dictionary将如何存储值？

- Marcus Rossel

Answer 1

基本上，处理哈希冲突有两种主要方法 - 分离链接，当具有相同哈希码的项存储在单独的数据结构中时，以及开放地址法，当冲突数据存储在使用某些算法选择的另一个可用存储桶中时。

两种策略都有许多子策略，在维基百科中描述。特定实现使用的确切策略是实现特定的，因此作者可以随时更改它以获得更有效的东西，而不会破坏其用户的假设。

此时，找出Swift如何处理冲突的唯一方法就是反汇编库（即，除非您为Apple工作并且可以访问源代码）。好奇的人这样做了NSDictionary，并确定它使用线性探测，这是开放寻址技术的最简单变化。

- Sergey Kalinichenko

Answer 2

有两种基本技术：

1. 使用不同的质数进行重新散列，通常选择原始质数N-2，使得N和N-2都是质数。
2. 每个哈希使用一个列表。

或者两者都使用。

- user207421

Answer 3

Swift字典使用开放寻址和线性探测。

这里有一个链接到实际源文件文档，详细解释了所有内容: https://github.com/apple/swift/blob/master/stdlib/public/core/HashedCollections.swift.gyb

- Adam Zerby