哈希表是我们常用的一种数据结构，它拥有的 O(1) 的读写时间复杂度，但是由于它是通过计算特征并存储原始数据的方式进行实现的，因为不可避免的我们就需要考虑哈希冲突的问题，本文中列出了目前流行的多种的数据冲突解决方式。
一、Hash表基本概念
1.1、装填因子
装填因子 = （哈希表中的记录数） / （哈希表的长度）
装填因子是哈希表装满程度的标记因子。值越大，填入表中的数据元素越多，产生冲突的可能性越大。
二、Hash函数
2.1、直接寻址法
将某个关键字或者关键字的某个线性函数值作为哈希地址，即Func(Key)=a*Key+b，其中a和b为整数；这种散列函数也叫做自身函数，如果Func(Key)的哈希地址上已经有值了，那么就往下一个位置找，直到找到Func(Key)的位置没有值了就把元素放进去。
2.2、数字分析法
分析要写入的数据，依据数据的特性，选择数字出现冲突率较低的部分列来构造哈希地址，因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
2.3、平方取中法
取一个数平方后的中间几位作为散列地址，一个数的平方值的中间几位和数的每一位都有关。因此，利用平方取中法得到的哈希地址同数字的每一位都有关，这样的哈希地址具有较好的分散性。该方法适用于关键字中的每一位取值都不够分散或者较分散的位数小于哈希地址所需要的位数的情况。
2.4、折叠法
折叠法即将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（注意：叠加和时去除进位）作为散列地址，数位叠加可以有移位叠加和间界叠加两种方法：
移位叠加：将分割后的每一部分的最低位对齐，然后相加;间界叠加：从一端向另一端沿分割界来回折叠，然后对齐相加；
2.5、随机数法
选择一个随机数，去关键字的随机值作为散列地址，通常用于关键字长度不同的场合。
2.6、取余数法（比较常用）
取关键字被某个不大于散列表长度的基数p，除后所得的余数为散列地址，即Func(Key)=Key MOD p，其中p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数，若p选得不好，则很容易产生冲突，一般p取值为哈希表的长度。
三、Hash冲突解决方法
3.1、开放定址法（线性探测法）
线性探测法的地址增量di = 1, 2, ... , m-1，其中i为探测次数。该方法一次探测一个地址（上次探测的下一个地址），直到有空的地址后插入，若整个空间都找不到空余的地址，则产生溢出。
线性探测容易产生聚集现象，当表中的第i、i+1、i+2的位置上已经存储某些关键字，则下一次哈希地址为i、i+1、i+2、i+3的关键字都将企图填入到i+3的位置上，这种多个哈希地址不同的关键字争夺同一个后继哈希地址的现象称为聚集。聚集对查找效率有很大影响。
3.2、链地址法（拉链法）
将所有具有相同哈希地址的而不同关键字的数据元素连接到同一个单链表中。如果选定的哈希表长度为m，则可将哈希表定义为一个有m个头指针组成的指针数组T[0..m-1]，凡是哈希地址为i的数据元素，均以节点的形式插入到T[i]为头指针的单链表中。并且新的元素插入到链表的前端（通常新插入的元素可能不久又会被访问）。
特点：
- 处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
- 由于各链表上的节点空间是动态申请的，因此它更适合于造表前无法确定表长的情况；
- 开放定址法为减少冲突，要求装填因子
α较小，故当结点规模较大时会浪费很多空间，而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间； - 删除结点的操作易于实现，只要简单地删去链表上相应的结点即可。对于使用开放定址法构造的散列表，删除结点不能简单地将被删节点的空间置为空，否则将截断在它之后填入哈希表的同义词节点的查找路径。这是因为在开放定址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放定址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
3.3、再哈希法（二次哈希法）
同时构造多个不同的哈希函数： Func1 = RH1(key) ， Func2 = RH2(key) ，当Func1 = RH1(key) 发生冲突时，再用Func2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间。
四、平均查找长度计算
4.1、公式
| 处理冲突的方法 | 平均查找长度【查找成功】 | 平均查找长度【查找失败】 |
|---|---|---|
| 线性探测法 | $S_(nl) \approx \frac{1}{2}(1+\frac{1}{1-\alpha})$ | $U_(nl) \approx \frac{1}{2}(1+\frac{1} {(1-\alpha)^2})$ |
| 二次探测法和双哈希法 | $S_(nr) \approx-\frac{1}{\alpha}\ln(1-\alpha)$ | $U_(nr) \approx \frac{1}{1-\alpha}$ |
| 链地址法 | $S_(nc) \approx 1+\frac{\alpha}{2}$ | $U_(nc) \approx \alpha + e^{-\alpha} $ |
4.2、示例
假设散列表的长度是13，散列函数为H(K) = k % 13，给定的关键字序列为{32， 14， 23， 01， 42， 20， 45， 27， 55， 24， 10， 53}。分别画出用线性探测法和拉链法解决冲突时构造的哈希表，并求出在等概率情况下，这两种方法的查找成功和查找不成功的平均查找长度。
4.2.1、线性探测法
4.2.2、链地址法
