Java 从入门到精通（九）：集合框架（下）——Map 家族与 HashMap 源码剖析

上一篇我们把 List 与 Set 的底层结构、扩容机制、fail-fast 迭代器讲透了。本篇进入 Map 家族——这是 Java 面试中出现频率最高、源码最值得逐行精读的一块。全文代码均在 JDK 8 与 JDK 17 上实测通过，涉及版本差异的地方会明确标注。建议把文中的源码片段对照你本地 rt.jar / src.zip 里的 java.util.HashMap 一起读，尤其是 putVal、resize、treeifyBin 这三段，读完你会明白”为什么容量必须是 2 的幂””为什么树化阈值是 8”这些结论根本不需要死记硬背。另外文中会出现大量位运算，看不懂的地方先把二进制写出来。

一、Map 家族全景

1.1 八种 Map 实现的语义与适用场景

Map 不是 Collection 的子接口，它是独立的顶层接口，存储的是”键到值”的映射（key-value mapping）。JDK 提供了八种常用实现，它们的核心差异体现在四个方面：是否有序、是否允许 null、底层数据结构、是否线程安全。

一句话选型口诀：默认 HashMap，要顺序用 LinkedHashMap，要排序用 TreeMap，要并发用 ConcurrentHashMap，枚举 key 用 EnumMap，其余都是特定场景的专用工具。

1.2 Map 接口的常用方法与默认方法

JDK 8 为 Map 接口引入了一批默认方法（default method），它们把”取不到就放一个”这类样板代码压缩成一行。

注意 computeIfAbsent 与 putIfAbsent 的关键区别：putIfAbsent 的第二个参数是已经算好的值，无论是否需要都会被求值；computeIfAbsent 的第二个参数是函数，只有 key 不存在时才执行。所以当构造 value 代价很高（比如查库、建集合）时，必须用 computeIfAbsent。

1.3 用 merge 做词频统计

merge 是为”计数聚合”量身定做的方法，一行顶过去五行。

二、哈希表原理

2.1 哈希函数与哈希冲突

哈希表的理想模型是：给一个 key，通过哈希函数 h(key) 直接算出数组下标，一次寻址拿到值，时间复杂度 O(1)。但现实有两个绕不开的问题：

1. 哈希函数不可能单射：key 的取值空间远大于数组长度，必然存在 k1 != k2 但 h(k1) == h(k2)，这就是哈希冲突（collision）。
2. 数组不能无限大：如果开一个 40 亿长度的数组来装所有可能的 key，空间直接爆炸。

于是工程上必须做两件事：设计分布均匀的哈希函数，以及选择冲突解决策略。

冲突解决有两大流派：

HashMap 选择链地址法，并在 JDK 8 引入红黑树作为”链表过长时的兜底”，形成数组 + 链表 + 红黑树的三段式结构：数组负责 O(1) 定位，链表负责解决少量冲突，红黑树负责防止恶意哈希攻击把单次操作退化成 O(n)。

2.2 装载因子与 O(1) 的推导

装载因子（load factor）定义为 α = 元素个数 / 数组容量。在链地址法下，一次成功查找的平均探测次数约为 1 + α/2，一次失败查找约为 α。也就是说查找代价只与 α 有关，与元素总量无关——这正是 O(1) 的来源，注意它是摊还期望意义下的 O(1)，不是最坏情况。

那为什么 DEFAULT_LOAD_FACTOR = 0.75f？这是空间与时间的折中点：

• α 太小（如 0.5）：冲突极少，但一半数组空着，内存浪费严重，且扩容更频繁；
• α 太大（如 1.0）：数组利用率高，但链表迅速变长，查找退化，且泊松分布下出现长链的概率陡增；
• 0.75 恰好让”链表长度超过 8”的概率降到千万分之一量级（下一节会给数据），同时数组利用率尚可。JDK 源码注释里明确写了这是”a decent tradeoff between time and space costs”。

2.3 扰动函数：让高 16 位参与运算

HashMap 没有直接用 key.hashCode() 取模，而是先做了一次扰动（disturbance）：

