Hash算法解决冲突的方法总结

  • Hash算法解决冲突的方法总结已关闭评论
  • 2 views
  • A+
所属分类:编程开发

Hash算法解决冲突的方法一般有以下几种常用的解决方法

1, 开放定址法:

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

公式为:fi(key) = (f(key)+di) MOD m (di=1,2,3,……,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}时,都是没有冲突的散列地址,直接存入:

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

于是我们应用上面的公式f(37) = (f(37)+1) mod 12 = 2。于是将37存入下标为2的位置:

Hash算法解决冲突的方法总结

(1)线性探查法(Linear Probing)

该方法的基本思想是:

将散列表T[0..m-1]看成是一个循环向量,若初始探查的地址为d(即h(key)=d),则最长的探查序列为:

d,d+l,d+2,…,m-1,0,1,…,d-1

即:探查时从地址d开始,首先探查T[d],然后依次探查T[d+1],…,直到T[m-1],此后又循环到T[0],T[1],…,直到探查到T[d-1]为止。

探查过程终止于三种情况:

(1)若当前探查的单元为空,则表示查找失败(若是插入则将key写入其中);

(2)若当前探查的单元中含有key,则查找成功,但对于插入意味着失败;

(3)若探查到T[d-1]时仍未发现空单元也未找到key,则无论是查找还是插入均意味着失败(此时表满)。

利用开放地址法的一般形式,线性探查法的探查序列为:

hi=(h(key)+i)%m 0≤i≤m-1 //即di=i

用线性探测法处理冲突,思路清晰,算法简单,但存在下列缺点:

① 处理溢出需另编程序。一般可另外设立一个溢出表,专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表,查找方法可用顺序查找。

② 按上述算法建立起来的哈希表,删除工作非常困难。假如要从哈希表 HT 中删除一个记录,按理应将这个记录所在位置置为空,但我们不能这样做,而只能标上已被删除的标记,否则,将会影响以后的查找。

③ 线性探测法很容易产生堆聚现象。所谓堆聚现象,就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突,如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ,则当新的记录加入该表时,与这个序列发生冲突的可能性愈大。因此,哈希地址的较长连续序列比较短连续序列生长得快,这就意味着,一旦出现堆聚 ( 伴随着冲突 ) ,就将引起进一步的堆聚。

(2)线性补偿探测法

线性补偿探测法的基本思想是:

将线性探测的步长从 1 改为 Q ,即将上述算法中的 j = (j + 1) % m 改为: j = (j + Q) % m ,而且要求 Q 与 m 是互质的,以便能探测到哈希表中的所有单元。

【例】 PDP-11 小型计算机中的汇编程序所用的符合表,就采用此方法来解决冲突,所用表长 m = 1321 ,选用 Q = 25 。

(3)随机探测

随机探测的基本思想是:

将线性探测的步长从常数改为随机数,即令: j = (j + RN) % m ,其中 RN 是一个随机数。在实际程序中应预先用随机数发生器产生一个随机序列,将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次序,从而可以避 免或减少堆聚。基于与线性探测法相同的理由,在线性补偿探测法和随机探测法中,删除一个记录后也要打上删除标记。

2, 再哈希法:

再哈希法又叫双哈希法,有多个不同的Hash函数,当发生冲突时,使用第二个,第三个,….,等哈希函数

计算地址,直到无冲突。虽然不易发生聚集,但是增加了计算时间。

3, 链地址法:

链地址法的基本思想是:每个哈希表节点都有一个next指针,多个哈希表节点可以用next指针构成一个单向链表,被分配到同一个索引上的多个节点可以用这个单向

链表连接起来,如:

键值对k2, v2与键值对k1, v1通过计算后的索引值都为2,这时及产生冲突,但是可以通道next指针将k2, k1所在的节点连接起来,这样就解决了哈希的冲突问题

4, 建立公共溢出区:

这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表

  • 我的微信
  • 微信扫一扫
  • weinxin
  • 微信公众号
  • 微信公众号扫一扫
  • weinxin
avatar