二级聚集 4.双散列探查法 能消除基本聚集 避免二级聚集 不同的关键码,其探查序列的某些段 探查序列是原来关键码值的函数 而不仅仅是基位置的函数 伪随机探查和二次探查可以消除 ■二级聚集( secondary clustering 每到两箨翁蛋列到产全操还是 双散列探查法 利用第二个散列函数作为常数 聚契接喜度国最基地址的函数,而不是原 每次跳过常数项,做线性探查 例子:伪随机探查和二次探查 叔新有,盘 张 4双散列探查法的基本思想4明确两个公式概念 双散列探查法使用两个散列函数h1和h2 ■双散列函数探查法序列公式 萄类到的装生浮为:则再计 di (d+i h2(key))%/ M (d+h,(key)) (d+22(key))%/oM 双散列函数公式: (d+3h,(key))%o M P(K, i=i*h2(key) 订恤 张铭趣 T恤息@ 积新有,究 双散列函数法特征 M和h2(k选择方法 ah2(key)尽量与M互素 查女秀1高"起回的值在 ■使发生冲突的同义词地址均匀地分布 法2:设量M=2m,让h2返回一个1到2吃之 在整个表中 ■否则可能造成同义词地址的循环计算 方法3:若M是素数,h1(KO= K mod m h ,(k)=Kmod(M-2)+1 双散列的优点:不易产生“聚集 或者h2(K=[K/M]mod(M-2)+1 ■缺点:计算量增大 蹇导数0= mod p, h2(K)= K mod q+1(q是小于p的最大素数)17 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 97 二级聚集 „ 能消除基本聚集 „ 基地址不同的关键码，其探查序列的某些段 重叠在一起 „ 伪随机探查和二次探查可以消除 „ 二级聚集( secondary clustering ) „ 如果两个关键码散列到同一个基地址，还是 得到同样的探查序列，所产生的聚集 „ 原因探查序列只是基地址的函数，而不是原 来关键码值的函数 „ 例子：伪随机探查和二次探查 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 98 4. 双散列探查法 „ 避免二级聚集 „ 探查序列是原来关键码值的函数 „ 而不仅仅是基位置的函数 „ 双散列探查法 „ 利用第二个散列函数作为常数 „ 每次跳过常数项，做线性探查 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 99 双散列探查法的基本思想 „ 双散列探查法使用两个散列函数h1和h2 „ 若在地址h1(key)=d发生冲突，则再计 算h2(key)，得到的探查序列为： (d+h2(key)) % M， (d+2h2 (key)) %M ， (d+3h2 (key)) % M ， ... 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 100 明确两个公式概念 „ 双散列函数探查法序列公式： di =(d + i h2 (key)) % M „ 双散列函数公式： p(K, i) = i * h2 (key) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 101 双散列函数法特征 „ h2 (key) 尽量与M互素 „ 使发生冲突的同义词地址均匀地分布 在整个表中 „ 否则可能造成同义词地址的循环计算 „ 双散列的优点: 不易产生“聚集” „ 缺点：计算量增大 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 102 M和h2(k)选择方法 „ 方法1：选择M为一个素数，h2返回的值在 1≤h2(K)≤M – 1范围之间 „ 方法2：设置M = 2m，让h2返回一个1到2m之 间的奇数值 „ 方法3：若M是素数，h1(K)=K mod M „ h2 (K) = K mod(M-2) + 1 „ 或者h2(K) = [K / M] mod(M-2) + 1 „ 方法4：若M是任意数，h1(K)=K mod p，(p 是小于M的最大素数) „ h2 (K) = K mod q + 1 (q是小于p的最大素数)