解决哈希冲突的一般方法

什么是哈希冲突

简单来说, 假设一个哈希函数是: \(y=x \ mod \ 5\), 那么又两个键 1987 和 2 得到的结果都是 2, 则称为 哈希冲突, 其与 哈希函数 有关

冲突的解决

线性试探法

线性试探法属于 开放定址法 的一种, 除此之外, 开放定址法还包括 二元探测法, 双重嘻哈希发等. 当插入键 key 时候, 如果发现桶单元 bucket[hash(key)] 已经被占用, 则向下线性寻找, 直到找到可以使用的空桶. 故而经过第 i 次试探后, 桶单元为:

$$ bucket[(hash(key)+i) \ mod \ M], \ i = 1, 2, 3, \cdots $$

当 查找到某个 key 时, 首先通过哈希函数计算出桶的位置, 然后比较该桶中保存的值是否为该 key, 如果不是, 则继续向下寻找, 如果查到末尾, 则会从头开始查找

而删除某个 key 时, 为了避免查找过程中出现信息丢失, 则会将删除位置标记为 deleted, 这样, 当进行线性查找时, 遇到 deleted 会继续向下查找而不会中断

链地址法

解决冲突的另一种办法是将桶内产生冲突的 key 串成一个链表

再哈希法

再哈希法比较典型的应用是双重哈希法, 即发生冲突时, 通过使用另一个哈希函数来避免冲突, 在构造另一个哈希函数的时候, 需要具备一些约束条件才能避免再次冲突

双重哈希法中存在的问题有

1. 与线性试探法比, 双重哈希法会消耗较多的时间
2. 在双重哈希法中, 删除会使问题变得复杂, 如果逻辑删除数量太多, 则应重新构建哈希表

公共溢出区法

公共溢出区法就是建立另一个哈希表 dict_overflow 作为公共溢出区, 当发生冲突时, 则将该 key 保存在该 哈希表中