上一章我们讲了如何根据需要动态设置 hash 表的大小，在第四章中，我们使用了双重哈希来解决 hash 表的碰撞，其实解决方法有很多，这一章我们来介绍下其他方法。
本章将介绍两种解决 hash 表碰撞的方法：
拉链法
开放地址法
拉链法
使用拉链法，每一个 bucket 都会包含一个链接表，当发生碰撞时，就会将该记录插入在该位置的链接表后面，步骤如下：
插入时：通过 hash 函数获取到要插入的位置，如果该位置是空的，就直接插入，如果该位置不是空的，就插入在链接表的后面
搜索时：通过 hash 函数获取到 key 对应的位置，遍历链接表，判断 key 是不是搜索的 key，如果是，则返回 value，否则返回 NULL
删除时：通过 hash 函数获取到 key 对应的位置，遍历链接表，找到需要删除的 key，如果找到，则将该 key 对应的记录从链接表中删除，如果链接表中只有一条记录，则将该位置置为 NULL
拉链法的优点是实现起来简单，但是空间利用率低。每个记录必须存储指向链接表中下一个记录的指针，如果没有记录，则指向 NULL，这种方法会浪费一些空间来存储额外的指针。
开放地址法
开放地址法能解决拉链法空间利用率低的问题，发生碰撞时，碰撞的记录将放置在 hash 表中的其他 bucket 中，存放的位置是根据预先确定的规则选择的，以便在搜索记录时可以重复该规则，有如下几种规则：
线性探查
当发生碰撞时，就会递增索引，将记录插入在下一个可用的索引中，方法如下：
插入时：通过 hash 函数找到插入的位置的索引，如果这个位置是空的，直接插入，如果不为空，就递增索引，直到找到索引指向的位置是空的为止，然后执行插入
搜索时：通过 hash 函数找到搜索的记录的索引，每次递增索引，并比较索引指向的值是否是要搜索的值，如果索引指向的是空，则返回 NULL
删除时：通过 hash 函数找到删除的记录的索引，每次递增索引，直到找到要删除的那个 key 后执行删除
线性探测提供了良好的缓存性能，但是存在碰撞后遍历次数多的问题。将发生碰撞的 key 放入下一个可用的 bucket 中可能导致后面插入记录也要往后插，就需要多次迭代。
二次探查
二次探查法和先行探查类似，不同的是，发生碰撞后，我们会将记录插入在如下的序列中：i, i + 1, i + 4, i + 9, i + 16, …，i 代表通过 hash 函数获取到的索引，具体步骤如下：
插入时：通过 hash 函数找到插入的索引，通过遍历上面的序列直到找到一个空的或已被删除的索引位置，执行插入
搜索时：通过 hash 函数找到 key 的索引，遍历上面的序列，将序列上的 key 与搜索的 key 对比，如果相等，则返回 value，否则返回 NULL
删除时：因为我们无法判断要删除的项是不是碰撞链上的，所以我们不能直接删除该条记录，只能把它标记为已删除
二次探查法减少发生碰撞后遍历的次数，并且仍然提供了不错的缓存性能。
双重 hash
双重 hash 旨在解决碰撞后遍历次数多的问题。使用两次 hash 函数为插入的记录选择新的索引，这个索引会均匀的分布在整个表中，该方法虽然解决了上述问题，但也失去了缓存特性，双重 hash 是实际项目中常见的冲突管理方法，也是我们在本教程中实现的方法。
上一章：设置 hash 表大小