为什么要 h ^ (h >>> 16)？因为真正的下标计算是 (n - 1) & hash。当数组容量 n 较小时（默认 16），n - 1 = 15 = 0b1111，只有低 4 位参与运算，高 28 位全部被丢弃。如果 key 的 hashCode 只有高位变化（这非常常见，比如 Float、Long 的低位常常是 0，或者自定义对象只在高位写入了 ID），所有元素就会挤在同一个槽里。扰动函数把高 16 位右移后与低 16 位异或，把高位的随机性”混入”低位，用一次异或（单周期指令）换来了低位雪崩效应，性价比极高。

用实验直观验证一下：

JDK 7 的扰动函数做了 4 次异或（把高低位反复混合），JDK 8 简化为 1 次。原因有二：一是 JDK 8 引入了红黑树，即使低位碰撞严重也有 O(log n) 兜底；二是实测表明 1 次异或对常见 hashCode 已经足够，多做无谓的 CPU 消耗。

2.4 为什么容量必须是 2 的幂

这是最经典的一道题，答案是为了用位运算取代取模，而位运算的成立需要 n 是 2 的幂。

数学等价性证明：设 n = 2^k，则 n - 1 = 2^k - 1，其二进制为 k 个连续的 1（例如 k=4 时，n-1 = 15 = 0b1111）。对任意非负整数 h，把它写成 h = q · 2^k + r，其中 0 ≤ r < 2^k（这正好是带余除法定义，r 为余数）。由于 2^k 的二进制是第 k 位为 1、后面全 0，所以 q · 2^k 的低 k 位全为 0，而 r 恰好占据低 k 位。因此：

也就是说，当且仅当 n = 2^k 时，h & (n-1) 与 h % n 完全等价。若 n 不是 2 的幂（比如 n=10），n-1 = 9 = 0b1001，第 1、2 位恒为 0，那些位永远是 0，槽位 2、3、6、7 永远用不上，分布直接崩坏。

性能上，在 x86 上 & 是 1 个时钟周期，而 % 需要调用整数除法指令，约 20~40 个周期。HashMap 每次 get/put 都要算一次下标，这是热路径上的关键优化。

容量取 2 的幂还带来一个额外红利，这是 JDK 8 resize 能做到”免重哈希”的前提：容量从 oldCap 翻倍到 2·oldCap，相当于多参与了一位（第 k 位）。因此每个元素的新下标只有两种可能——原位 j（第 k 位为 0）或 j + oldCap（第 k 位为 1）。判断条件就是 (e.hash & oldCap) == 0，一次与运算即可，不必重新调用 hash()。这个巧思在 3.5 节展开。

三、HashMap 源码精读（JDK 8）

3.1 核心字段与常量

table 用 transient 修饰，因为 JDK 自己实现了 writeObject/readObject，只序列化有效节点以节省空间。modCount 记录结构性修改（put、remove、clear），迭代器创建时会拷贝一份 expectedModCount，遍历期间两者不等就抛 ConcurrentModificationException。

3.2 tableSizeFor：向上取整到 2 的幂

构造方法传入的 initialCapacity 可以是任意正整数，HashMap 必须把它”规整”为不小于它的最小 2 的幂。

原理是位扩散：只要最高位有一个 1，5 次”或右移”就能把它右边所有位全部填成 1，此时 n 的形如 0b00...0111...1，再加 1 就得到 0b00...1000...0，即大于等于原 cap 的最小 2 的幂。先 cap - 1 是为了处理 cap 恰好是 2 的幂的边界：若不减 1，传入 16 会得到 32，白白浪费一半空间。

需要强调：tableSizeFor 只在构造时把结果赋给 threshold，真正的数组要等到第一次 put 时由 resize() 分配。这是 HashMap 的懒加载（lazy init）设计，避免 new HashMap<>(1000) 却一个元素都不放的内存浪费。

3.3 putVal：一次 put 的完整生命周期

这是 HashMap 最重要的方法，逐行拆解：

判断 key 相等的条件是 p.hash == hash && (p.key == key || key.equals(k))，两个条件缺一不可：先比 hash 是为了快（一个 int 比较就能过滤掉绝大多数不等的 key），再比 equals 是为了准（hash 相等不代表对象相等）。这也解释了为什么重写 equals 必须重写 hashCode——否则两个逻辑相等的对象 hash 不同，会被当成两个 key。

3.4 treeifyBin 与泊松分布：阈值为什么是 8

