哈希冲突解决方法学习笔记

链地址法

链地址法也叫做拉链法，它的基本思想是，将哈希表中的每个槽位都指向一个链表，当发生哈希冲突时，将数据插入到链表中。

很好理解，如图所示：

开放定址法是一种解决哈希冲突的方法，它的基本思想是，当发生哈希冲突时，不是将数据直接插入到哈希表中，而是寻找哈希表中的空槽位，将数据插入到空槽位中。

线性探测采用固定步长的线性搜索来进行探测。

注意，我们不能在开放寻址哈希表中直接删除元素。因为删除元素会在数组内产生一个空桶 None ，当查询元素时，线性探测到该空桶就会返回，因此在该空桶之下的元素都无法再被访问到，程序可能误判这些元素不存在。

为了解决该问题，我们可以采用懒删除（ lazy deletion ）机制，不直接从哈希表中移除元素，而是利用一个常量 TOMBSTONE 来标记这个桶。

None 和 TOMBSTONE 都代表空桶，都可以放置键值对。线性探测到 TOMBSTONE 时应该继续遍历，因为其之下可能还存在键值对。在线性探测中记录遇到的首个 TOMBSTONE 的索引，并将搜索到的目标元素与该 TOMBSTONE 交换位置，这样可以优化效率。

线性探测容易产生 聚集现象，为了缓解这个问题，就有了平方探测和双重散列。

平方探测思想与线性探测类似，不同之处在于探测的步长是平方级别的。即当发生哈希冲突时，探测的步长为 1，4，9，...步。

平方探测可以缓解线性探测的聚集现象，但不能彻底解决。

多次哈希的基本思想是，当发生哈希冲突时，尝试其他的哈希函数，直到找到空槽位。

与线性探测相比，多次哈希方法不易产生聚集，但多个哈希函数会带来额外的计算量。

Warning

以上三种方法，线性探测、平方探测和多次哈希哈希表都存在 不能直接删除元素 的问题。