HashMap底层实现原理在Java面试经常问到,HashMap底层实现原理主要涉及:数据结构、哈希函数等。
1.HashMap的数据结构
要搞清楚HashMap底层实现原理,首当其冲,要了解清楚HashMap的数据结构。
如下图所示:
HashMap 底层是一个数组,每个数组元素是一个链表,也就是一个桶(bucket),每个桶中存放的是一个个 key-value 对。
当桶中的链表长度超过阈值,默认为8,链表就会转化为红黑树,这样可以提升效率。
备注:在 JDK 1.7及以前 底层实现是一个 数组 + 链表 的形式,而在 JDK 1.7以后 ,底层是: 数组 + 链表 + 红黑树 ,也就是红黑树是JDK1.8开始才有的。
2.HashMap哈希函数
哈希函数是HashMap的核心,所以要掌握HashMap底层实现原理,这是重点。
HashMap哈希函数,如下图所示:
在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值进行按位异或操作,得到一个新的哈希值。
如下图所示:
这样做的目的其实就是为了增强哈希值的随机性,这个方法也叫做“扰动方法”。
3.HashMap哈希冲突
理解了HashMap哈希函数,还需要了解HashMap冲突,这是HashMap底层实现原理的关键点。
由于哈希函数的输出长度是固定的,因此可能会出现不同的键对应到同一个桶的情况,这种情况称为哈希冲突。
如下图所示:
为了解决哈希冲突,HashMap采用了链地址法,即在每个桶中使用链表来存储具有相同哈希值的键值对。
4.动态扩容
在实际开发过程中,出现容量默认大小不能满足需求时,就需要扩容。
如下图所示:
当HashMap中的键值对数量达到了负载因子(load factor)乘以容量的阈值时,就会触发扩容操作。
负载因子的默认值是0.75,而容量大小默认是16,也就是说,第1次扩容的动作会在元素个数达到12的时候触发,扩容的大小是原来的2倍。
在扩容时,HashMap会创建一个新的数组,并将原数组中的所有键值对重新插入到新数组中。
以上就是HashMap底层实现原理的详解,主要就是涉及到:数据结构、哈希函数、以及扩容等原理。
作者简介
陈睿|mikechen,10年+大厂架构经验,就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注作者「mikechen」公众号,获取更多技术干货!
后台回复【架构】,即可获取《阿里架构师进阶专题全部合集》,后台回复【面试】即可获取《史上最全阿里Java面试题总结》