树化阈值的选取不是拍脑袋，JDK 源码注释里给出了依据：在装载因子 0.75 下，单个桶中元素个数服从参数约为 0.5 的泊松分布，长度达到 8 的概率仅约千万分之六。

结论很清晰：正常 hashCode 下链表长度几乎不可能到 8。一旦到了，几乎可以断定是哈希攻击（恶意构造同 hash 的 key）或 hashCode 实现极差，此时树化把 O(n) 降到 O(log n) 是必要的防护。

两个细节：

• 为什么退化阈值是 6 而不是 8？ 留出 2 的缓冲带（ hysteresis，滞后区间）。若在 8 附近反复增删，没有缓冲就会频繁链表↔树互转，每次转换都要重建结构，代价很高。
• 为什么还要 MIN_TREEIFY_CAPACITY=64？ 表容量小于 64 时，链表变长的根因往往是表太小而非 hash 太差，此时一次 resize() 就能把长链一分为二，比建树划算得多。

3.5 resize：JDK 8 的高低位拆分

扩容是 HashMap 最精妙的部分。JDK 8 的核心优化是：不需要重新计算 hash，只用一个与运算就能把一条链拆成两条。

为什么容量翻倍能让元素均匀拆分？ 因为容量从 oldCap = 2^k 变为 2^(k+1)，掩码从 2^k - 1（k 个 1）变为 2^(k+1) - 1（k+1 个 1），多参与了恰好一个新的二进制位——也就是 oldCap 那一位（值为 2^k）。对于原下标为 j 的元素，新下标只可能是：

• 若 hash & oldCap == 0（该位为 0）→ 新下标仍为 j；
• 若 hash & oldCap != 0（该位为 1）→ 新下标为 j | oldCap，即 j + oldCap。

举例：oldCap = 16，某 key 的 hash 低 5 位为 10101。原掩码 15 = 0b01111，下标 = 0b0101 = 5；新掩码 31 = 0b11111，新下标 = 0b10101 = 21 = 5 + 16。一次扩容相当于”把一个桶按第 k 位劈成两半”，且由于 hash 的随机性，两半元素数量期望各占一半——扩容后链表长度直接减半，这正是扩容能降低冲突的根本原因。

树节点也有对应的 TreeNode.split()，逻辑相同，多了一步判断拆分后的链表长度是否 ≤ UNTREEIFY_THRESHOLD(6)，是则 untreeify 退化回链表。

3.6 getNode 与 removeNode

removeNode 的结构与 getNode 完全对称，只是多了一句 ++modCount 和 --size，以及在红黑树删除后调用 moveRootToFront 保证桶头始终是树根。删除后不会自动退化成链表，退化只发生在扩容的 split 阶段（JDK 8 的行为）。

3.7 JDK 7 头插法与并发死循环推演

这是 Java 面试史上最著名的一道题。JDK 7 的扩容用 transfer 方法，采用头插法且不加锁：

头插法本身在单线程下没问题（还能利用缓存局部性），但它会反转链表顺序。一旦两个线程同时扩容，反转 + 共享引用就会织出环。

环形链表形成过程推演（设旧桶中有 A → B → C 三个节点，它们在新表中仍映射到同一桶）：

1. 线程 T1 执行到 ① 处挂起，此时 e = A，next = B；
2. 线程 T2 完整跑完 transfer。由于头插反转，新桶中的顺序变为 C → B → A，即 C.next = B、B.next = A、A.next = null。注意此时是同一个堆内存上的节点对象，T1 持有的 e/next 引用依然指向 A 和 B；
3. T1 恢复执行，e = A，next = B。执行 ②：A.next = newTable[i]，而 newTable[i] 现在是 C，于是 A.next = C；执行 ③：newTable[i] = A；执行 ④：e = B；
4. T1 下一轮，next = B.next，而 B.next 在 T2 的处理后指向 A，于是 next = A。执行 ②：B.next = A（已经是了）；③：newTable[i] = B；④：e = A；
5. T1 再下一轮，next = A.next，而第 3 步已经把 A.next 改成了 C，所以 next = C。执行 ②：A.next = C；③：newTable[i] = A；④：e = C；
6. 此时结构为 newTable[i] = A，A.next = C，C.next = B，B.next = A——A → C → B → A，环形成了。

