散列表
Content 散列技术简介1
常见散列函数2
冲突处理技术3
PART THREE
D 双散列法利用两个散列函数，改善“二次聚集”现象
具备两个散列函数h
1和h
2
，探查序列为：
h1(key), (h1(key)+ h2(key))%M, (h1(key)+ 2h2(key))%M, …,
(h1(key)+ i*h2(key))%M,…
h2的作用：
•对h1散列值产生一个固定增量，实现跳跃式探查
•改善“二次聚集”，对两个散列函数都为同义词的关键字很少
具备两个散列函数h
1和h
2
，探查序列为：
h1(key), (h1(key)+ h2(key))%M, (h1(key)+ 2h2(key))%M, …,
(h1(key)+ i*h2(key))%M,…
h2(key)应该是小于M且与M互质的整数，以保证探测序列能够最多经过M次探测（i=0, 1, …, M-1）即可遍历表中所有地址
若M为素数，则可取h
2
(key)=key % (M-2)+1
(h 1(key)+ i*h 2(key))%M, i =0, 1, …, M -101234567891024801565插入58h 1(key)=58%11=3
h 2(key)=58％9＋1＝5
(h 1(key)＋h 2(key))％11=(3＋5)%11=8
58h 1(key) = key % 11 h 2(key) = key % 9 + 1
(h 1(key)+ i*h 2(key))%M, i =0, 1, …, M -101234567891024801565
插入35h 1(key)=35%11=2
h 2(key)=35％9＋1＝9(h 1(key)＋h 2(key))％11=(2＋9)%11=0
58h 1(key) = key % 11 h 2(key) = key % 9 + 1
35
常见错误
⚫将h
2散列值列入探查序列
(h1(key)+ i*h2(key))%M, i=0, 1, …, M-1
END。