周末，本来打算找人去玩，结果没找到，所以我只好有学习了。
为什么会学习散列表，因为要使用HashMap？因为在做项目的时候，在服务器和客户端需要传输DTO，而传输的属性是动态增加的，所以需要HashMap动态的添加一些属性到DTO类中去，所以学习一下。
【定义】
Hash表：是根据关键字而直接进行访问的数据结构，也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。
散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash（key）=Addr。
冲突：散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为“冲突”。
同义词：这些发生碰撞的不同关键字成为同义词。
【基础知识】
一. 常用的散列函数：
直接定址法——H（key）=a*key+b
除留余数法——H（key）=key%p
数字分析法
平方去中法
二. 处理冲突的方法
(一) 拉链法
拉链法是指把所有的同义词存储在一个线性链表中，这个链表由散列地址唯一标识。
关键字码为：{06,12,15,26,36,38,41,44,51,68}，散列函数为H(key)=key%13。用拉链法处理冲突建立的表如下：
(二) 开放定址法
开放定址法是指可存放新表项的空闲地址即向它的同义词表项开发，又向它的非同义词表项开发。其数学递推公式为(Hi表示冲突发生后第i次探测的散列地址)：
Hi=(H(key)+di)%m
其中，i=1，2，···，k(k<=m-1)；m为散列表表长；di为增量序列。当取定某一增量序列后，则对应的处理方法是确定的。通常有：
1. 线性探测
di=1，2，···，m-1
特点：冲突发生时，顺序查看表中下一个单元，直到找到空单元为止。
2. 平方探测
di=12，-12，22，-22···，k2，-k2。K<=m/2
3. 再散列
【题】
设有一组关键字{9,1,23,14,55,20,84,27}，采用散列函数H(key)=key mod 7,表长为10，用开放定址的二次探测再散列法Hi=(H(key)+di)%10(di=12，22，32，···)解决冲突。要求：对该关键字序列构造散列表，并计算查找成功的平均查找长度。
答案：
{9,1,23,14,55,20,84,27} mod 7={2,1,2,0,6,6,0,6}
关键字
计算
比较次数
9
H(9)=9%7=2(不冲突)
1
1
H(1)=1%7=1(不冲突)
1
23
H(23)=23%7=2(冲突)，H1=(2+1)%10=3(不冲突)
2
14
H(14)=14%7=0(不冲突)
1
55
H(55)=55%7=6(不冲突)
1
20
H(20)=20%7=6(冲突)，H1=(6+1)%10=7(不冲突)
2
84
H(84)=84%7=0(冲突)，H1=(0+1)%10=1(冲突)，H2=(0+22)%10=4(不冲突)
3
27
H(27)=27%7=6(冲突)，H1=(6+1)%10=7(冲突)，H2=(6+22)%10=0(冲突)，H3=(6+32)%10=5(不冲突)
4
散列地址
0
1
2
3
4
5
6
7
8
9
关键字
14
1
9
23
84
27
55
20
探测长度
1
1
1
2
3
5
1
2
平均查找长度=(1+1+2+1+1+2+3+4)/8=15/8