一、什么是hash冲突？
假设hash表的大小为9（即有9个槽），现在要把一串数据存到表里：5,28,19,15,20,33,12,17,10
简单计算一下：hash(5)=5, 所以数据5应该放在hash表的第5个槽里；hash(28)=1，所以数据28应该放在hash表的第1个槽里；hash(19)=1，也就是说，数据19也应该放在hash表的第1个槽里——于是就造成了碰撞（也称为冲突，collision）。
二、Hash冲突解决方法：
1.开放定址法(再散列法)：
基本思想：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…， 直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
这种方法有一个通用的再散列函数形式：
Hi=（H（key）+di）% m i=1，2，…，n
其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。
(1).线性探测再散列：
dii=1，2，3，…，m-1
冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
(2).二次探测再散列：
di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )
冲突发生时，在表的左右进行跳跃式探测，比较灵活。
(3).伪随机探测再散列：
di=伪随机数序列。
具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。
4. 示例：
已知哈希表长度m=11，哈希函数为：H（key）= key % 11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。
a): 如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，
继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元。
0 1 2 3 4 5 6 7 8 9 10
47 26 60 69
b): 如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，
将69填入2号单元。
0 1 2 3 4 5 6 7 8 9 10
69 47 26 60
c): 如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址
为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元。
0 1 2 3 4 5 6 7 8 9 10
47 26 60 69
2.再哈希法
这种方法是同时构造多个不同的哈希函数：
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
3.链地址法 (HashMap的冲突处理方式)
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
4.建立公共溢出区
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
三、拉链法与开放地址法相比的缺点：
拉链法优点：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
拉链法缺点：
指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
四、不同处理冲突的平均查找长度
例：
假设散列表的长度是13，三列函数为H(K) = k % 13，给定的关键字序列为{32， 14， 23， 01， 42， 20， 45， 27， 55， 24， 10， 53}。分别画出用线性探测法和拉链法解决冲突时构造的哈希表，并求出在等概率情况下，这两种方法的查找成功和查找不成功的平均查找长度。
（1）线性探测法：
查找成功时的查找次数等于插入元素时的比较次数,查找成功的平均查找长度为：
ASL = （1+2+1+4+3+1+1+3+9+1+1+3)/12 = 2.5
查找成功时的查找次数：第n个位置不成功时的比较次数为，第n个位置到第1个没有数据位置的距离：如第0个位置取值为1，第1个位置取值为2.
查找不成功的平均查找次数为：
ASL = （1+2+3+4+5+6+7+8+9+10+11+12）/ 13 = 91/13
（2）链地址法
查找成功时的平均查找长度：
ASL = (1*6+2*4+3*1+4*1)/12 = 7/4
查找不成功时的平均查找长度：
ASL = (4+2+2+1+2+1)/13
注意：查找成功时，分母为哈希表元素个数，查找不成功时，分母为哈希表长度。
https://blog.csdn.net/u011080472/article/details/51177412
