对于哈希冲突这个问题，我们有两类解决方案：
● 一类是构造尽可能理想的 Hash 函数，使得 Hash 以后得到的数值尽可能平均分布，从而减少冲突发生的概率；
● 另一类是在冲突发生以后，通过「提供冲突解决方案」来完成存储和查找。最常用的两种冲突解决方案是「开放寻址法」和「链表法」。
下面，我就来介绍一下这两种方法，并且重点看看它们对检索效率的影响。
如何利用开放寻址法解决 Hash 冲突？
所谓「开放寻址法」，就是在冲突发生以后，最新的元素需要寻找新空闲的数组位置完成插入。那我们该如何寻找新空闲的位置呢？我们可以使用一种叫作 线性探查（Linear Probing）的方案来进行查找。
线性探查 的插入逻辑很简单：在当前位置发现有冲突以后，就顺序去查看数组的下一个位置，看看是否空闲。如果有空闲，就插入；如果不是空闲，再顺序去看下一个位置，直到找到空闲位置插入为止。
查询逻辑也和插入逻辑相似。我们先根据 Hash 值去查找相应数组下标的元素，如果该位置不为空，但是存储元素的 Key 和查询的 Key 不一致，那就顺序到数组下一个位置去检索，就这样依次比较 Key。如果访问元素的 Key 和查询 Key 相等，我们就在哈希表中找到了对应元素；如果遍历到空闲处，依然没有元素的 Key 和查询 Key 相等，则说明哈希表中不存在该元素。
为了帮助你更好地理解，我们来看一个例子。
假设一个哈希表中已经插入了两个 Key，key1 和 key2。其中 Hash(key1) = 1, Hash(key2) = 2。这时，如果我们要插入一个 Hash 值为 1 的 key3。根据线性探查的插入逻辑，通过 3 步，我们就可以将 key3 插入到哈希表下标为 3 的位置中。插入的过程如下：
在查找 key3 的时候，因为 Hash（key3）= 1，我们会从哈希表下标为 1 的位置开始顺序查找，经过 3 步找到 key3，查询结束。
讲到这里，你可能已经发现了一个问题：当我们插入一个 Key 时，如果哈希表已经比较满了，这个 Key 就会沿着数组一直顺序遍历，直到遇到空位置才会成功插入。查询的时候也一样。但是，顺序遍历的代价是 O(n)，这样的检索性能很差。
更糟糕的是，如果我们在插入 key1 后，先插入 key3 再插入 key2，那 key3 就会抢占 key2 的位置，影响 key2 的插入和查询效率。因此，线性探查会影响哈希表的整体性能，而不只是 Hash 值冲突的 Key。
为了解决这个问题，我们可以使用 二次探查（Quadratic Probing）和 双散列（Double Hash）这两个方法进行优化。下面，我来分别解释一下这两个方法的优化原理。
● 二次探查就是将线性探查的步长从 i 改为 i^2：第一次探查，位置为 Hash(key) + 1^2；第二次探查，位置为 Hash(key) +2^2；第三次探查，位置为 Hash(key) + 3^2，依此类推。
● 双散列就是使用多个 Hash 函数来求下标位置，当第一个 Hash 函数求出来的位置冲突时，启用第二个 Hash 函数，算出第二次探查的位置；如果还冲突，则启用第三个 Hash 函数，算出第三次探查的位置，依此类推。
无论是二次探查还是双散列，核心思路其实都是在 发生冲突的情况下，将下个位置尽可能地岔开，让数据尽可能地 随机分散存储，来降低对不相干 Key 的干扰，从而提高整体的检索效率。
但是，对于开放寻址法来说，无论使用什么优化方案，随着插入的元素越多、哈希表越满，插入和检索的性能也就下降得越厉害。在极端情况下，当哈希表被写满的时候，为了保证能插入新元素，我们只能重新生成一个更大的哈希表，将旧哈希表中的所有数据重新 Hash 一次写入新的哈希表，也就是 Re-Hash，这样会造成非常大的额外开销。因此，在数据动态变化的场景下，使用开放寻址法并不是最合适的方案。
如何利用链表法解决 Hash 冲突？
相比开放寻址法，还有一种更常见的冲突解决方案，链表法。所谓 链表法，就是在数组中不存储一个具体元素，而是存储一个链表头。如果一个 Key 经过 Hash 函数计算，得到了对应的数组下标，那么我们就将它加入该位置所存的链表的尾部。
这样做的好处是，如果 key3 和 key1 发生了冲突，那么 key3 会通过链表的方式链接在 key1 的后面，而不是去占据 key2 的位置。这样当 key2 插入时，就不会有冲突了。最终效果如下图。
