HashMap解决哈希冲突的方式

一、链式寻址法（链表法）

在JDK1.8版本中，HashMap主要采用链式寻址法来解决哈希冲突。当不同的键通过哈希函数计算后得到相同的哈希值（即发生哈希冲突）时，会将这些键值对以单向链表的形式存储在哈希表对应的桶（bucket）中。例如，当向HashMap中插入键值对时，如果计算得到的索引位置已经存在元素，那么新的元素就会被添加到该位置的链表末尾。这样，在查找元素时，如果遇到哈希冲突，就需要遍历链表来找到对应的键值对。 具体来说，HashMap中的每个桶其实就是一个链表的头节点，当有新元素插入到已存在元素的桶中时，新元素对应的Entry对象会指向原来桶中的Entry对象，从而形成链表结构。这一过程可以从源码中得到体现，在 addEntry方法中，当 bucketIndex索引处已经有了一个Entry对象，新添加的Entry对象就会指向原有的Entry对象，形成Entry链。

二、红黑树优化（JDK1.8特性）

在JDK1.8版本中，HashMap还引入了红黑树来优化链表过长导致的性能问题。当链表长度大于8并且哈希表的容量大于64的时候，再向链表中添加元素就会触发链表转化为红黑树。红黑树是一种自平衡的二叉查找树，它的查找、插入和删除操作的时间复杂度都是  �(log⁡�) O ( lo g n )，相比链表在数据量较大时具有更高的查找效率。

除了上述HashMap采用的方法外，还有一些其他常见的解决哈希冲突的方法：

• 开放定址法（线性探测法等）
  • 线性探测法：从发生冲突的那个位置开始，按照一定的次序从hash表中找到一个空闲的位置，然后把发生冲突的元素存入到这个空闲位置中。例如，在插入元素时，如果发生冲突，就往后找没有元素的位置。
  • 平方探测再散列：如果发生冲突，放到(冲突+1平方)的位置，如果还发生冲突，就放到(冲突 - 1平方)的位置；如果还有冲突就放到(冲突+2平方)的位置，以此类推，要是负数就倒序数。开放定址法中的线性探测法被ThreadLocal用于解决hash冲突。
• 再哈希法：当通过某个hash函数计算的key存在冲突时，再用另外一个hash函数对这个key做hash，一直运算直到不再产生冲突。
• 建立公共溢出区：把hash表分为基本表和溢出表两个部分，凡是存在冲突的元素，一律放入溢出表中。