后续任何一次 get() 命中这个桶，就会在环里无限循环，while (e != null) 永不终止，CPU 直接打满 100%。这就是传说中的”HashMap 并发死循环导致 CPU 100%”。同时因为两个线程互相覆盖 newTable[i]，还会造成数据丢失。

JDK 8 改成尾插法，扩容时保持链表原有顺序（preserve order 注释即来源于此），从根源上消除了成环的可能。但必须强调：JDK 8 的 HashMap 依然不是线程安全的，它只是把”死循环”降级成了”数据覆盖/丢失”，多线程场景仍然要 ConcurrentHashMap。

面试时最容易答错的一点：JDK 8 修复的不是线程安全问题，只是环形链表。多线程同时 put 仍会丢数据（两个线程同时算出同一槽位为空，后写的覆盖先写的）；size 字段非 volatile、非原子，计数会偏小；put 与 get 并发还可能读到半初始化状态。结论不变——并发用 ConcurrentHashMap，或者外部加锁。

四、HashMap 使用禁忌与实战

4.1 key 的选择：为什么推荐 String / Integer

String 和 Integer 是最理想的 key，原因有三：不可变（immutable）、hashCode 缓存且分布良好、equals 语义稳定。

可变对象作 key 是一场灾难——对象状态改变后 hashCode 随之改变，导致它”躺在错误的桶里”，get 永远找不到，remove 也删不掉，最终内存泄漏。

铁律：作为 key 的对象必须不可变，或者至少保证参与 equals/hashCode 的字段在放入 Map 后不再改变。 如果非要用可变对象，推荐用其中的不可变字段（如 id）单独作为 key。

4.2 重写 equals 必须重写 hashCode

这不是”建议”，而是 Object.hashCode() 的通用契约：

1. 同一对象多次调用 hashCode() 必须返回相同值（前提是用于 equals 比较的信息未被修改）；
2. a.equals(b) 为 true，则 a.hashCode() == b.hashCode() 必须成立；
3. a.hashCode() == b.hashCode() 不要求 a.equals(b)（允许哈希碰撞）。

只重写 equals 会违反第 2 条：两个逻辑相等的对象 hash 不同，HashMap 会把它们放进不同桶，导致 map.get(new User(1,"Tom")) 返回 null，或者出现”逻辑上重复”的两个条目。

JDK 7+ 可以直接用 Objects.hash(f1, f2, ...)，它内部就是 Arrays.hashCode，等价但更简洁（代价是会创建 Object[]，极端热路径可手写）。

4.3 遍历方式与性能对比

四种遍历方式里，entrySet 明显优于 keySet——后者对每个 key 都要再查一次表，等于做了 N 次 getNode。

结论：只读遍历用 forEach 最快；需要边遍历边删除用 Iterator.remove() 或 JDK 8 的 removeIf；永远不要在 for-each 里调用 map.remove(k)。另外在 key 为 null 或 value 很大时，values() 与 keySet() 视图仍有价值——它们是零拷贝的视图，修改会反映到原 Map。

4.4 初始容量设置与内存开销

反复扩容的代价是：一次 resize 要重建数组并搬迁全部元素。如果预知要放 N 个元素，应在构造时就给出容量：

常见误区：把”预计元素个数”直接传给构造器。new HashMap<>(1000) 的实际阈值是 1024 * 0.75 = 768，放 1000 个元素仍会扩容一次。正确写法是 new HashMap<>((int)(1000 / 0.75f) + 1)，即 1334。阿里巴巴 Java 开发手册也强制要求”集合初始化时指定初始值大小”。

内存开销估算（64 位 HotSpot，开启压缩指针 -XX:+UseCompressedOops）：

粗略公式：总开销 ≈ 32 × size + 4 × capacity。存 100 万个 Entry，Node 本身约 32 MB，数组约 4~8 MB。所以在大容量场景下，HashMap 的空间放大率可达 4~8 倍，这时应考虑 long 原生类型 map（fastutil、Eclipse Collections）或改用数组/堆外内存。

五、LinkedHashMap：顺序与 LRU 缓存

5.1 双向链表的维护与三个钩子

LinkedHashMap 继承 HashMap，几乎不重写核心算法，而是通过 HashMap 预留的三个钩子方法注入顺序语义：

