8.4.3 哈希冲突解决方法 (1).pptx

8.4.3哈希冲突解决方法;发生冲突时查找周围一个空位置存放记录。

设置一个查找周围一个空位置的函数。;从发生冲突的地址（设为d）开始，依次循环探测d的下一个地址（当到达下标为m-1的哈希表表尾时，下一个探测的地址是表首地址0），直到找到一个空闲单元为止。

描述公式为：d0=h(k)，di=(di-1+1)modm(1≤i≤m-1);问题：可能出现堆积现象：;发生冲突时前后查找空位置。

描述公式为：d0=h(k)，di=(d0±i2)modm(1≤i≤m-1);平方探测法可以避免出现堆积问题。

缺点是不能探测到哈希表上的所有单元，但至少能探测到一半单元。;【例8.15】假设哈希表长度m=13，采用采用除留余数法加线性探测法建立如下关键字集合的哈希表：

(16,74,60,43,54,90,46,31,29,88,77)。;哈希函数：h(k)=kmod13

解决冲突方法：线性探测法;h(29)=3 有冲突

d0=3，d1=(3+1)%13=4 仍有冲突

d2=(4+1)%13=5 仍有冲突

d3=(5+1)%13=6 ha[6]=29,共4次探测

h(88)=10 ha[10]=88,共1次探测

h(77)=12 有冲突

d0=12，d1=(12+1)%13=0 ha[0]=77，共2次探测;下标;下标;哈希表ha中查找失败的所有情况的探测次数;拉链法是把所有的同义词用单链表链接起来的方法。

在这种方法中，哈希表每个单元中存放的不再是记录本身，而是相应同义词单链表的头指针。

由于单链表中可插入任意多个结点，所以此时装填因子α根据同义词的多少既可以设定为大于1，也可以设定为小于或等于1，通常取α=1。;;解：采用拉链法解决冲突建立的链表如下图所示。;;;【例8.17】将关键字序列(7,8,30,11,18,9,14)散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H(key)=(key×3)mod7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。

（1）请画出所构造的散列表。

（2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。

说明：本题为2010年全国考研题。;解：（1）n=7，α=0.7=n/m，则m=n/0.7=10。

计算各关键字存储地址的过程如下：

H(7)=7×3mod7=0

H(8)=8×3mod7=3

H(30)=30×3mod7=6

H(11)=11×3mod7=5

H(18)=18×3mod7=5 冲突

d1=(5+1)mod10=6 仍冲突

d2=(6+1)mod10=7

H(9)=9×3mod7=6 冲突

d1=(6+1)mod10=7 仍冲突

d2=(7+1)mod10=8

H(14)=14×3mod7=0 冲突

d1=(0+1)mod10=1;构造的哈希表：;不成功的情况下所有探测次数：;平均情况下的平均查找长度：