哈希表（散列表）
1. 哈希表(散列表)的基本概念
散列表，又称哈希表。是一种数据结构，特点是：数据元素的关键字与其存储地址直接相关。
解释说明 已知关键字，能计算出来它的存储地址
若不同的关键字通过散列函数映射到同一个值，则称他们为“同义词”。
通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”
给出一个具体实例：
注意在本题中，采用处理冲突的方法是拉链法，即两个关键字，映射到相同的地址，就让他们之间顺序的指向
1.查找27的过程：
27=1 顺序查找地址1，查到第三个成功查到了27。
2.查找21的过程：
21=8，为空。
查找长度为0
查找长度-- 在查找运算中，需要对比关键字的次数称为查找长度
:three: ASL~成功~
（1*6 2*4 3*1 4*1）/12=1.75
平均成功查找长度=查找成功各情况比较的总次数/查找成功的情况总数
最理想的情况
:four: 平均失败查找长度
（0 4 0 2 0 0 2 1 0 0 2 1 0）/13=0.92
平均失败查找长度：从头带尾都查找失败的总次数/散列表长度 其实就是：表中记录数/散列表长度 平均失败查找长度又叫装填因子a ，，，，，，，，，，，，
引出下文：
不难发现，哈希表最重要的两部分是
如何让关键值分布的均匀------散列函数解决
如果冲突了怎么处理 ----------处理冲突的方法
2. 常见的散列函数
2.1 除留余数法
H(key)=key%p
散列表表长为m，取一个不大于m但最接近或等于m单的质数p,这个p作为散列表新的表长
为什么取最大质数？
让不同关键字的冲突尽可能少。所以即使散列表本身是15，为了减少冲突，还是得取13
2.2 直接定址法
直接定址法
H(key)=key或H(key)=a*key b
适合分布基本连续的情况，如存储同一个班级的学生信息，班内学生学号为(1120112176~1120112205),设计哈希函数为H(key)=key-1120112176
若分布不连续，空位就会比较多，会造成存储空间的浪费。
2.3 数字分析法
选取数码分布较为均匀的若干位作为散列地址
数码在各位上出现的频率不一定相同，可能在某些位上分布的均匀，某些位不均匀
2.4 平方取中法
取关键字的平方值的中间几位作为散列地址
具体取多少位要视实际情况而定。这种方法得到的散列地址与关键的每位都有关系
总结：散列查找是典型的用空间换时间的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低。
3. 处理冲突的方法
3.1 拉链法
前面提到的拉链法就是处理冲突的一种方法
3.2 开放定址法
- 线性探测法
- 平方探测法
- 伪随机序列法3.2.1开放地址法的定义开放地址法的核心就是说把其他地址开放，发生冲突时，可以把关键字放入其他的地址 数学公式 H~i~=(H(key) d~i~)%m，其中m是<font color="red">表长!!!</font> d~i~是增量序列，根据d~i~的不同，可以分为三种方法。
- :star:线性探测法
- 平方探测法
- 伪随机序列法 ==注意==：H(key)是哈希函数，哈希函数的计算是哈希函数，开放地址的计算是另一个东西，切不可混淆。尤其是哈希函数➗的是我们人为设置的，而开放地址法➗的是表长。
使用开放地址法计算ASL的时候，要注意空位置的判断也要算作一次比较，和上面的拉链法不同，可以理解为拉链法比较的是空指针，开放地址法是空的元素，所以算作一次
采用开放定址法时，删除结点不能简单地将被删结点的空间置为空，要做一个删除标记，进行逻辑删除(只能逻辑删除)，如果不这么做，后面再查找时，可能会出现中间出现截断就不查找了，直接算查找失败了.
3.2.2 开放地址法的三种方法
1.线性探测法：
d~i~=0，1，2，3，4....m-1，即发生冲突时，每次往后探测相邻的下一个单元是否为空。
d~i~，意味着发生第0次冲突，d~i~取0， d~i~就是 0，意味着发生第1次冲突，d~i~取1， d~i~就是 1
举一个计算ASL成功的例子
举出一个查找失败的例子:
2.平方探测法：
d~I~=0^2^,1^2^,-1^2^,2^2^,-2^2^,...,k^2^,-k^2^
平方探测法：比起线性探测法更不易产生“聚集”（堆积）问题。
注意一点,一个坑：平方探测法散列表长度m必须是一个可以表示4j 3的素数，才能探测到所有位置。
3.伪随机序列法：d~i~=某个伪随机序列，如d~i~=0,5,24,11,....
3.3 再散列法(再哈希法)
准备多个散列函数，一个发生冲突就用下一个。
4. 重难点题型总结
4.1 拉链法求平均成功查找长度与查找失败长度
ASL~成功~要横着看，（一次查找到的结点数 2*两次的查到的结点数 ...n*n次查到的结点数）/表中所有的结点数
ASL~失败~=表中所有的结点数/mod的数
解释说明，上面给出的ASL~失败~只是一种数值相等的公式，并不是理解。
拉链法中空指针算0次比较，所以拉链法在每一种查找失败的情况，就是该条链下结点的个数，mod的数，就是情况数，比如mod7，会得到0-6，7种情况。
例题如下:
【1999年 9分】
4.2 开发地址法之线性探测法求平均成功查找长度与查找失败长度
重点讲解：
1.当用哈希函数算完之后，使用线性探测的时候，要注意，分母变成了表长，不是哈希函数中的modx中的x，并且使用结果是上一步中哈希函数的结果，比如算完46=2，假设表长为13，线性探测就是（2 1），而不是（46 1），也不是（2 1），这都是值得注意的。
2.在计算平均查找失败长度的过程中，每一次的情况是遇到空的时候就停止。
分母是映射空间，哈希函数是mod7，地址空间就是0-6，7种情况，从为0的情况出发一直加到6的情况
3.查找成功就是比较次数，这里不多说了
例题1:
例题2:
4.3 开发地址法之平方探测法求平均成功查找长度
根据题目给出的H~i~函数，来具体进行平方探测法的计算，本质和线性探测是一回事
例题1:
