HashMap
HashMap 先用哈希值找到键值对所在的位置,再确认键是否相等。它平均 O(1) 的读写成本、对 equals 和 hashCode 的要求、树化和扩容的时机,都来自这条查找路径。只要能顺着一次 get 和 put 讲清楚每一步在做什么,冲突、树化、容量这些追问都能推出来。下文的阈值和容量计算以 OpenJDK 21 为准。
1. 面试核心
先记住这几条,再读正文- HashMap 先用哈希定位桶,再用键引用或
equals确认匹配;get和put走的是同一条路径。卡 · 结构与查找路径 - 哈希分布合理时,每个桶只有少量节点,所以
get与put的平均成本是 O(1)。 - OpenJDK 21 中,普通
put向链表追加第 9 项时请求树化。卡 · 冲突与树化 - 树化还要求桶数组容量至少为 64,小表先扩容,让冲突的节点有机会分散开。卡 · 冲突与树化
- 容量翻倍后,每个节点要么留在原索引,要么移到原索引加旧容量的位置。卡 · 容量与扩容
2. 结构与查找路径
HashMap 的做法是先把候选键缩小到一个桶里,再在桶内逐个确认。桶是底层数组中的一个位置,哈希值决定键落进哪个桶。空桶里没有节点;不同的键落进同一个桶,叫作哈希冲突,冲突的节点用链表或红黑树串起来。
get(key) 的查找路径分四步:
- 计算哈希。非空键先调用
hashCode(),再把高 16 位异或到低 16 位上,这一步叫扰动。桶下标只取哈希的低位,扰动让高位也能影响落点。null 键的哈希固定为 0。 - 用当前容量算出桶下标。
- 在桶内先比较节点保存的哈希,相同再比较键引用,引用不同才调用
equals。 - 找到相等的键就返回值,找不到返回
null。
put(key, value) 沿同一条路径查找。找到相等的键就替换旧值;找不到就插入新节点,然后判断要不要树化或扩容。
Map<Long, User> users = new HashMap<>();
users.put(7L, new User("Lin"));
User user = users.get(7L);
get(7L) 算出的哈希和 put 时相同,所以会进入同一个桶,再通过 equals 认出这个键,拿到之前保存的 User。哈希分布合理时,每个桶只需要检查很少的节点,get 与 put 的平均成本就是 O(1)。冲突严重时,大量键挤在同一个桶里,桶内查找就会变慢。
这个 O(1) 是把 hashCode 和 equals 当作常数成本算的。如果键的哈希计算或相等比较本身很贵,比如很长的字符串或复杂对象,这部分耗时也要算进去。
3. equals 与 hashCode
HashMap 靠 hashCode 找桶、靠 equals 认键,两者必须配合:相等的键必须产生相同的哈希,而哈希相同的键不一定相等。所以自定义键要同时正确实现这两个方法,参与比较的字段在键放进 Map 之后也不能再改。
record UserId(long value) {}
Map<UserId, String> names = new HashMap<>();
names.put(new UserId(7), "Lin");
System.out.println(names.get(new UserId(7))); // Lin
两个 UserId(7) 是不同的对象,但 record 会根据字段自动生成 equals 和 hashCode,所以它们被识别为同一个键。如果只重写了 equals 而没重写 hashCode,两个对象的哈希大概率不同,get 会去另一个桶里找,返回 null。
键放进 Map 之后,如果修改了参与哈希的字段,再算出的哈希就变了。查找要么进入另一个桶,要么在原桶里因为哈希和节点保存的值对不上而直接跳过。结果是即使传入同一个对象引用,也找不到它。
HashMap 允许一个 null 键和多个 null 值,所以 get 返回 null 有两种可能:键不存在,或者键存在但值是 null。单线程下可以用 containsKey 区分,也可以在业务上约定只保存非空值。
4. 冲突与树化
树化是把桶里的链表换成红黑树,用来降低严重冲突时的查找成本。红黑树是一种自平衡的二叉搜索树,插入和删除后能把树高控制在 O(log n)。节点少的时候链表更简单、更省空间;节点持续变多时,才值得为每个节点多存颜色、父子指针这些字段,换来更快的查找。
OpenJDK 21 的树化与退化条件要按操作区分:
TREEIFY_THRESHOLD为 8。普通put向已经有 8 项的链表追加第 9 项时,请求树化。- 桶数组容量达到 64 才真正树化。容量更小时先扩容:扩容让更多哈希位参与定位,原本挤在一起的长链有机会分到不同的桶。
computeIfAbsent、compute和merge数的是桶里已有的节点:已有 7 个、再加入第 8 个时就请求树化,比普通put早一项。- 扩容拆分树桶时,拆出的某一侧节点数不超过 6,就转回链表。
- 普通
remove删除树节点后,会看根节点附近的形状,树小到一定程度就转回链表,源码注释说大约在 2 到 6 个节点之间。通过迭代器删除时不做这项检查,树桶会一直保留到下次扩容拆分。
这些数字是 OpenJDK 21 的实现细节,Map 接口并没有要求所有实现使用相同的阈值。
树化后查找不一定就是 O(log n),前提是能判断要找的键在树的哪一侧。Comparable 是对象声明自身比较顺序的接口。哈希相同、键又没有可用的 Comparable 顺序时,查找只能把两侧子树都搜一遍,最坏情况仍要线性检查候选键。
5. 容量与扩容
容量决定桶的数量,进而影响冲突概率和扩容频率。讨论扩容前,先分清四个概念:
size是当前保存的键值对数量。capacity是桶数组的长度。loadFactor是负载因子,默认 0.75,用来在空间占用和冲突概率之间取舍。threshold是触发扩容的条目数上限,通常是capacity × loadFactor取整数部分。size超过它就扩容。
HashMap 的容量总是 2 的幂,这样 capacity - 1 的二进制低位全是 1。拿它做位掩码(用来选出特定几位的数),一次按位与就能得到桶下标:
index = (capacity - 1) & hash;
比如容量 16 时,capacity - 1 是二进制 1111,下标就是哈希的低 4 位。容量翻倍到 32,掩码变成 11111,多了一位参与定位。所以旧桶里的节点只有两个去向,看的就是新增的那一位:
(hash & oldCapacity) == 0 -> 原索引
(hash & oldCapacity) != 0 -> 原索引 + oldCapacity
迁移时直接使用节点里保存的哈希,不用重新调用每个键的 hashCode()。但它仍然要分配新数组、扫描所有旧桶、调整节点链接,成本随旧容量和节点数增长;负载因子固定、表已经接近满的时候,可以记为 O(n)。
大 Map 扩容时新旧数组会短暂同时存在,内存占用上升,触发扩容的那次 put 也会明显变慢。已知条目数时,提前算好初始容量可以避免反复扩容;但容量预留过大会浪费内存,遍历时也要多扫描空桶。
6. 使用边界
选 HashMap 时还要看两件事:需不需要固定的遍历顺序,会不会被多个线程同时修改。
HashMap 的遍历要扫描整个桶数组,成本与容量加 size 成正比,而且遍历顺序没有保证。需要保留插入顺序可以用 LinkedHashMap,需要按键排序则用 TreeMap 与 TreeSet。
多个线程不加同步地修改 HashMap,可能丢失更新,也可能读到修改到一半的结构,所以共享的可变 HashMap 需要外部同步。换成并发 Map 也不能先 containsKey 再 put,两步之间仍有竞态,应该按需求用 putIfAbsent 或 compute 这类原子方法。
复合操作的实现与边界见 ConcurrentHashMap。
检查能否解释
沿 put/get 解释定位与比较,说明键的相等性、扩容原因和共享修改限制。
说明 HashMap 的 put 和 get 路径。 查看题目与参考回答 →7. 预期条目数与初始容量
预估初始容量时,要把「打算放多少条」换算成「需要多少个桶」。new HashMap<>(100) 里的 100 是桶容量的提示,不是能容纳的条目数。OpenJDK 21 首次分配时会把它向上取整到 2 的幂 128,再乘默认负载因子 0.75,得到阈值 96。所以插入第 97 个不同的键时就会扩容。
Java 21 可以直接用 HashMap.newHashMap(expectedMappings),它按预期条目数和默认负载因子算出合适的容量。Java 17 没有这个方法,可以自己把条目数除以 0.75 再向上取整,传给构造器,构造器会再按 2 的幂调整。
8. 常见问题
8.1 hash 与 equals 的比较顺序
先比哈希,因为比较两个整数很便宜,哈希不同的键可以直接排除,省掉一次 equals。哈希相同可能只是冲突,所以还要比较键引用,引用不同再调用 equals 确认。
8.2 遍历顺序的约定
HashMap 不保证遍历顺序。同样的键在同样的环境下,结果有时看起来很稳定,但扩容、键的哈希变化或 JDK 实现调整都会改变顺序。业务需要固定顺序时,应该换用有顺序约定的 Map。
8.3 链表长度与树化条件
OpenJDK 21 的普通 put 向链表追加第 9 项时请求树化,但不一定真的树化:桶数组容量小于 64 时先扩容,达到 64 才把链表转成树桶。
9. 面试题卡片
10. 参考资料
来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明