HashMap底层实现原理(图文超详解)

HashMap底层实现原理在Java面试经常问到,HashMap底层实现原理主要涉及:数据结构、哈希函数等。

1.HashMap的数据结构

要搞清楚HashMap底层实现原理,首当其冲,要了解清楚HashMap的数据结构。

如下图所示:

HashMap底层实现原理(图文超详解)-mikechen

HashMap 底层是一个数组,每个数组元素是一个链表,也就是一个桶(bucket),每个桶中存放的是一个个 key-value 对。

当桶中的链表长度超过阈值,默认为8,链表就会转化为红黑树,这样可以提升效率。

备注:在 JDK 1.7及以前 底层实现是一个 数组 + 链表 的形式,而在 JDK 1.7以后 ,底层是: 数组 + 链表 + 红黑树 ,也就是红黑树是JDK1.8开始才有的。

 

2.HashMap哈希函数

哈希函数是HashMap的核心,所以要掌握HashMap底层实现原理,这是重点。

HashMap哈希函数,如下图所示:

HashMap底层实现原理(图文超详解)-mikechen

在Java中HashMap使用的哈希函数是取模算法,即通过对键的哈希值进行取模运算,得到数据存储的位置。

HashMap中的hash算法中,首先会 key 计算出hashCode值,如下所示:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

然后再将hashCode值与右移 16 为的hashCode值进行按位异或操作,得到一个新的哈希值。

如下图所示:

HashMap底层实现原理(图文超详解)-mikechen

这样做的目的其实就是为了增强哈希值的随机性,这个方法也叫做“扰动方法”。

 

3.HashMap哈希冲突

理解了HashMap哈希函数,还需要了解HashMap冲突,这是HashMap底层实现原理的关键点。

由于哈希函数的输出长度是固定的,因此可能会出现不同的键对应到同一个桶的情况,这种情况称为哈希冲突。

如下图所示:

HashMap底层实现原理(图文超详解)-mikechen

为了解决哈希冲突,HashMap采用了链地址法,即在每个桶中使用链表来存储具有相同哈希值的键值对。

 

4.动态扩容

在实际开发过程中,出现容量默认大小不能满足需求时,就需要扩容。

如下图所示:

HashMap底层实现原理(图文超详解)-mikechen

当HashMap中的键值对数量达到了负载因子(load factor)乘以容量的阈值时,就会触发扩容操作。

负载因子的默认值是0.75,而容量大小默认是16,也就是说,第1次扩容的动作会在元素个数达到12的时候触发,扩容的大小是原来的2倍。

在扩容时,HashMap会创建一个新的数组,并将原数组中的所有键值对重新插入到新数组中。

以上就是HashMap底层实现原理的详解,主要就是涉及到:数据结构、哈希函数、以及扩容等原理。

作者简介

陈睿|mikechen,10年+大厂架构经验,就职于阿里巴巴、淘宝、百度等一线互联网大厂。

关注作者「mikechen」公众号,获取更多技术干货!

后台回复架构,即可获取《阿里架构师进阶专题全部合集》,后台回复面试即可获取《史上最全阿里Java面试题总结

评论交流
    说说你的看法