hash冲突解决方法总结

hash冲突解决方法总结

我们知道在两个不相等的 key 通过hash函数获得相同的 hash值, 这个时候我们就要结局 hash表中的 hash冲突.

开放定址法

开放定址法就是一旦发生了冲突, 就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入.

线性探测法

公式为:

fi(key) = (f(key) + di) MOD m (di=1,2,3,4,......,m-1)

用开放地址法解决冲突的做法是: 当冲突.发生时,使用某种探测技术在散列表中形成一个探测序列. 沿着这个序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址(即地址单元为空)为止(若要插入,在探查到开放的地址,这可将待插入的新节点存入该地址单元).查找时探测开放地址则表明无代查关键字,即查找失败.

比如说, 我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34},表长为12. 我们用散列函数f(key) = key mod l2.

当计算前S个数{12,67,56,16,25}时, 都是没有冲突的散列地址, 直接存入:

示例1

计算key = 37时, 发现f(37) = 1, 此时就与25所在的位置冲突.

于是我们应用上面的公式f(37) = (f(37)+1) mod 12 = 2. 于是将37存入下标为2的位置. 这其实就是房子被人买了于是买下一间的作法

示例2

接下来22,29,15,47都没有冲突, 正常的存入

示例3

到了 key=48, 我们计算得到f(48) = 0, 与12所在的0位置冲突了, 不要紧, 我们f(48) = (f(48)+1) mod 12 = 1, 此时又与25所在的位置冲突. 于是f(48) = (f(48)+2) mod 12=2, 还是冲突……一直到 f(48) = (f(48)+6) mod 12 = 6时, 才有空位, 机不可失, 赶快存入

示例4

我们把这种解决冲突的开放定址法称为线性探测法.

从这个例子我们也看到, 我们在解决冲突的时候, 还会碰到如48和37这种本来都不是同义词却需要争夺一个地址的情况, 我们称这种现象为堆积. 很显然, 堆积的出现, 使得我们需要不断处理冲突, 无论是存入还是査找效率都会大大降低.

二次探测法

这里所谓的二次探测也叫做二次方探测,公式为

fi(key) = (f(key) + di^2) MOD m (di=1,2,3,4,......)

随机探测法

公式:

fi(key) = (f(key) + random_num) MOD m

双散列


(hash1(key)+ i * hash2(key))%TABLE_SIZE i=1,2,3,4,5,6,7,...
这里hash1()和hash2()是哈希函数,TABLE_SIZE 是哈希表的大小.

第一个哈希函数通常是

hash1(key)= key%TABLE_SIZE

一般的第二个哈希函数是:

hash2(key) = PRIME – (key % PRIME)

双散列

再散列

hash_i = hash_i(key) , i =1,2,3,4,5,6...,k hash_i是一些散列函数。即在上次散列计算发生冲突时,利用该次冲突的散列函数地址产生新的散列函数地址,直到冲突不再发生。这种方法不易产生“聚集”(Cluster),但增加了计算时间。

单独链表法

将散列到同一个存储位置的所有元素保存在一个链表中。实现时,一种策略是散列表同一位置的所有冲突结果都是用栈存放的,新元素被插入到表的前端还是后端完全取决于怎样方便。

建立一个公共溢出区

发表评论