哈希表（散列表）

冲突：对不同的关键字可能得到同一哈希地址，即key1≠key2面f（key1）=f（key2）这种现象称冲突（collision）。具有相同函数值的关键词对该哈希函数来说称作同义词（synonym）。

（1）除留余数法(K%P P一般情况下取小于表长的最大素数 表长是100则p取97 若表长是25则p取23)
（2）数字分析法
（3）平方取中法
（4）直接定址法

（1）开放定址法（1.线性探测法 +1 +2 +3… 2.二次探测法 +12 -12 +22 -22）

(2) 再哈希法（增加了不算的时间 不容易产生聚集现象）
(3)
设散列表的地址区间为0-17,散列函数为H(K)=K mod 17 (k%17)。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。为采用线性探测法处理冲突，请画出它们对应的哈希表？求平均查找长度?
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
18 72 38 59 25 26 8

H(26)=26%17=9
H(25)=25%17=8

H(72)=72%17=4

H(38)=38%17=4 (冲突)
H(38)=(38+1)%17=5

H(8)=8%17=8(冲突)
H(8)=(8+1)%17=9(冲突)
H(8)=(8+2)%17=10

H(18)=18%17=1

H(59)=59%11=4(冲突)
H(59)=(59+1)%11=5(冲突)
H(59)=(59+2)%11=6(冲突)

平均查找长度=（1+1+1+2+3+1+3）/7=12/7

设散列表的地址区间为0-17,散列函数为H(K)=K mod 17 (k%17)。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。为采用二次探测法处理冲突，请画出它们对应的哈希表？求平均查找长度?

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
18 72 38 8 25 26 1 59

H(26)=26%17=9

H(25)=25%17=8

H(72)=72%17=4

H(38)=38%17=4 （冲突）
H(38)=(38+12)=39%17=5

H(8)=8%17=8(冲突)
H(8)=(8+12)=9%17=9（冲突）
H(8)=(8-12)=7%17=7

H(18)=18%17=1

H(59)=59%17=8（冲突）
H(59)=(59+12)=60%17=9（冲突）
H(59)=(59-12)=58%17=7（冲突)
H(59)=(59+22)=63%17=12

ASL 平均查找长度=（1+1+1+2+3+1+4）/7=13/7

装填因子：反映哈希表的装满程度 <=1
= 表中装入的记录数/哈希表的总长度
= 1 – 表中未装入的记录数/哈希表的总长度

1 哈希函数
2 处理冲突方法
3装填因子

装填因子的值越大 发生冲突的可能性越大
装填因子的值越小 发生冲突的可能性越小
注意：冲突只能减小 不可以避免

列表 哈希表 哈希