位序382456172369107225938267892739623334924676690812779246389238221603992224哈希地址的集合为{2，75，28，34，16，38，62，20)11/62
位序 1 2 3 4 5 6 7 8 9 2 3 1 7 6 0 2 9 2 3 2 6 8 7 5 9 2 7 3 9 6 2 8 9 2 3 4 3 6 3 4 9 2 7 0 6 8 1 6 9 2 7 7 4 6 3 8 9 2 3 8 1 2 6 2 9 2 3 9 4 2 2 0 哈希地址的集合为{2，75，28，34，16，38，62，20} 11/62
哈希冲突解决方法9.4.3在哈希表中，虽然冲突很难避免，但发生冲突的可能性却有大有小。这主要与三个因素有关：与装填因子有关。所谓装填因子α是指哈希表中已存入的元素数n与哈希地址空间大小m的比值，即α=n/m。α越小，冲突的可能性就越小；但α越小，存储空间的利用率就越低。与所采用的哈希函数有关。与解决冲突的哈希冲突函数有关12/62
在哈希表中，虽然冲突很难避免，但发生冲突的可能性却有大有小。 这主要与三个因素有关： 与装填因子有关。所谓装填因子α是指哈希表中已存入的元素数n与 哈希地址空间大小m的比值，即α=n/m。α越小，冲突的可能性就越 小； 但α越小，存储空间的利用率就越低。 与所采用的哈希函数有关。 与解决冲突的哈希冲突函数有关。 12/62
解决哈希冲突方法有许多，可分为开放定址法和拉链法两大类。1：开放定址法发生冲突时查找周围一个空位置存放记录。设置一个查找周围一个空位置的函数。13/62
解决哈希冲突方法有许多，可分为开放定址法和拉链法两大类。 1. 开放定址法 发生冲突时查找周围一个空位置存放记录。 设置一个查找周围一个空位置的函数。 13/62
(1)线性探测法从发生冲突的地址（设为d）开始，依次循环探测d的下一个地址（当到达下标为m-1的哈希表表尾时，下一个探测的地址是表首地址0），直到找到一个空闲单元为止。描述公式为：(1≤i≤m-1)de=h(k), d,=(di-i+1) mod m8951814/62
从发生冲突的地址（设为d）开始，依次循环探测d的下一个地址（当到 达下标为m-1的哈希表表尾时，下一个探测的地址是表首地址0），直 到找到一个空闲单元为止。 描述公式为： d0=h(k)，di=(di-1+1) mod m (1≤i≤m-1) 0 1 2 3 4 5 6 7 8 9 * * * * * * * * 14/62
问题：可能出现堆积现象：n=6,m=10,关键字为（10,11,12,19,20,21）哈希函数：h(key) = key % 910, 11, 12123456780C10111219h（19)=19%9=1（冲突）dg=1，di=(1+1)%10=2（冲突）d2=(2+1)%10=3（冲突）d3=（3+1)%10=4（将19放在4位置）21345670891011121920h（20）=20%9=2（冲突）哈希函数值不相同的多个记dg=2，di=(2+1)%10=3（冲突）录争夺同一个后继哈希地址d2=(3+1)%10=4（冲突)称为非同义词冲突d3=（4+1)%10=5（将20放在5位置）15/62
问题：可能出现堆积现象： 0 1 2 3 4 5 6 7 8 9 10 11 12 n=6,m=10,关键字为（10,11,12,19,20,21） 哈希函数：h(key) = key % 9 10，11，12 19 h(19)=19%9=1（冲突） d0=1，d1=(1+1)%10=2 （冲突） d2=(2+1)%10=3 （冲突） d3=(3+1)%10=4（将19放在4位置） 0 1 2 3 4 5 6 7 8 9 10 11 12 19 20 h(20)=20%9=2（冲突） d0=2，d1=(2+1)%10=3 （冲突） d2=(3+1)%10=4 （冲突） d3=(4+1)%10=5（将20放在5位置） 哈希函数值不相同的多个记 录争夺同一个后继哈希地址 称为非同义词冲突 15/62