何为Hash冲突
假设Hash表大小为5(即5个槽位)，现在要把2,5,6,7,8这几个数存储到Hash表中，假设hash函数为hash(num)=num % size
简单计算下，第一个数2的hash值为2所以放到第三个槽中，第二个数5的hash值为0放到第一个槽中，第三个数6的hash值为1放到第二个槽中，如下图所示：
| 1号槽 | 2号槽 | 3号槽 | 4号槽 | 5号槽 | |
|---|---|---|---|---|---|
| 5 | 6 | 2 |
第四个数7的hash值也为2，应该放到第二个槽位，但是第二个槽位中已经放有数据了，这种情况就属于hash冲突。
简单来说，就是两个不同的数据经过hash函数计算之后得到了相同的hash值，这就叫做hash冲突。
如何解决冲突
开放地址法
开放地址法也称为再散列法
基本原理
当关键字key的哈希地址 p=hash(key)出现冲突时，以hash值p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，然后将相应元素存入其中
基本公式
1 | p = hash(key) |
上面的公公式中：
hash(key)是根据关键字key计算得到的hash值pdi是一个增量序列，根据这个增量序列取值的区分，开放地址法也有不同的区分m是hash表的表长(表大小)
线性探测再散列
当上述公式中的增量序列di的取值为递增顺序取值时即为线性探测再散列1
di = 1,2,3,4,5 ... n-1,n (n <= m - 1)
这种方式在发生hash冲突时，会逐步向后移动一个位置，顺序的查看下一个槽位，一直到找出下一个空的槽位或是直到查遍全表
当hash值p出现冲突时，则将数据放到(p + 1) % m处，如果此时还存在冲突，则将数据放到(p + 2) % m处，如果再次存在冲突，则将数据放到(p + 3) % m处，依次类推
二次探测再散列
当di的取值规则如下时则称为二次探测再散列1
1*1,-1*1, 2*2,-2*2, 3*3,-3*3, ..., k*k,-k*k (k <= m/2)
当hash值p出现冲突时，则将数据放到(p + 1) % m处，如果此时还存在冲突，则将数据放到(p - 1) % m处，如果再次存在冲突，则将数据放到(p + 4) % m处，如果依然存在冲突，则将数据放到(p - 4) % m处，依次类推
伪随机探测再散列
当di的取值是随机数序列时则称为伪随机探测再散列1
2di = 随机数序列
//假设有个随机数序列：2，8，3，5，11，6，7
当hash值p出现冲突时，则将数据放到(p + 2) % m处，如果此时还存在冲突，则将数据放到(p + 8) % m处，如果再次存在冲突，则将数据放到(p + 3) % m处，如果依然存在冲突，则将数据放到(p + 5) % m处，依次类推
缺点
- 对开放地址法构造的哈希表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点
- 开放地址法要求哈希表空间大于或等于装填数据数目
再哈希法
这种方式是构造多个不同的哈希函数1
hi = RHi(key) i=1,2,3,...,k
当哈希值hi = RH1(key)发生冲突时，再计算hi = RH2(key)….一直到不产生冲突为止。
优缺点
这种方式不容易产生聚集，但是增加了计算时间
链地址法
这种方法的原理是将所有哈希值为i而导致冲突的元素构成一个同义词单链表，并将单链表的头指针存在哈希表的第i个槽位中。因此对哈希值为i的元素的查找、添加、删除都是在此单链表中进行。结构如下图
优点
- 处理冲突简单，无堆积现象，即非同义词不会产生冲突，平均查找路径较短
- 链地址法中各链表的节点空间都是动态申请的，因此链地址法比较适合构造Hash表前无法确定表长的业务场景
- 链地址法构造的哈希表删除操作比较容易实现，只需要简单的删除链表上对应的节点即可
缺点
链地址法的指针需要额外的空间
建立公共溢出区
这种方法的原理是将哈希表分为基本表和溢出表两部分，凡是和基本表中元素发生冲突的元素均存入溢出表
原创文章，转载请出处注明。
下面是我的个人公众号，欢迎关注交流
