例:改进线性探查 2.二次探查 例如,C=2,要插入关键码k1和 ■探查序列依次为:12,-12, k2,h(k1)=3,h(k2)=5 22,…,即探查地址是 探查序列 d-=(d+i2)%M k的探查序列是3、5、7、9、 d2=(d-i)%M k2的探查序列就是5、7、9 ■用于简单线性探查的探查函数是 k1和k2的探查序列还是纠缠在 p(K2-1)=i 起,从而导致了聚集 p(K,2)=-i* 叔新有,盘 张 例:二次探查 3.伪随机数序列探査 ■例:使用一个大小M=13的表 ■探查函数 假定对于关键码k1和k2,h(x1)=3,h(k2) ■探查序列 p( K, i)=permi -1 k1的探查序列是3、4、2、7、 这里perm是一个长度为M-1的数组 kz2的探查序列是2、3、1、6、… 包含值从1到M-1的随机序列 尽管k2会把k的基位置作为第2个选择来 后就立即分开了 订恤 张铭趣 张帖 产生n个数的仍随机排列 例:伪随机数序列探查 例:考虑一个大小为M=13的表,per[0]= 2,perm[1]=3,perm[2]=7 void permute int *array, int nt 假定两个关键码k1和k2,hk1)=4,hk2)=2 for (int i = 1; i<=n;i++) ■探查序列 swap(array [i-1l array [RandomEd; ak的探查序列是4、6、7、11、 kx2的探查序列是2、4、5、9、 尽管k2会把k的基位置作为第2个选择来 探查,但是这两个关键码的探查序列此 后就立即分开了 学恤息 权新有,种 张帖兽 回16 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 91 例：改进线性探查 „ 例如，c = 2，要插入关键码k1和 k2，h(k1) = 3，h(k2) = 5 „ 探查序列 „ k1的探查序列是3、5、7、9、... „ k2的探查序列就是5、7、9、... „ k1和k2的探查序列还是纠缠在一 起，从而导致了聚集 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 92 2. 二次探查 „ 探查序列依次为：12，-12，22 ，- 22，...，即探查地址是 d2i-1 = (d +i2) % M d2i = (d – i 2) % M „ 用于简单线性探查的探查函数是 p(K，2i-1) = i*i p(K，2i) = - i*i 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 93 例：二次探查 „ 例：使用一个大小M = 13的表 假定对于关键码k1和k2，h(k1)=3，h(k2)=2 „ 探查序列 „ k1的探查序列是3、4、2、7 、... „ k2的探查序列是2、3、1、6 、... „ 尽管k2会把k1的基位置作为第2个选择来 探查，但是这两个关键码的探查序列此 后就立即分开了 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 94 3. 伪随机数序列探查 „ 探查函数 p(K，i) = perm[i - 1] „ 这里perm是一个长度为M - 1的数组 „ 包含值从1到M - 1的随机序列 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 95 产生n个数的伪随机排列 „ void permute(int *array, int n) { for (int i = 1; i <= n; i ++) swap(array[i-1], array[Random(i)]); } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 96 例：伪随机数序列探查 „ 例：考虑一个大小为M = 13的表，perm[0] = 2，perm[1] = 3，perm[2] = 7。 „ 假定两个关键码k1和k2，h(k1)=4，h(k2)=2 „ 探查序列 „ k1的探查序列是4、6、7、11 、... „ k2的探查序列是2、4、5、9 、... „ 尽管k2会把k1的基位置作为第2个选择来 探查，但是这两个关键码的探查序列此 后就立即分开了