通过构造良好的哈希函数可以减少冲突,但一般不能完全避免冲突。因此解决冲突是哈希法的另一个关键问题。常用的解决冲突方法有以下四种。
- 开放地址法
这种方法也称再散列法,基本思想是当关键字key的哈希地址p = H(key)冲突时,以p为基础再产生一个新的哈希地址p1,p1再冲突时,再以p为基础,产生地址p2……知道产生一个不冲突的地址pi,再将key填入其中,这种方法都有一个通用的再散列表达式
Hi = (H(key)+ di)%m
其中H(key)是哈希函数,m为表长,di是增量序列,增量的取值方式不同,相应的再散列方式也不相同,主要有以下三种。
(1)线性探测再散列
i = 1,2,3,4……..m-1.
采用这种方法冲突发生时,查看下一单元,直到找到一个空的单元,或者遍历全表。
(2)二次探测再散列
m = 1^2,-1^2 ,2^2,-2^2……k^2,-k^2.(k < m/2).
采用这种方法冲突发生时在表的左右进行探测比较灵活。
(3)伪随机探测再散列
i = 伪随机数序列
具体实现时需要建立一个伪随机数生成器,并给定一个随机数做为起点。
例题:
已知哈希表长度m=11,哈希函数为:H(key)= key % 11,则H(47)=3,H(26)=4,H(60)=5,假设下一个关键字为69,H(69)= 3冲突,采用线性探测在散列(见下图a),i = (3 + 1)%11 = 4冲突,i = (3 + 2)%11 = 5冲突,i = (3 + 3)%11 = 6不冲突,所以H(69)=6。采用二次探测再散列(见下图b),i = (3 + 1^2)%11 = 4 冲突,i = (3 - 1^2)%11 = 2不冲突所以H(69) = 2。采用伪随机法探测再散列。假设伪随机序列为2,5,9,….,则下一个哈希地址为i = (3 + 2)%11 = 5冲突,继续寻找下一个i = (3 + 5)%11 = 8不冲突,所以将69填入8号单元。
总结:
由上述例子可以看出线性探测再散列法容易产生“二次聚集”即再处理同义词的冲突时又造成非同义词的冲突,但是它的优点是只要哈希表不满,都可以找到不冲突的地址,但是二次探测再散列和伪随机数探测再散列法则不一定。
- 再哈希法
再哈希法是同时构造多个不同的哈希函数
Hi = RHi(key)i=1,2,3,4,5,….,k
如果RH1(key)冲突,就采用RH2(key),直到不在产生冲突为止,这种方法不易产生聚集,但是增加量计算时间。 - 拉链法
这种方法的基本思想是,将所有哈希地址为i的元素构成一个同义词链的单链表。将单链表的头指针存放在单链表的第i个单元中。
例:
已知一组关键字(32,40,36,53,16,46,71,27,42,24,49,64),哈希表长度为13,哈希函数为:H(key)= key % 13,则用链地址法处理冲突的结果如图d所示。
- 建立公共溢出区
这种方法的思想是哈希表分为基本表和溢出表。和基本表冲突的元素都填入溢出表。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)