如何高效总结处理Hash碰撞冲突的技巧？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1140个文字，预计阅读时间需要5分钟。
Hash冲突+我们知道，对象的前提是实现equals()和hashCode()两个方法。那么hashCode()的作用就是保证返回唯一hash值，但当两个对象的计算出的hash值相同时，就会发生冲突。下面将介绍Hash冲突。
Hash碰撞冲突
我们知道，对象Hash的前提是实现equals()和hashCode()两个方法，那么HashCode()的作用就是保证对象返回唯一hash值，但当两个对象计算值一样时，这就发生了碰撞冲突。如下将介绍如何处理冲突，当然其前提是一致性hash。
1.开放地址法
开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。
如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k<=m/2)，称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。
2.再哈希法
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止
3.链地址法（拉链法）
将所有关键字为同义词的记录存储在同一线性链表中。
本文共计1140个文字，预计阅读时间需要5分钟。
Hash冲突+我们知道，对象的前提是实现equals()和hashCode()两个方法。那么hashCode()的作用就是保证返回唯一hash值，但当两个对象的计算出的hash值相同时，就会发生冲突。下面将介绍Hash冲突。
Hash碰撞冲突
我们知道，对象Hash的前提是实现equals()和hashCode()两个方法，那么HashCode()的作用就是保证对象返回唯一hash值，但当两个对象计算值一样时，这就发生了碰撞冲突。如下将介绍如何处理冲突，当然其前提是一致性hash。
1.开放地址法
开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。
如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k<=m/2)，称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。
2.再哈希法
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止
3.链地址法（拉链法）
将所有关键字为同义词的记录存储在同一线性链表中。