【哈希表 | 散列表】根据关键字的值来计算出关键字在表中的地址

address = H(key)

【哈希函数|散列函数】函数H(key)，将关键字映射到地址上

举例

构造

【问题举例】
1. 关键字序列为{7, 4, 1, 14, 100, 30, 5, 9, 20, 134}
2. 设Hash函数为H(key)= key Mod 13
3. 试给出表长为15的Hash表

【构造】

1. 根据【Hash函数】求的【地址】
   
2. 按地址，将数据写到一个数组中
   
3. 可以观察到这个数组有【冲突】（不同的key有相同的地址）
   
4. 出现冲突怎么办呢？这里使用一种【冲突处理方法】：当插入一个元素，该位置已经有别的元素时，一步一步往后找，直到找到空位，再填入
   

查找

根据哈希函数–>找到第一个位置的记录–>比较该记录是否和key相等–>不相等，按冲突处理的函数继续找

查找成功的分析

ASL1 = (1+2+1+2+2+1+2+1+2+8)/10=11/5

查找失败的分析

查找不成功的位置是Hash函数【所能映射到的位置】，不是表中的所有位置
【例子】该例子中，0-12才是哈希函数所能映射到的位置，因为len=13

【查找失败】

1. 使用H(key)函数算出映射的地址–>
2. 根据地址查找数值是不是该元素–>
3. 不是，怀疑是不是冲突函数将其位移了–>
4. 按冲突函数位移–>
5. 直到遇到空的位置–>
6. 查找失败

ASL2 = (1+3+2+1+9+8+7+6+5+4+3+2+1)/13 = 4

构造哈希函数

以上例子的构造，涉及到两个东西：

1. 哈希函数：选择一个好的哈希函数，产生的冲突会比较少
2. 冲突处理：选择一种处理冲突的方法

哈希函数

【哈希函数】把key转换为address的一个函数
【选择原则】建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小

数字关键字

方法名	介绍	特点(适用于)	公式或例子	说明
直接定址法	取关键字或关键字的某个线性函数为Hash地址	地址集合的大小=关键字集合的大小	H(key)=key 或者 H(key) = a×key+b	其中：a和b为常数
数字分析法	分析的原则：尽量取冲突较少的位数段	关键字【位数】比较多 表中关键字都是已知的		电话号码后4位的重复几率较少
平方取中	取关键字平方后的中间几位作为Hash地址	放到了数字，产生的冲突较少 关键字中的每一位都有某些数字重复出现频度很高的现象	关键字123，123²=15129，取512做为哈希地址	一个数平方后的中间几位数和数的每一位都相关，由此得到的Hash地址随机性更大
除留余数法	取关键字被某个≤Hash表表长m的数p除后所的余数为Hash地址			一般p≤len的最大素数，p不含20以下的质因子，这样可以减少冲突，
折叠法	将关键字分割成若*分，然后取它们的叠加和为哈希地址	关键字的数字位数特别多	移位叠加 间界叠加
随机数法		用于对长度不等的关键字构造哈希函数	H(key) = Random(key)

非数字关键字

对关键字进行数字化处理

冲突处理方法

【冲突】不同的元素经过哈希函数映射到同一位置上，导致了位置重叠
【冲突处理方法】为产生冲突的地址寻找下一个哈希地址

开放地址法

位置上已经有人了，我就找别的位置

【每次的增量di的取法】

方法	介绍	特点	公式	说明
线性探查法（线性探测再散列）	一次往后走i	可以探测到表中所有位置，但是容易产生【堆积】问题	H(key) = ( H(key)+i ) Mod len，i∈[1,len-1]，len为表长	【堆积问题】原来，A和B经过哈希函数，不会地址冲突，而后来B的位置被A占了，导致了堆积，致使B又要往后移
平方探查法（平方探测再散列）	走的距离d是平方变化的	不可探测到表中所有位置（至少可以探测到一半位置） 不易产生堆积问题	d：发生冲突的地址 新地址为
随机探测再散列（双散列函数探测）	每次探测的距离是一个随机数		di是一组伪随机数列

【增量di应具有“完备性”】

链地址法

将冲突的元素用地址链起来

查找失败的次数

key=A，若H(A)=9 若A这个关键字的值映射的地址是9

那么要比较几次关键字才知道查找失败呢？

1. 先与100比较
2. 再与9比较
3. 最后发现空指针NULL

【答案一】这里比较了2次
【答案二】但有些教材与学校把和空指针比较也算一次，那就是3次了
这两个答案只是不同的说法，但一般是答案一，毕竟指针的判别，不是【关键字比较】

装填因子

表中关键字填满的程度a = n/len

【例子】
1. 关键字列表{1, 9, 12, 11, 25, 35, 17, 29}创建Hash表
2. 装填因子a为1/2
3. 试确定表长len
4. 采用除留余数法构造Hash函数
5. 采用链地址法来处理冲突

【构造】
1. 装填因子a=1/2 => len=15
2. 取p=13（p≤len的最大素数）
3. 用链地址法