Hash的构造方法

1.直接定址法

2.数字分析法：适用于关键字位数比较多且表中可能的关键字都是已知的情况，如一些连续的电话号码，分析数字的特点

3.平方取中法：123的平方为15129，取其中的三位512

4.除留余数法：H(key)=key mod p (p<=len)

冲突处理

开放定址，线性探测（特点：可以探测到表中的任何位置；容易产生堆积问题）

$$红色位为冲突位置，根据彩虹的颜色分布，为依次扫描的六个位置，如果碰到没有关键字的位置，则填充$$

开放定址，平方探测d+i^2 , d-i^2（特点：不可以探测到表中的任何位置；不容易产生堆积问题(一错再错)）

链地址法

◆ 用关键字序列{1、9、12、11、25、35、17、29}创建一个Hash 表，装填因子a为1/2，试确定表长len,采用除留余数法构造 Hash函数，采用链地址法来处理冲突。 n/length 装填因子就是表的装填的个数比例,所以表长为16，H(key)=key mod p，p可以为13

---

计算查找成功时和失败时的，平均查找长度

查找失败，就是查找一个不存在的数的“比较”次数，所以要“遍历”(对于数组就是n,散列表的就是散列表的长))

$$查找成功的平均查找长度AS{L}_{成功}$$

$$查找失败的平均查找长度AS{L}_{失败}$$

顺序查找

$$\begin{gathered} AS{L}_{成功}(顺序查找)=\frac{n+1}{2} \\ AS{L}_{失败}(顺序查找)=n \end{gathered}$$

hash线性探测

$$\begin{gathered} AS{L}_{成功}(线性探测)=\frac{1+1+3(依次比较次数)}{3(关键字个数)} \\ AS{L}_{失败}(线性探测)=\frac{3+2+1}{3(探测可能的入口的个数)}=2 \end{gathered}$$

hash连地址法

以上图为例： $$\begin{gathered} AS{L}_{成功}(连地址法)=\frac{3\ast 1+1\ast 2(依次比较次数)}{4(关键字个数)} \\ AS{L}_{失败}(连地址法)=\frac{4(关键字个数（依次比较）)}{7(探测可能的入口的个数，散列表的长)} \end{gathered}$$

二叉排序树

$$树的计算方法一样$$

$$\begin{gathered} AS{L}_{成功}(二叉排序树)=\frac{1\ast 1+2\ast 2+3\ast 3(依次比较次数)}{6(关键字个数)} \\ AS{L}_{失败}(二叉排序树)=\frac{2\ast 1+6\ast 3(查找底部不存在的数字)}{7空指针个数} \end{gathered}$$

折半查找及判定树

$$\begin{gathered} AS{L}_{成功}(折半查找)=\frac{1\ast 1+2\ast 2+3\ast 2}{5} \\ AS{L}_{失败}(折半查找)=\frac{2\ast 2+2\ast 3}{4} \end{gathered}$$ 树的平均查找长度为树的深度