• afterNodeAccess(Node e)：节点被访问（get/put 覆盖）后调用，把节点移到链表尾部（仅 accessOrder=true 时）；
• afterNodeInsertion(boolean evict)：插入后调用，配合重写 removeEldestEntry 可实现自动淘汰；
• afterNodeRemoval(Node e)：删除后调用，从双向链表摘除。

它在 Node 基础上扩展了 before/after 两个指针，并维护 head（最老）与 tail（最新）两个引用。代价是每节点多 8 字节、每次操作多几次指针赋值，换来的是可预测的迭代顺序——HashMap 的迭代顺序是不确定的，扩容后会变。

5.2 用 accessOrder 实现 LRU 缓存

写 LRU 有两个坑：一是 accessOrder 忘了传 true，退化成 FIFO；二是 removeEldestEntry 里用 >= 而不是 >，导致容量永远差 1。

LRU 与 LFU 的区别：LRU（Least Recently Used）只看”最后一次访问时间”，淘汰最久没被碰过的；LFU（Least Frequently Used）看”访问总次数”，淘汰访问频率最低的。LRU 对”偶发批量扫描”不友好（一次全表扫描会把热数据全挤走），LFU 则对”历史热点”不友好（老热点永远不淘汰）。生产环境（Caffeine、Redis）一般使用 W-TinyLFU 或 LRU + 分段（Segmented LRU） 来兼顾两者。LinkedHashMap 只能实现 LRU，要实现 LFU 需要自己维护频次表或使用 Caffeine。

另外必须提醒：这个 LRU 不是线程安全的。多线程场景要么用 Collections.synchronizedMap 包裹（但迭代仍要手动加锁），要么直接用 Caffeine/Guava Cache。

六、TreeMap：有序映射与范围查询

6.1 红黑树的五条性质

TreeMap 底层是红黑树（Red-Black Tree），一种自平衡二叉查找树。它必须满足五条性质：

1. 每个节点要么是红色，要么是黑色；
2. 根节点是黑色；
3. 所有叶子节点（NIL 空节点）是黑色；
4. 红色节点的两个子节点都必须是黑色（不能有连续的红节点）；
5. 从任一节点到其所有后代 NIL 节点的路径上，黑色节点数量相同（黑高一致）。

性质 4 与性质 5 共同约束了树的形态：最长路径不超过最短路径的 2 倍，因此树高始终为 O(log n)，保证了 get/put/remove 的最坏时间复杂度是 O(log n)。红黑树不像 AVL 树那样追求严格平衡（AVL 要求左右子树高度差 ≤ 1），它的旋转次数更少，插入删除性能更稳定，这也是 std::map、Linux 内核、HashMap 的树化桶都选择它的原因。

6.2 有序性操作

TreeMap 的 key 不能为 null（自然排序下会抛 NullPointerException），因为 compareTo 无法与 null 比较。若必须支持 null key，需要传入一个能处理 null 的 Comparator，此时 null 会被当作正常值参与排序——但这是”第二棵树”的语义，官方并不推荐。

6.3 Comparable 与 Comparator 的选型

TreeMap 有两种排序来源：

最后一个陷阱在实战中极常见：TreeMap 判断 key 相等的准则是 compare(a,b) == 0，与 equals 完全无关。如果 Comparator 写得比 equals 宽松（比如只比 name 不比 score），就会出现”看起来不同的两个对象被当成同一个 key”。官方建议 compareTo 与 equals 保持一致（SortedMap 文档明确写了这点），不一致时应显式注明。

性能上，TreeMap 的 get/put/remove 为 O(log n)，且没有哈希计算、没有扩容、没有红黑树与链表的转换，因此元素量不大（几千以内）且需要排序时，TreeMap 往往是比”HashMap + 排序”更省心的选择。排序稳定性：TreeMap 的迭代顺序完全由比较器决定，只要比较器是确定的，顺序就是确定且稳定的。

七、Hashtable、Properties 与线程安全 Map

7.1 Hashtable 为什么被淘汰

Hashtable 是 JDK 1.0 的遗留类，被淘汰有三个硬伤：

