Java HashMap 扩容原理实战:负载因子、树化阈值与初始容量到底怎么设

Java HashMap 扩容原理实战:负载因子、树化阈值与初始容量到底怎么设new HashMap()你写了无数遍,但很少有人想过一个问题:往里塞 1000 个元素,这个 HashMap 到底扩容了几次?每次扩容做了什么?为什么面试官老爱问「初始容量给多少合适」?这不是背八股文,是真会影响性能的东西。一次扩容意味着重新分配数组、把所有元素挪个位置,批量插入时如果反复扩容,吞吐会明显掉。这篇我们把 HashMap 的扩容机制讲清楚,并给出「初始容量到底怎么算」的可落地公式。三个关键数字:容量、负载因子、阈值HashMap 内部是一个数组(叫table),每个格子叫一个「桶」(bucket)。三个概念要先分清:容量(capacity):数组的长度,永远是 2 的幂(16、32、64…)。默认初始 16。负载因子(load factor):默认0.75。它决定「数组用到多满就扩容」。阈值(threshold):容量 × 负载因子。元素个数超过它就触发扩容。默认16 × 0.75 12。也就是说,默认的 HashMap 塞到第 13 个元素时就会第一次扩容:数组从 16 变成 32,阈值从 12 变成 24。验证一下(用反射偷看内部数组长度):importjava.lang.reflect.Field;importjava.util.HashMap;publicclassResizeDemo{staticinttableLength(HashMap?,?map)throwsException{FieldfHashMap.class.getDeclaredField(table);f.setAccessible(true);Object[]table(Object[])f.get(map);returntablenull?0:table.length;}publicstaticvoidmain(String[]args)throwsException{HashMapInteger,IntegermapnewHashMap();System.out.println(初始 table: tableLength(map));// 0,懒初始化for(inti0;i13;i){map.put(i,i);System.out.println(put i - table 长度 tableLength(map));}}}输出会看到:第一次put时数组才从 0 变成 16(懒初始化,new的时候不分配),塞到第 13 个(i12)时数组变成 32。这就是扩容发生的确切时刻。扩容做了什么:rehash扩容不是简单地把数组变长,而是要把每个元素重新分配到新数组的桶里——这个过程叫 rehash。元素落在哪个桶,由hash (capacity - 1)决定(容量是 2 的幂,所以能用位与代替取模,快)。容量翻倍后,capacity - 1的二进制多了一个高位 1,于是每个元素要么留在原来的桶,要么移动到「原索引 旧容量」的桶。JDK 8 对此做了优化:不用重新算 hash,只需看那个新增的高位 bit 是 0 还是 1 就能决定去留,省了重复计算。关键结论:扩容 分配双倍数组 遍历所有元素重新分桶。这是个 O(n) 操作。如果你能预知要放多少元素,一次性给够初始容量,就能完全避免中途反复扩容。初始容量到底怎么设:别直接填元素个数最常见的错误:「我要放 100 个元素,那就new HashMap(100)」。错了。因为负载因子 0.75 的存在,容量 100 塞到第 76 个(100×0.7575)就又扩容了。正确的公式是:初始容量 期望元素数 / 0.75 1,再让 HashMap 向上取整到 2 的幂。intexpected100;// 官方推荐算法:确保放 expected 个元素也不会触发扩容intinitialCapacity(int)(expected/0.75f)1;HashMapString,ObjectmapnewHashMap(initialCapacity);100 / 0.75 1 134,HashMap 会向上取整到 256(2 的幂),阈值256 × 0.75 192 100,放 100 个绝不扩容。JDK 19 更省心,直接有个工厂方法帮你算好:// Java 19 : 参数直接是期望元素数,内部自动换算容量MapString,ObjectmapHashMap.newHashMap(100);如果还在用 JDK 8~18,就老老实实用(int)(n / 0.75) 1这个公式。树化:链表什么时候变红黑树当多个 key 的 hash 冲突落到同一个桶,它们会先串成链表。链表长了查找就退化成 O(n)。JDK 8 引入了优化:一个桶里的链表长度达到 8,且数组容量 ≥ 64 时,链表转成红黑树,查找回到 O(log n)。这里有个容易记错的点:链表长度到 8 只是条件之一。如果此时数组容量 64,HashMap 会优先扩容而不是树化——因为容量小时冲突多,扩容能更便宜地分散冲突。只有容量 ≥ 64 且某桶链表 ≥ 8,才真的树化。反过来,红黑树节点数退回到 6 以下(比如删除元素),会退化回链表。所以「链表超过 8 就变红黑树」这句流传的说法不完整,少了「容量 ≥ 64」这个前提。// 树化的两个阈值(HashMap 源码里的常量)// static final int TREEIFY_THRESHOLD 8; // 链表转树// static final int UNTREEIFY_THRESHOLD 6; // 树退化回链表// static final int MIN_TREEIFY_CAPACITY 64; // 容量不够先扩容负载因子该不该改new HashMap(16, 0.5f)能自定义负载因子,但绝大多数情况不要动。它是空间和时间的权衡:调小(如 0.5):更早扩容,桶更稀疏,冲突少查询快,但更费内存、扩容更频繁。调大(如 0.9):更晚扩容,省内存,但冲突概率上升,查询变慢。0.75 是官方在时间和空间之间选的平衡点,基于泊松分布算过冲突概率。除非你有实测数据证明特定场景收益明显,否则保持默认。真正值得你调的是初始容量,而不是负载因子。小结HashMap 容量永远是 2 的幂,默认 16;阈值 容量 × 负载因子(默认 0.75),超过就扩容,数组翻倍。默认从第13个元素开始第一次扩容;扩容是 O(n) 的 rehash,批量插入时反复扩容会拖慢性能。设初始容量别直接填元素数,用(int)(n / 0.75) 1;JDK 19 直接HashMap.newHashMap(n)。树化需要两个条件:桶内链表 ≥ 8且数组容量 ≥ 64;容量不够时优先扩容而非树化。负载因子保持默认 0.75,该调的是初始容量。一句话记忆:能预估元素个数时,就用(int)(n/0.75)1给足初始容量,把「反复扩容 rehash」这个隐形成本一次性消掉。