散列表 ~

常用 Hash 函数的构造方法

• 直接定址法
• 数字分析法
• 平方取中法
• 除留余数法

常用的 Hash 冲突处理方法

• 开放定址法
  1）线性探查法
  2）平方探查法
• 链地址法

eg：用关键字序列{1，9，12，11，25，35，17，29}创建一个Hash表,装填因子a为1/2，试确定表长m,采用除留余数法构造 Hash函数，采用链地址法来处理冲突，并计算查找成功与不成功时的平均查找长度 ASL，和ASL2（只将与关键字的比较计算在内)。

装填因子 = 表中记录数 / 散链表长度
则：表长 m = 16

除留余数法的Hash函数构造公式为H(key)=key Mod p ，其中p为不大于表长的最大素数
则：H(key)=key Mod 13

由此所得 Hash 表如图
查找成功的平均查找长度 ASL
ASL₁=(1+1+1+1+2+1+1+2) / 8=1.25

查找不成功的平均查找长度 ASL
ASL₂=(0+1+0+1+1+0+0+0+0+2+0+1+2) / 13=0.62