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面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》