哈希冲突是如何处理的？

Question

我最近学到了一些关于哈希值的知识，因此也听说过哈希冲突的问题。

因此，我想知道:如何处理这些问题？

例如，Swift的Dictonary使用带键的散列值。我假设它通过散列查找它的值。那么，Swift的Dictionary将如何存储不同键的值，而这些键恰好具有相同的哈希？

Answer 1

从根本上讲，有两种处理哈希冲突的主要方法:当具有碰撞哈希码的项存储在单独的数据结构中时，使用单独的链接；当碰撞数据存储在使用某种算法选择的另一个可用桶中时，打开寻址。

这两种策略都有许多子策略，维基百科。一个特定的实现所使用的确切策略是特定于实现的，这并不奇怪，因此作者可以在任何时候更改它，以获得更高的效率，而不会打破用户的假设。

A这一点，了解Swift如何处理冲突的唯一方法是拆卸库(也就是说，除非您为Apple工作，并且可以访问源代码)。NSDictionary，并确定它使用http://en.wikipedia.org/wiki/Linear_probing，这是开放寻址技术中最简单的变体。

Answer 2

有两种基本技术：

1. 使用不同的素数重散，通常是N-2，其中N是原始素数，选择N和N-2都是素数。
2. 每个散列使用一个列表。

或者两者都有。

Answer 3

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

下面是一个指向解释一切的实际源代码文档的链接：https://github.com/apple/swift/blob/master/stdlib/public/core/HashedCollections.swift.gyb