1. 全表锁：几乎所有 public 方法都用 synchronized 修饰，锁的是整个 this，并发度为 1。100 个线程同时读都会串行；
2. 不允许 null：key 与 value 都不能为 null，否则 NullPointerException（它的 hash 直接调用 key.hashCode()）；
3. API 老旧：继承自 Dictionary 抽象类而非 Map 体系（JDK 2 才被改造适配 Map），还有 elements()、keys() 这种返回 Enumeration 的历史方法，无法与 Collections 工具类无缝配合。

另外它的默认容量是 11（不是 2 的幂），扩容是 2n+1，用的是取模而非位运算，性能也不如 HashMap。

7.2 Collections.synchronizedMap 的装饰器陷阱

Collections.synchronizedMap 返回的是 SynchronizedMap 内部类，它持有 mutex 对象（默认就是自身），把每个方法包在 synchronized (mutex) 里。它解决的是”单个方法的原子性”，解决不了”多个方法组成的复合逻辑的原子性”，也解决不了迭代期间的一致性。

7.3 ConcurrentHashMap 的演进

ConcurrentHashMap 的锁粒度经历了两代演进：

JDK 8 的思路是把锁的粒度降到单个桶：插入时先 CAS 尝试写入空桶；失败说明有冲突，就 synchronized (f) 锁住桶头节点再挂链表。由于同一时刻竞争同一个桶的线程极少，实际并发度远高于 JDK 7 的固定 16。size() 用 CounterCell 分片计数（类似 LongAdder），避免单点竞争。扩容还支持多线程协同迁移（ForwardingNode + transferIndex），这是另一个大话题，我们留到并发篇展开。

为什么推荐用 ConcurrentHashMap 替代 Hashtable：并发度从 1 提升到接近桶数；读操作完全无锁；提供 putIfAbsent/computeIfAbsent/merge 等原子复合操作，不用外部加锁；迭代器是弱一致性的，不会抛 ConcurrentModificationException，适合大 map 的遍历。唯一代价是不能存 null 值——这是刻意的取舍，因为 get 返回 null 必须能无歧义地表示”key 不存在”。

Properties 是 Hashtable 的子类，专用于读写 .properties 配置：

注意 Properties 的 getProperty 返回 String，而继承自 Hashtable 的 get/put 返回 Object，不要混用——用 put 存非 String 值会导致 store() 写不出来。

八、高频面试题解析

1. HashMap 的容量为什么必须是 2 的幂？
   为了用 (n-1) & hash 取代 hash % n。当 n = 2^k 时，n-1 的二进制是 k 个连续的 1，按带余除法 h = q·2^k + r，q·2^k 低 k 位全 0，故 h & (2^k-1) = r = h % 2^k，两者严格等价。位运算比取模快一个数量级。副产品是扩容时可用 (e.hash & oldCap) 免重哈希拆分。
2. HashMap 什么时候扩容？扩容做什么？
   当 ++size > threshold（threshold = capacity × loadFactor）时扩容为 2 倍。JDK 8 的 resize 分三步：计算新容量与新阈值、新建数组、搬迁元素。搬迁时对每个桶按 (e.hash & oldCap) == 0 拆成低位链（留原位）和高位链（移到 j + oldCap），链表保持原顺序（尾插），树节点走 split，拆分后长度 ≤ 6 则退化成链表。
3. 树化阈值为什么是 8，退化为什么是 6？
   源码注释依据泊松分布：装载因子 0.75 下单桶元素数达 8 的概率约 6e-8，正常 hashCode 几乎不可能出现，出现即说明哈希被恶意攻击，需要红黑树把 O(n) 降到 O(log n)。退化取 6 而非 8 是为了留出滞后区间，避免在阈值附近频繁互转。
4. 为什么还有个 MIN_TREEIFY_CAPACITY = 64？
   表容量 < 64 时链表变长的根因通常是”表太小”，此时一次 resize 就能把长链劈成两半，代价远低于建树。所以 treeifyBin 里先判断容量，不够就只扩容不树化。
5. JDK 7 的 HashMap 为什么会在并发下死循环？
   JDK 7 的 transfer 用头插法迁移，会反转链表。两个线程同时扩容时，T2 先完成使链表变为 C→B→A，T1 恢复后按自己持有的旧引用继续头插，最终让 A.next 指回 C，形成 A→C→B→A 的环。此后任何命中该桶的 get 都会在 while (e != null) 里无限循环，CPU 100%。JDK 8 改为尾插法保留原序，从根上消除了成环。
