HashMap 是如何解决哈希冲突的

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表分为基本表和溢出表两个部分,凡是存在冲突的元素,一律放入溢出表中。


请使用浏览器的分享功能分享到微信等