[TOC]
问题一、什么是哈希冲突
由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突。（两个不同的数据计算后的结果一样）
问题二、如何解决哈希冲突
1、开放地址法（再散列法）
- 线性探查法
- 二次探测
- 随机探测再散列，
2、链地址法（拉链法）
3、再哈希法
4、创建公共溢出区
详细解释：
1、开放地址法（前提是散列表的长度大于等于所要存放的元素）
发生哈希冲突后，按照某一次序找到下一个空闲的单元，把冲突的元素放入。
线性探查法：
从发生冲突的单元开始探查，依次查看下一个单元是否为空，如果到了最后一个单元还是空，那么再从表首依次判断。如此执行直到碰到了空闲的单元或者已经探查完所有单元。
平方探查法
从发生冲突的单元加上1^2,2^2,3^2,…,n^2，直到遇到空闲的单元
双散列函数探查法
定义两个散列函数，分别为s1和s2，s1的算法和前面一致，s2取一个1～m-1之间并和m互为素数的数。s2作为步长。
2、链地址法
将哈希值相同的元素构成一个链表，head放在散列表中。一般链表长度超过了8就转为红黑树，长度少于6个就变为链表。
3、再哈希法
同时构造多个不同的哈希函数，Hi = RHi(key) i= 1,2,3 … k;
当H1 = RH1(key) 发生冲突时，再用H2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间。
4、建立公共溢出区
把哈希表分为公共表和溢出表，如果发生了溢出，溢出的数据全部放在溢出区。