6. JDK 8 的 HashMap 线程安全了吗？
   没有。只是把”死循环”降级为”数据覆盖丢失”。多线程同时 put 同一空槽会互相覆盖；size++ 非原子导致计数偏小；扩容时也可能丢数据。并发场景请用 ConcurrentHashMap。
7. 装载因子为什么是 0.75？
   时间与空间的折中。链地址法下查找代价约为 1 + α/2，α 越大冲突越多；但 α 过小则数组利用率低、扩容频繁。0.75 使”链表长度 ≥ 8”的概率降到千万分之一，同时空间利用率可接受，源码注释称其为 “a decent tradeoff”。
8. 重写 equals 为什么必须重写 hashCode？
   Object.hashCode 契约规定 a.equals(b) == true ⇒ a.hashCode() == b.hashCode()。只重写 equals 会破坏该契约，导致两个逻辑相等的对象算出不同下标，HashMap 把它们存成两条记录，get 返回 null。反过来只重写 hashCode 不重写 equals 同样错误。
9. HashMap 的 key 可以为 null 吗？Hashtable 和 ConcurrentHashMap 呢？
   HashMap 允许一个 null key（hash() 中特判为 0，固定落在 table[0]）和多个 null value。Hashtable 与 ConcurrentHashMap 都不允许 null key/value，因为它们的 get 语义要求”返回 null 无歧义地表示 key 不存在”，并发环境下若允许 null 就无法区分”值为 null”和”不存在”。
10. put 方法的返回值是什么？
    若 key 原本不存在，返回 null（新增）；若 key 已存在，返回被覆盖的旧值。所以不能用 put 返回 null 来判断”原来有没有这个 key”，正确做法是先 containsKey，或用 putIfAbsent。
11. computeIfAbsent 与 putIfAbsent 有什么区别？
    putIfAbsent(key, value) 的 value 是已计算好的值，无论是否需要都会被求值，构造昂贵时白白浪费；computeIfAbsent(key, Function) 只在缺失时才调用函数，且返回的是当前（新计算或已有的）value。另外 computeIfAbsent 的函数里不能对本 map 做递归修改，否则可能 ConcurrentModificationException 或死锁。
12. HashMap 与 TreeMap、LinkedHashMap 如何选型？
    默认 HashMap（O(1)，无序）；需要保持插入顺序或做 LRU 用 LinkedHashMap（accessOrder=true + removeEldestEntry）；需要按键排序或做范围查询（floorKey/ceilingKey/subMap）用 TreeMap（O(log n)，key 不能为 null）。枚举 key 用 EnumMap，并发用 ConcurrentHashMap。
13. HashMap 的遍历为什么推荐 entrySet 而不是 keySet？
    keySet 遍历后还要对每个 key 调 get(k)，等于多做 N 次哈希定位与比较，时间复杂度从 O(n) 变成”N 次 O(1) 但常数翻倍”。entrySet 直接拿到 key 与 value，最快的是 JDK 8 的 forEach(BiConsumer)，没有迭代器对象开销。
14. 已知要存 1000 个元素，HashMap 初始容量应该设多少？
    设 1334（(int)(1000 / 0.75f) + 1），HashMap 内部会 tableSizeFor 向上取整到 2048。直接传 1000 会导致实际阈值 768 < 1000，仍扩容一次。

本篇我们把 Map 家族从接口语义一路读到 JDK 8 的字节码级实现：容量取 2 的幂的数学证明、扰动函数的雪崩效应、tableSizeFor 的位扩散、resize 的高低位拆分、泊松分布支撑的树化阈值，以及 JDK 7 头插法成环的完整推演。下一篇（第十篇）我们将进入并发编程的世界：JMM 内存模型、happens-before、volatile 的可见性与禁止重排序、synchronized 的锁升级（偏向锁→轻量级锁→重量级锁）、CAS 与 AQS 原理，以及本篇预告的 ConcurrentHashMap 多线程协同扩容的完整实现。建议在此之前，把本文的 putVal 与 resize 源码对照本地 src.zip 再精读一遍，那是理解整个并发容器体系的基石。