解决hash冲突的常用方法


开放地址法

1.线性探查法

从发生冲突的单元起,依次判断下一个单元是否为空,当达到最后一个单元时,再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止。

2.平方探查法

平方探查法即是发生冲突时,用发生冲突的单元d[i], 加上 1²、 2²等。即d[i] + 1²,d[i] + 2², d[i] + 3²…直到找到空闲单元。在实际操作中,平方探查法不能探查到全部剩余的单元。

3.双散列函数探查法

该方法是开放地址法中最好的方法之一,它的探查序列是:
hi=(h(key)+ih1(key))%m 0≤i≤m-1 //即di=ih1(key)
即探查序列为:
d=h(key),(d+h1(key))%m,(d+2h1(key))%m,…,等。
该方法使用了两个散列函数h(key)和h1(key),故称为双散列函数探查法。


拉链法

将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m,则可将散列表定义为一个由m个头指针组成的指针数组T[0…m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中,装填因子α可以大于1,但一般均取α≤1。


再哈希法

就是同时构造多个不同的哈希函数:
Hi = RHi(key) i= 1,2,3 … k;
当H1 = RH1(key) 发生冲突时,再用H2 = RH2(key) 进行计算,直到冲突不再产生,这种方法不易产生聚集,但是增加了计算时间。


建立公共溢出区

将哈希表分为公共表和溢出表,当溢出发生时,将所有溢出数据统一放到溢出区。



版权声明:本文为J0Han原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。