Java基础知识---解决hash冲突的几种方法_java 对象hashcode相撞 hashcode优化

一. 两个不相等的对象可能会产生相同的hashcode

• 在产生hash冲突时,两个不相等的对象就会有相同的 hashcode 值，为了解决这个问题，一般都四种方式去解决。

产生哈希冲突的原因

• 哈希是通过对数据进行再压缩，提高效率的一种解决方法。但由于通过哈希函数产生的哈希值是有限的，而数据可能比较多，导致经过哈希函数处理后仍然有不同的数据对应相同的哈希值。

二. 开放定址法

• 开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一一个空闲位置，将其插入。比如，我们可以使用线性探测法。当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，如果遍历到尾部都没有找到空闲的位置，那么我们就再从表头开始找，直到找到为止
  

①. 线性探测

• 按顺序决定哈希值时，如果某数据的哈希值已经存在，则在原来哈希值的基础上往后加一个单位，直至不发生哈希冲突。

②. 再平方探测

• 按顺序决定哈希值时，如果某数据的哈希值已经存在，则在原来哈希值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。

③. 伪随机探测

• 按顺序决定哈希值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来哈希值的基础上加上随机数，直至不发生哈希冲突。

三. 链式地址法（HashMap的哈希冲突解决方法）

• 对于相同的哈希值，使用链表进行连接。使用数组存储每一个链表。将哈希表的每个单元作为链表的头结点，所有哈希地址为 i 的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。
  

四. 再哈希法

• 对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。

五. 建立公共溢出区

• 建立公共溢出区存储所有哈希冲突的数据。

六. 链式地址法和开放定址法比较

①. 链式地址法

优点

• ①对于记录总数频繁可变的情况，处理的比较好（也就是避免了动态调整的开销）
• ②由于记录存储在结点中，而结点是动态分配，不会造成内存的浪费，所以尤其适合那种记录本身尺寸（size）很大的情况，因为此时指针的开销可以忽略不计了
• ③删除记录时，比较方便，直接通过指针操作即可

缺点

• ①存储的记录是随机分布在内存中的，这样在查询记录时，相比结构紧凑的数据类型（比如数组），哈希表的跳转访问会带来额外的时间开销
• ②由于使用指针记录不容易进行序列化（Serializable）操作

②. 开放定址法

优点

• ①记录更容易进行序列化（Serializable）操作
• ②如果记录总数可以预知，可以创建完美哈希函数，此时处理数据的效率是非常高的

最后总结

1. 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
2. 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
3. 开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，
   拉链法中增加的指针域可忽略不计，因此节省空间；
4. 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，
   删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。