⒈ hash 碰撞

  hash 函数接受任意的输入，然后产生一个独一无二的固定长度的值作为输出。现实中，输入可以有无限种可能，但 hash table 的长度是有限的，所以难免不同的输入产生相同的输出，这就产生了 hash 碰撞。

   无论 hash table 有多大，hash 冲突都很容易出现。典型的例子是生日悖论， 23 个人中两个人生日相同的概率高达 50%。

   所谓拉链法，即实际发生碰撞的值存储在一个链表中，值的插入、查找、删除都在链表中进行，而 hash table 的每个 slot 中只记录指向该链表的头指针。

   例如，要将序列 50, 700, 76, 85, 92, 73, 101 存入 hash table，hash table 长度为 7，hash 函数为 key % 7。在操作过程中，50、85、92 会产生碰撞；73、101 会产生碰撞。最后产生的 hash table 示意图如下：

   所有值都存储在 hash table 中，这样就要求 hash table 的长度必须大于等于值的数量。

   以 hash 函数的输出作为起始位置，依次向后查找，直到找到一个空的 slot，然后将值插入。

   以下为伪代码，其中 x 为输入值，hash(x) 即为查找开始位置，S 为 hash table 的 size。

   仍以序列 50, 700, 76, 85, 92, 73, 101 为例，以下为示意图：

   线性探查法由于在发生碰撞时值会连续存储，所以有很高的缓存性能；但正是由于值的连续存储，造成集群现象，导致查找和插入比较耗时。

   以 hash 函数的输出作为起始位置，以偏移量的二次方向后查找，直到找到一个空的 slot，然后将值插入。

   仍以 x 为输入值，hash(x) 作为查找起始位置，S 为 hash table 的长度。以下为伪代码：

   二次探查法在发生碰撞时，值的连续性不如线性探查法，所以缓存性能也不如线性探查法，但也不会像线性探查法那样出现集群现象，所以查找和插入不会像线性探查法那样耗时。

   以 hash 函数的输出作为起始位置，如果该位置对应的 slot 不为空，则对输入再次进行 hash。

   仍以 x 为输入值，hash(x) 作为查找起始位置，S 为 hash table 的长度。hash2 为再 hash 函数，以下为伪代码：

   再 hash 法的值存储的连续行最差，所以缓存性能也最差。同时，由于需要进行两次 hash ，增加了计算量。但再 hash 不会出现集群现象。