结论先行:HashMap 的所有源码设计都在回答一个问题——如何让 get/put 稳定在 O(1)。哈希扰动让高位参与寻址、容量始终为 2 的幂让取模变成位运算、链表长度到 8 才树化,三者共同保证了哈希足够分散时的查找效率。理解了这三点,面试和线上问题都能直接落到源码层面:下标怎么算的、为什么这么算、异常情况的兜底在哪,都有确定性的答案。
哈希扰动:高位为什么参与运算
put 的第一步是计算 hash:
static final int hash(Object key) {
int h;
// 扰动:hashCode 与自己高 16 位异或,让高位也参与桶下标运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
扰动逻辑只有一行:hashCode 与它自己右移 16 位的结果做异或。原因是定位桶下标用的是 (n - 1) & hash,当数组容量 n 较小(比如默认 16)时,只有 hash 的低 4 位参与运算,高位信息全部丢失。把高 16 位异或进来,等于让高位也影响下标,减少「值相差很大但下标相同」的碰撞。int 只有 32 位,容量又通常远小于 2 的 16 次方,高位异或是一次成本极低、收益明显的折中:不需要额外的散列函数,一次移位加一次异或就把 32 位信息都用上了。顺带一提,key 为 null 时返回固定值 0,HashMap 是允许 null key 的,它被固定放在数组的第一个桶里,这一点与 Hashtable、ConcurrentHashMap 都不同。
扰动还能反过来解释一些现象:String 的 hashCode 实现质量高(缓存且分布均匀),所以 String 作 key 的表现稳定;而部分框架生成的对象 hashCode 集中在低位区间,就必须依赖扰动兜底。读源码时还能看到 spread 这个名字,ConcurrentHashMap 里同样的扰动逻辑被抽成了 spread(h),两个类的意图一致:在「不额外引入散列函数」的约束下尽量用满 32 位。
容量为什么必须是 2 的幂
构造方法传 new HashMap<>(10),实际容量并不是 10,而是 tableSizeFor 算出的 16——大于等于入参的最小 2 的幂。好处在取模:hash % n 等价于 hash & (n - 1),位运算比除法快,而且 n-1 的二进制是全 1,能让 hash 的每一位均匀参与下标运算。如果容量不是 2 的幂,比如 15,n-1 等于 1110,最低位恒为 0,下标永远落在偶数桶上,一半的桶直接浪费。另外 HashMap 的数组是懒加载的:new 出来时 table 还是 null,首次 put 才分配内存并确定容量,避免创建了不用白占。关键常量集中在一张表里:
| 常量 | 值 | 含义 |
|---|---|---|
| DEFAULT_INITIAL_CAPACITY | 16 | 默认容量,构造时向上取整为 2 的幂 |
| DEFAULT_LOAD_FACTOR | 0.75 | 负载因子,size 超过容量×0.75 触发扩容 |
| TREEIFY_THRESHOLD | 8 | 单桶链表长度达到 8 且容量足够时树化 |
| UNTREEIFY_THRESHOLD | 6 | 扩容拆分或删除后退化回链表的阈值 |
| MIN_TREEIFY_CAPACITY | 64 | 树化的最低容量要求,不够则优先扩容 |
| MAXIMUM_CAPACITY | 1 « 30 | 容量上限,超过后不再扩容,靠负载因子兜底 |
0.75 是空间与时间的折中:负载因子越大,空间利用率越高但碰撞概率上升;越小则扩容越频繁。扩容是成本很高的操作(整表 rehash),所以能预估数据量时,构造时直接传预估容量并留出余量,可以省掉多次扩容。
树化阈值:为什么是 8 而不是别的数
JDK 8 引入红黑树:单个桶的链表长度达到 8 且数组容量不小于 64(MIN_TREEIFY_CAPACITY)时转树,否则优先扩容。阈值 8 不是拍脑袋——理想情况下节点数遵循泊松分布,链表长度到 8 的概率约千万分之六,正常使用几乎碰不到树化。树化是哈希质量极差(key 没实现好 hashCode,或遭受哈希碰撞攻击)时的兜底手段:链表查找是 O(n),树化后是 O(log n),最坏情况的下界被拉住了。反向退化阈值是 6,留出缓冲带,避免在 8 附近频繁树化和链化来回震荡。还有一个容易忽略的细节:红黑树节点(TreeNode)的内存开销约为普通 Node 的两倍,如果一上来就全部用树存储,大部分场景反而是浪费——这正是「先链表、质量差了再树化」渐进式设计的动机。
工程上还有一个实用推论:如果业务里出现了「单个桶特别长」的监控特征,通常不是 HashMap 本身的问题,而是 key 的 hashCode 分布有问题——先去查 key 的实现,而不是急着调容量。树化只是兜底,散列质量才是根因,两者不要混淆。
扩容:JDK 8 最重要的优化
扩容时容量翻倍,元素要么留在原下标,要么落到「原下标 + 旧容量」,判断只需一次位运算(节选自 resize(),有删减):
if ((e.hash & oldCap) == 0) {
// hash 在 oldCap 那一位上是 0:新下标 = 原下标,留在低位链表
loTail.next = e;
} else {
// 是 1:新下标 = 原下标 + oldCap,挪到高位链表
hiTail.next = e;
}
判断依据很直观:容量翻倍后 n-1 多出一位,元素的新下标由 hash 在这一位上的取值决定,是 0 就原地不动,是 1 就加上旧容量。不需要重新计算每个元素的桶下标,且新旧链表都保持相对顺序,这是 JDK 7 到 JDK 8 扩容性能提升的核心。另外 JDK 8 改为尾插法,修复了 JDK 7 头插法在并发扩容时可能形成环形链表导致 CPU 100% 的问题——但这不意味着 HashMap 可以并发使用:并发 put 仍会丢数据、size 不准,JDK 8 之后的并发问题从「死循环」变成了「丢数据」,反而更隐蔽。多线程场景请直接用 ConcurrentHashMap,不要抱侥幸心理。
resize 还有一个容易忽略的成本:扩容期间老表节点被逐个搬到新表,部分读请求要顺着 forward 引用跳到新表继续查找,整个表处于「半新半旧」的过渡状态。这也是「预估容量、一次到位」比「运行期反复扩容」划算的深层原因——扩容不只是 rehash,还有过渡期的查找路径变长要消化。
实战提醒:key 的正确姿势
把自定义对象作 key 时必须同时重写 hashCode 和 equals,且二者口径一致(equals 相等则 hashCode 必须相等),否则会出现 put 成功、get 却返回 null 的诡异问题。可变字段参与 hashCode 计算后又被修改,也会造成 key「丢失」——entry 还在桶里,但按新状态算出的下标已经指不到它了。这类问题线上排查成本极高,建议 key 一律使用不可变对象:
// 错误写法:只重写 equals 不重写 hashCode,且 key 字段可变
class MutableKey {
private String userId; // 可变字段,setter 随处可调
public void setUserId(String userId) { this.userId = userId; }
@Override
public boolean equals(Object o) {
return o instanceof MutableKey
&& Objects.equals(userId, ((MutableKey) o).userId);
}
// 没有重写 hashCode:逻辑相等的两个对象散列到不同桶;
// put 之后修改 userId,这个 entry 从此「查无此人」
}
// 正确写法:不可变字段 + equals/hashCode 口径一致
final class OrderKey {
private final String orderNo; // final 字段,构造后不可变
OrderKey(String orderNo) { this.orderNo = Objects.requireNonNull(orderNo); }
@Override
public boolean equals(Object o) {
return o instanceof OrderKey
&& orderNo.equals(((OrderKey) o).orderNo);
}
@Override
public int hashCode() { return Objects.hash(orderNo); }
}
两个补充建议:一是预估数据量时在构造器传入按 0.75 换算后的初始容量,避免运行期多次扩容;二是遍历过程中的结构性修改会抛 ConcurrentModificationException,机制是 modCount 版本号校验(fail-fast),它是尽力而为的错误提示,不是并发安全保证。
生产案例
某次大促备战压测时,一个行情聚合服务的下游调用量远超预期,缓存命中率从压测初期的正常水平一路走低。抓堆 dump 分析发现,缓存 HashMap 里堆积了大量「逻辑相等但对象不同」的 key:缓存 key 用的是一个可变 DTO,某段装配代码在 put 之后又调了 setter 更新了参与 hashCode 计算的时间戳字段,之后所有 get 都落在别的桶上。由于 put 持续成功、get 持续未命中,缓存成了只进不出的内存黑洞,堆占用一路膨胀。整改分两步:key 换成不可变的字符串拼接对象,并在代码评审中加入「Map 的 key 类型必须不可变且重写 hashCode/equals」的强制检查项。这类问题的共同特征是功能上「看起来还能用」,只有监控和 dump 能暴露它,值得提前防范。