HashMap解决哈希冲突的方式
一、链式寻址法(链表法)
在JDK1.8版本中,HashMap主要采用链式寻址法来解决哈希冲突。当不同的键通过哈希函数计算后得到相同的哈希值(即发生哈希冲突)时,会将这些键值对以单向链表的形式存储在哈希表对应的桶(bucket)中。例如,当向HashMap中插入键值对时,如果计算得到的索引位置已经存在元素,那么新的元素就会被添加到该位置的链表末尾。这样,在查找元素时,如果遇到哈希冲突,就需要遍历链表来找到对应的键值对。 具体来说,HashMap中的每个桶其实就是一个链表的头节点,当有新元素插入到已存在元素的桶中时,新元素对应的Entry对象会指向原来桶中的Entry对象,从而形成链表结构。这一过程可以从源码中得到体现,在
addEntry
方法中,当
bucketIndex
索引处已经有了一个Entry对象,新添加的Entry对象就会指向原有的Entry对象,形成Entry链。
二、红黑树优化(JDK1.8特性)
在JDK1.8版本中,HashMap还引入了红黑树来优化链表过长导致的性能问题。当链表长度大于8并且哈希表的容量大于64的时候,再向链表中添加元素就会触发链表转化为红黑树。红黑树是一种自平衡的二叉查找树,它的查找、插入和删除操作的时间复杂度都是 O ( lo g n ),相比链表在数据量较大时具有更高的查找效率。
除了上述HashMap采用的方法外,还有一些其他常见的解决哈希冲突的方法:
-
开放定址法(线性探测法等)
- 线性探测法:从发生冲突的那个位置开始,按照一定的次序从hash表中找到一个空闲的位置,然后把发生冲突的元素存入到这个空闲位置中。例如,在插入元素时,如果发生冲突,就往后找没有元素的位置。
- 平方探测再散列:如果发生冲突,放到(冲突+1平方)的位置,如果还发生冲突,就放到(冲突 - 1平方)的位置;如果还有冲突就放到(冲突+2平方)的位置,以此类推,要是负数就倒序数。开放定址法中的线性探测法被ThreadLocal用于解决hash冲突。
- 再哈希法:当通过某个hash函数计算的key存在冲突时,再用另外一个hash函数对这个key做hash,一直运算直到不再产生冲突。
- 建立公共溢出区:把hash表分为基本表和溢出表两个部分,凡是存在冲突的元素,一律放入溢出表中。