「Java 进阶之路」系列 Day22写在前面HashMap是被问得最深的一个集合类随便一道追问就能扯出扰动函数、树化阈值、扩容时的位运算优化这些细节。这篇把 JDK 8 之后HashMap的底层结构和扩容机制从头捋一遍讲清楚每一个看似抠细节的设计背后到底图的是什么。一、是什么数组 链表 红黑树的混合结构Node数组 也叫哈希桶某个桶为空某个桶是链表 长度小于8某个桶是红黑树 长度大于等于8且数组长度大于等于64HashMap内部是一个Node[]数组每个位置叫一个桶bucket。存进去的键值对先算出一个下标落到某个桶里桶里没东西就直接放如果好几个不同的 key 算出同一个下标哈希冲突就在这个桶里挂成一条链表链表长度涨到一定程度会转成红黑树以提升查找效率。这个混合结构的设计意图很直接纯数组没办法处理哈希冲突纯链表查找是O(n)效率太差数组做快速定位、链表/树处理同一个桶内的冲突是空间和查找效率的折中方案。二、为什么这样设计几个容易被忽略的细节扰动函数为什么不直接用 hashCode()// HashMap内部的hash方法简化版staticinthash(Objectkey){inthkey.hashCode();returnh^(h16);// 高16位和低16位做异或}HashMap定位桶的公式是(容量 - 1) hash如果容量是16容量-1二进制就是0000...1111这个按位与操作只有hash值的低4位在起作用高位信息完全被浪费。如果两个key的hashCode低位相同、只有高位不同不做处理的话会被分到同一个桶里增加冲突概率。hash()方法把高16位和低16位做异或让原本用不上的高位信息也参与到最终结果的低位运算中相当于把分布信息从高位打下来减少了这种冲突。容量为什么必须是2的幂定位桶用的(容量-1) hash这个位运算只有在容量是2的幂时才等价于hash % 容量取模运算的效果而且分布均匀——位运算比取模运算快得多这是HashMap拿性能换出来的一个设计前提。这也是为什么即使你new HashMap(17)传了个奇怪的初始值JDK 内部也会自动把它调整成不小于17的最近一个2的幂这里是32保证这个位运算优化始终成立。put 的完整流程计算key的hash值用容量减1和hash做按位与定位到桶桶为空直接放入新节点桶不为空遍历桶内节点寻找相同的key找到相同key则替换旧值没找到则在链表尾部插入新节点链表长度达到8且数组容量达到64树化 转换成红黑树为什么树化阈值选 8退化阈值选 6不是同一个数链表长度超过8才转红黑树是因为在哈希分布良好的正常情况下一个桶挂到8个节点的概率极低按泊松分布计算大约是百万分之六十也就是说绝大多数场景根本不会触发树化只有hashCode设计得很差或者遭遇了针对性构造的哈希碰撞攻击时才会用到——红黑树节点本身比普通链表节点占用更多内存要维护平衡、存储颜色和多个指针只有真正冲突严重、值得用空间换查找效率时才转换。树退化回链表的阈值是6不是8这是故意留了一个缓冲区——如果树化和退化都用同一个阈值8节点数量在8附近反复增删时会导致链表和树来回抖动转换白白浪费性能用6做退化阈值、8做树化阈值中间隔出3个数字的缓冲空间避免这种震荡。三、怎么用扩容机制与 JDK 8 的一个巧妙优化HashMap有一个负载因子默认0.75阈值 容量 × 负载因子。元素个数超过这个阈值就触发扩容新容量是旧容量的2倍。扩容意味着所有节点要重新计算应该落在哪个桶里——但 JDK 8 之后有个巧妙的优化不需要重新完整计算每个节点的hash扩容前容量是16二进制10000扩容后是32二进制100000 一个节点原来的桶下标是hash值的低4位决定的 扩容后多了一位参与定位低5位只需要看这新增的这一位是0还是1 这一位是0 → 新桶下标和原下标相同节点留在原位置 这一位是1 → 新桶下标 原下标 旧容量16判断这新增的一位是0还是1只需要做一次hash oldCapacity的位运算不需要把hash和新容量重新做一次完整的取模计算——这个优化把扩容时每个节点的重定位计算从重新算一次哈希定位简化成了判断一个二进制位是JDK 8对HashMap扩容做的一个典型性能优化点也是面试里HashMap扩容原理这个问题能问出深度的地方。四、面试追问Q1HashMap 的 hash() 方法为什么要把 hashCode 的高16位和低16位做异或因为定位桶用的(容量-1) hash这个运算容量通常不大比如16容量-1的二进制只有低几位是1这意味着只有hash值的低位在参与定位高位信息完全被浪费。做异或扰动能把高位的信息混到低位里让两个hashCode低位相同、只有高位不同的key也能有更大概率分散到不同的桶减少哈希冲突。Q2为什么 HashMap 的容量必须是2的幂因为定位桶用的位运算(容量-1) hash只有在容量是2的幂时才等价于对哈希值做取模运算、并且分布均匀同时位运算比取模运算性能更好。这是HashMap用位运算代替取模运算的一个性能优化前提就是容量必须是2的幂所以即使构造时传入了不是2的幂的初始容量JDK内部也会自动调整成最近的、不小于该值的2的幂。Q3链表转红黑树的阈值为什么是8退化回链表又为什么是6而不是8链表长度达到8才转红黑树是因为在哈希分布正常的情况下一个桶挂到8个节点的概率极低绝大多数场景不需要用到红黑树只在冲突真的很严重时才值得为查找效率付出额外的内存和维护成本。退化阈值用6而不是8是为了避免节点数量在8附近反复增删时链表和树来回抖动转换6和8之间留出的缓冲区能减少这种无意义的性能损耗。Q4HashMap 扩容时JDK 8 做了什么优化避免重新计算每个节点的哈希扩容后容量翻倍参与定位的位数多了一位。JDK 8 利用这一点只需要判断节点hash值里新增的那一位是0还是1是0则新桶下标和原下标相同节点留在原位置是1则新桶下标等于原下标加上旧容量。这只需要一次hash oldCapacity的位运算就能判断不需要把hash值和新容量重新做一次完整定位计算大幅简化了扩容时每个节点重新分桶的开销。Q5HashMap 的默认负载因子为什么是 0.75不是1或者更低的值负载因子是空间利用率和哈希冲突概率之间的权衡负载因子设得太高比如接近1数组空间利用得更充分但桶越容易被填满哈希冲突概率上升链表变长查找效率下降负载因子设得太低冲突概率低、查找快但会浪费更多数组空间没被用上、还会更频繁触发扩容。0.75是JDK经过测算后在这两者之间取得的一个比较均衡的默认值。下一篇预告Day23 讲一个很实际的问题HashMap为什么线程不安全多线程并发操作会出现什么具体问题以及和ConcurrentHashMapDay08 讲过到底差在哪个环节。