C语言实现一个简易的Hash table(7)

上一章我们讲了如何根据需要动态设置 hash表 的大小，在第四章中，我们使用了 双重哈希 来解决 hash表 的碰撞，其实解决方法有很多，这一章我们来介绍下其他方法。

本章将介绍两种解决 hash表 碰撞的方法：

1. 拉链法
2. 开放地址法

拉链法

使用拉链法，每一个 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表 大小