一.基础知识
1.——哈希结构——查找哈希表/哈希表
2 .同义词：不同的关键字由散列函数映射到同一个值，它们是“同义词”
3 .碰撞：在这个位置已经保管了元素，这就产生了碰撞
4 .解决争端：拉链法/链地址法
将同义词保存到链表中
对于同义词，各关键字之间的顺序可以不一致，但排序可以在按顺序搜索链表时提高搜索效率
2 .哈希搜索
给出散列函数h(key )=key
给出关键字{19、14、23、1、68、20、84、27、55、11、10、79}
14=1，放入1号框，其他相同
(1)找55
在55=3、3号框中向下搜索，依次找到68、55，搜索成功，搜索长度为2
注：
查找长度：对比次数
)2)查找21
21=8，8位为空，检索失败
搜索长度： 0
注： 0次比较
)3)找66
66=1，在1号框向下找，依次找到14、1、27、79，找失败了
搜索长度： 4
注：四次比较
三.效率分析ASL
ASL成功=(162434 )/12=1.75 (横向计算)
ASL成功=[(1 234 ) )1 2 ) ) 1 2 )…]/12=1.75 ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) 652 )
注：每个框一个关键字时，效率最高
aslmin=(11…1 )/12=1
因此尽可能使用减少冲突
从在每一个框中寻找的长度(比较次数)来看，共有13个框
ASL失败=(0402021…)/13=0.92
可以看出分子是蓝框之和，分母是表长
即，ASL失败=表中记录数/散列表长度
为装填因子，=表中记录数/散列表长度
显然，填充因子直接影响着哈希表的检索效率，为了提高检索效率设计合理的哈希函数是很重要的
四.常见散列函数
设计目标：尽量减少不同关键词的冲突
1 .剩余法h(key )=key%p
m :散列表长
(p ) m以下的最大素数(通常具体问题将具体分析) )。
素数/素数：大于1的自然数中，不再具有1和其自身以外的因子的自然数。 例如2、3、5、7
例如：
表的长度为m=13，p为13
表的长度为m=15，p为13
2 .直接寻址法
h(key )=key或h(key )=a*key b
这里a和b是常数
优点：不发生冲突
缺点：占用空间太大
拟合：关键词的分布基本连续。 否则，会浪费空间
示例：保存班上同学的学生信息
每个学号与1120112176拉开差距，0、1、2、3…
3 .数字分析法
拟合：分布均匀
例如：手机号码
均匀分布在某个比特上，不均匀分布在某个比特上
可以将移动电话号码后4位作为散列地址
4 .平方取中法
平方关键词，取中间的几位数
符合：关键字的每个读取值小于散列地址所需的位数或不相等
例如：保存身份证号码
平方身份证号码，取中间五位
这样分布就会比较均匀，不会发生碰撞) ) ) ) ) ) ) ) ) ) ) )。
总结
五.解决冲突的另一种方法：开放定址法
Hi=(H(key)+di)%m
I=0，1，2，3，…，k (k (km-1 ) ) ) ) )。
m :表长
di :增量序列
(I )第I次冲突
(一)线性探测法
1 .基本概念
di=0，1，2，3，…，m-1
1、插入h(key )=1=1进行冲突
表的长度m=16
H0=(1D0)=1仍然是冲突的
继续计算H1=(1D1)=2
正常放入
这是空闲地址既向它的同义词开放，也向它的非同义词开放
接着，试图进入84
h(key )=84=6碰撞
H1=(61 )=7碰撞
H2=(62 )=8正常放入
放入27
h(key )=27=1碰撞
H1=(1)=2碰撞
H2=(12 )=3冲突
成功投入了H3=(1)3)=4
其他同样，如果你想放在25里
h(key )=25=12冲突
H1=(121 )=13正常放入
另外，想输入数据时，最大表长15
hi=(h ) key (di ) )。
即冲突处理函数值域为[0,15]
零散的情况
列函数H(key)=key%13散列函数值域[0,12]
2.查找操作
（1）查找27
27%13=1，匹配失败
H1=2，匹配失败
H2=3，匹配失败
H3=4，匹配成功
查找长度：4
（2）查找11
11%13=11，匹配成功
查找长度：1
（3）查找21
21%13=8匹配失败
H1=9匹配失败
H2=10匹配失败
H3=11匹配失败
H4=12匹配失败
H5=13匹配失败
与拉链法的空指针不同，这里空白处也记一个元素，与空位置相比也算一次比较
查找长度：6
（4）查找21
21%13=8匹配失败
H1=9匹配失败
H2=10匹配失败
对比完空位置，查找结束
查找长度：3
3.删除操作
删除1，1空出，想要查找27时
27%13=1匹配失败
H1=2匹配是吧，遇到空白结束
未成功找到4号位的27
因此在删除1后需要告诉计算机1位置有东西（做一个删除标记，进行逻辑删除），查找时还需要继续往后找
缺点：删除元素过多时还需要一个个对比
查找79
79%13=1
H1、H2…H9成功
8次冲突，对比关键字9次
4.查找效率分析ASL
ASL成功=(1+1+1+2+4+1+1+3+3+1+3+9)/12=2.5
查找失败需要走到底
初次探测地址H0只能在[0,12]
要查找的关键字映射到0的位置：需要对比1次
要查找的关键字映射到1的位置：需要对比13次
…
要查找的关键字映射到12的位置：需要对比2次
ASL失败=(1+13+12+11+10+9+8+7+6+5+4+3+2)/13=7
注：若用mod表示key%13中的13
这里的分子的个数是mod（从0~mod-1）,分母的值也是mod；而查找成功的分母为元素个数（12）
例：现有长度为 11 且初始为空的散列表 HT，散列函数是 H(key) = key % 7，采用线性探查 （线性探测再散列）法解决冲突。将关键字序列 87, 40, 30, 6, 11, 22, 98, 20 依次插入 HT 后， HT 查找失败的平均查找长度是 ：(9+8+7+6+5+4+3)/7=6
（二）平方探测法
1.基本概念
di=0,1,-1,4,-4,9,-9
表长27
（1）插入19
19%13=6，冲突
H1=(6+1)%27=7成功插入
（2）插入32
32%13=6，冲突
H1=(6+1)%27=7冲突
H2=(6-1)%27=5成功插入
插入84
84%13=6
H1=7冲突
H2=5冲突
H3=10冲突
H4=2冲突
H5=(6+9)%27=15冲突
H6=(6-9)%27=(-3)%27=24
注：(-3)=(-1)×27+24
mod也把表看成循环表，6往左移动9位，5,4,3,2,1,0,26,25,24
插入成功
2.查找
查找71
71%13=6匹配失败
H1=7匹配失败
H2=5匹配失败
H3=10匹配失败
H4=2匹配失败
H5=15匹配成功
3.其他
平方探测法散列表的长度m必须可以表示成4j+3的素数，才能探测到所有位置
如：m=4×1+3=7可以
m=8不可以
（三）伪随机序列法
di是一个伪随机序列
如：di=0,5,24,11…
举例：
总结
六.再散列法
除了原始的散列函数H(key)之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止
Hi=RHi(key)
i=1,2,3,…,k