Java 基础核心复习笔记 (Day 05) —— Map 体系深度解析

1. HashMap：王者归来

HashMap 是 Java 中使用频率最高的键值对容器。理解它，是理解 Java 集合框架的关键。

1.1 底层结构 (JDK 1.7 vs JDK 1.8)

  • JDK 1.7: 数组 + 链表。
    • Entry 数组。即使哈希冲突了，也只是拉一条链表。
    • 缺点：如果黑客故意构造 hash 冲突，链表会变得无限长，查询退化为 O(n)。
  • JDK 1.8: 数组 + 链表 + 红黑树。
    • 当链表长度 > 8 且 数组长度 >= 64 时，链表会转为 红黑树。
    • 优点：查询效率从 O(n) 提升到 O(log n)。

🛠️ 图解：HashMap 内存结构 (JDK 1.8)

1
2
3
4
5
6
7
8
9
10
11
12
       [Node[] table 数组]
       +-----+-----+-----+-----+
Index: |  0  |  1  |  2  | ... |
       +--+--+--+--+--+--+-----+
          |     |     |
          |     |     +-- [Node: K-V] -- [Node: K-V] (链表)
          |     |
          |     +-- [TreeNode] -- [TreeNode] (红黑树结构)
          |             /   \
          |           ...   ...
          |
          +-- null (没有元素)

📝 图解说明: HashMap 就像一个巨大的停车场（数组）。

  1. 每辆车（Key-Value）进来，通过 Hash 算法计算它该停在哪个车位（Index）。
  2. 如果车位是空的，直接停进去。
  3. 如果车位已经有车了（哈希冲突），JDK 1.7 说是“串糖葫芦”（链表），后来的车挂在前面的车后面。
  4. JDK 1.8 说：如果串得太长（超过8个），找车太慢了，我就把它改造成立体停车库（红黑树），这样找车就快多了。

1.2 核心源码解析：tableSizeFor (2 的幂次方)

为什么 HashMap 的容量总是 2 的 n 次方？即使你传了 10，它也会把你改成 16。秘密就在这个方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 作用：给定一个目标容量 cap，返回一个 >= cap 的最小的 2 的幂次方。
 * 例如：输入 10 -> 返回 16；输入 5 -> 返回 8。
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1; // 步骤 A: 防止 cap 本身就是 2 的幂，如果不减 1，最后会翻倍（如 16 变成 32）
    
    // 步骤 B: 核心位运算 —— "抹平低位"
    // 目的：把最高位的 1 后面的所有位都变成 1
    n |= n >>> 1; // 把最高位的 1 右移 1 位，并与原值或运算。结果：最高两位都是 1
    n |= n >>> 2; // 把最高的 2 位 1 右移 2 位... 结果：最高四位都是 1
    n |= n >>> 4; // ... 结果：最高八位都是 1
    n |= n >>> 8; // ...
    n |= n >>> 16;// ... 此时，从最高位 1 开始，后面全变成了 1。
                  // 例如：00100... -> 变成 00111...
    
    // 步骤 C: 最后 + 1，00111... + 1 变成了 01000... (即 2 的幂次方)
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

🤔 为什么要这样？(菜鸟解惑) 想象二进制数 0001 0100 (20)。

  1. 我们希望把它变成 0010 0000 (32)。
  2. 上面的移位操作，就是为了把 1 后面的 0 全部填满变成 1，得到 0001 1111 (31)。
  3. 最后 n + 1，31 + 1 = 32。搞定！

1.3 核心源码解析：hash 方法 (扰动函数)

1
2
3
4
5
6
7
8
9
10
// JDK 1.8 源码
static final int hash(Object key) {
    int h;
    // 如果 key 是 null，hash 值为 0 (所以 HashMap 可以存 null 键)
    // 如果非 null：
    // 1. 拿到 key 自带的 hashCode() (这是一个很大的 int)
    // 2. 将 hashCode 高 16 位移到低 16 位 (h >>> 16)
    // 3. 将两者进行 异或 (^) 运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

🛠️ 图解：为什么要异或？

1
2
3
4
hashCode (32位): 1111 1111 1111 1111 0000 0000 0000 0000
    >>> 16     : 0000 0000 0000 0000 1111 1111 1111 1111
    ---------------------------------------------------
    异或结果    : 1111 1111 1111 1111 1111 1111 1111 1111

解释: HashMap 计算数组下标的公式是 (n - 1) & hash。 如果数组长度 n 很小（比如 16），n-1 就是 1111 (二进制)。 如果不做扰动，只有 hash 值的最后 4 位参与运算，高位全被忽略了，这会导致严重的哈希冲突。 通过 ^ (h >>> 16)，让高 16 位也参与到低位的运算中，增加了随机性，减少了冲突。

🔥 大厂面试通关检查 (HashMap 篇)

Q1: 为什么 HashMap 的长度必须是 2 的幂次方？

A: (这是必考题，回答要分两层)

  1. 为了性能 (位运算替代取模): 我们希望数据均匀分布，通常做法是 hash % length。但是，CPU 做取模运算很慢。如果 length 是 2 的幂次方，那么 hash % length 等价于 hash & (length - 1)。位运算(&)比取模(%)快得多。
  2. 为了分布均匀: length - 1 的二进制位全是 1 (如 16-1=15 -> 1111)。这样在进行 & 运算时，hash 值的最后几位能完全保留下来，每一位都有机会参与索引计算，能最大程度保证散列均匀。如果 length 是奇数，最后一位是 0，那么所有算出来的下标都是偶数，浪费了一半空间。

Q2: 为什么 JDK 1.8 引入红黑树？阈值为什么是 8 和 64？

A:

  • 引入红黑树: 解决哈希冲突导致的链表过长问题。链表查询 O(n)，红黑树 O(log n)。防止发生 Hash DoS 攻击（黑客构造大量相同 hash 值的 key 让服务器 CPU 飙升）。
  • 阈值 8 (树化): 这是一个概率学问题。根据泊松分布，在负载因子 0.75 下，链表长度达到 8 的概率极低（亿分之六）。如果真的到了 8，说明哈希冲突极其严重，必须变树来优化。
  • 阈值 64 (最小数组容量): 如果数组很短（<64），哈希冲突大概率是因为数组太挤了，这时候应该优先扩容（resize），而不是急着变树。变树结构复杂，开销大，扩容能直接解决拥挤问题。

Q3: HashMap 是线程安全的吗？会出现什么问题？

A: 不是线程安全的。

  • JDK 1.7: 在多线程扩容时，采用头插法移动链表元素。如果两个线程同时扩容，可能导致链表中的节点指针互相指，形成死循环 (Infinite Loop)，导致 CPU 100%。
  • JDK 1.8: 改成了尾插法，解决了死循环问题。但是，多线程下仍然存在数据覆盖的问题（两个线程同时判断一个坑位为空，同时写入，后写的覆盖先写的），导致数据丢失。

2. 并发噩梦的终结者：ConcurrentHashMap (CHM)

为了解决 HashMap 的线程不安全，又不想用慢如蜗牛的 Hashtable（全表一把锁），Doug Lea 大神贡献了 CHM。

2.1 结构演进 (JDK 1.7 vs 1.8)

JDK 1.7: 分段锁 (Segment)

  • 核心思想: 既然锁全表太慢，那我就把数组切成一段一段 (Segment)，每段配一把锁。
  • 结构: Segment 数组 + HashEntry 数组 + 链表。
  • 锁: ReentrantLock。默认并发度 16。

🛠️ 图解: 1.7 分段锁

1
2
3
4
5
6
7
Map
 |
 +-- [Segment 0] (锁0) --- [HashEntry 数组] --- 链表
 |
 +-- [Segment 1] (锁1) --- [HashEntry 数组] --- 链表
 |
 ...

JDK 1.8: CAS + synchronized

  • 核心思想: 放弃 Segment，回归 HashMap 的大数组结构。锁的粒度细化到每一个桶 (Node/Head)。
  • 结构: Node 数组 + 链表 + 红黑树。
  • 锁: synchronized 锁住链表/红黑树的头节点。

🛠️ 图解: 1.8 节点锁

1
2
3
4
5
6
7
Map (Node[])
 |
 +-- [Index 0] (空) -> CAS 插入，无锁
 |
 +-- [Index 1] (有数据 Node A) -> synchronized(Node A) { ... } -> 链表
 |
 +-- [Index 2] (红黑树 Root) -> synchronized(Root) { ... } -> 树

📝 图解说明:

  • 1.7: 像是 16 个小的 HashMap 拼在一起，操作之前先判断你在哪个小 Map 里，然后锁住那个小 Map。
  • 1.8: 只要哈希不冲突，大家随便写（CAS 保证）。如果发生冲突（撞车了），只锁住撞车的那一列（头节点），其他列完全不受影响。这是并发度的极限。

2.2 核心源码解析：JDK 1.8 put 方法

这是 CHM 最精华的部分，展示了它是如何利用 CAS 和 synchronized 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException(); // 1. 严禁 null
    int hash = spread(key.hashCode()); // 计算 hash
    int binCount = 0;
    
    // 死循环 (自旋)，直到插入成功为止
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        
        // 情况 A: 表还没初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable(); // 初始化表
            
        // 情况 B: 当前桶位 (Index) 是空的
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 【关键】直接使用 CAS 尝试插入。
            // 如果两个线程同时来，只有一个能成功，失败的会进入下一次循环
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;                   
        }
        
        // 情况 C: 发现正在扩容 (hash == MOVED)
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f); // 帮忙一起扩容 (多线程协同)
            
        // 情况 D: 发生哈希冲突，需要挂链表或红黑树
        else {
            V oldVal = null;
            // 【关键】锁住当前桶的头节点 f
            // 只有操作同一个桶的线程才会互斥，不同桶互不影响
            synchronized (f) {
                if (tabAt(tab, i) == f) { // 双重检查
                    if (fh >= 0) { // 链表操作
                        // ... 遍历链表，插入或覆盖 ...
                    } else if (f instanceof TreeBin) { // 红黑树操作
                        // ... 树操作 ...
                    }
                }
            }
        }
    }
    addCount(1L, binCount); // 增加计数，可能触发扩容
    return null;
}

🔥 大厂面试通关检查 (ConcurrentHashMap 篇)

Q1: JDK 1.7 和 1.8 的 ConcurrentHashMap 实现有什么本质区别？

A: (高频对比题，建议分三点回答)

  1. 数据结构: 1.7 是 Segment 数组 + HashEntry 数组，实现了分段锁；1.8 去掉了 Segment，直接用 Node 数组 + 链表 + 红黑树，结构与 HashMap 一致。
  2. 锁机制: 1.7 使用 ReentrantLock (Segment 继承自它)；1.8 使用 CAS + synchronized。JDK 1.8 中 synchronized 做了大量优化，在低竞争下性能很好，且节省了 Segment 对象的内存开销。
  3. 锁粒度: 1.7 的锁粒度是 Segment（默认为 16，即并发度 16）；1.8 的锁粒度是 Node（Hash 桶），并发度等于数组长度，大幅提升。

Q2: 为什么 ConcurrentHashMap 的 Key 和 Value 不允许为 null，而 HashMap 可以？

A: (参考下文深度解析，简述版)

  • 这是为了避免二义性 (Ambiguity)。
  • 在多线程环境下，如果你 get(key) 返回 null，你无法判断是“这个 key 根本不存在”还是“这个 key 对应的值就是 null”。
  • 在单线程 HashMap 中，你可以用 containsKey(key) 再查一次来确认。但在多线程 CHM 中，两次调用之间 map 可能已经被其他线程改了，所以 containsKey 的结果不可信。为了安全，CHM 直接禁止 null。

Q3: ConcurrentHashMap 能保证复合操作的原子性吗？比如“如果不存在则插入”？

A: 不能保证完全的原子性，必须使用它提供的专用原子方法。

  • 错误写法:

    1
    2
    3
    4
    // 这种写法不是线程安全的！因为 get 和 put 是两个独立动作
    if (map.get(key) == null) {
        map.put(key, value);
    }

  • 正确写法: 使用 putIfAbsent(key, value)。CHM 内部在源码层面对这个方法进行了整体加锁/CAS 处理，保证了“判断+写入”是一个原子操作。

3. 其他 Map 家族成员

3.1 Hashtable

  • 状态: 只有考古学家在用。
  • 特点: 全表一把 synchronized 锁。效率极低。key/value 都不允许 null。

3.2 HashSet 保证不重复原理

  • 本质: HashSet 底层完全就是一个 HashMap。

  • 源码:

    1
    2
    3
    4
    5
    6
    7
    8
    // HashSet 源码
    private static final Object PRESENT = new Object(); // 占位符

    public boolean add(E e) {
        // 调用 map.put，value 存一个固定的 Object (PRESENT)
        // HashMap 的 put 方法：如果 key 存在，会返回旧值；如果不存在，返回 null
        return map.put(e, PRESENT) == null;
    }

  • 解释: 因为 HashMap 的 Key 是唯一的（依赖 hashCode 和 equals），所以 HashSet 的元素也就唯一了。

4. 思考题与深度解析

❓ 深度解析：为什么 ConcurrentHashMap 严禁 null 键值？

题目: 请从并发编程的设计角度，深入分析为什么 ConcurrentHashMap (CHM) 不支持 null key 和 null value，而 HashMap 支持？(500字以上)

答案解析:

这是一个非常经典的架构设计问题，不仅仅关乎代码实现，更关乎并发语义的不确定性。

1. “二义性” (Ambiguity) 问题是核心原因 在 Map 接口中，get(key) 方法如果返回 null，通常有两种含义：

  • 含义 A: 该 key 从未存入过 Map（不存在）。
  • 含义 B: 该 key 存在，但它对应的 value 被显式存为了 null。

2. 单线程环境的可解性 (HashMap) 在 HashMap（单线程环境）中，我们可以通过额外的 containsKey(key) 方法来消除这种二义性：

1
2
3
4
5
6
7
if (map.get(key) == null) {
    if (map.containsKey(key)) {
        // 确认是含义 B：值为 null
    } else {
        // 确认是含义 A：key 不存在
    }
}

因为是单线程，在执行 get 和 containsKey 之间，Map 的数据状态是稳定的，没有人会去修改它。

3. 多线程环境的不可解性 (ConcurrentHashMap) 在并发环境中，情况完全变了。假设 CHM 允许 value 为 null：

  • 线程 T1 调用 map.get(key)，返回了 null。
  • T1 此时无法确定是含义 A 还是 B。
  • T1 试图调用 map.containsKey(key) 来确认。
  • 但在 T1 执行这两步操作的微小时间间隙里，线程 T2 可能横插一脚，删除了这个 key，或者刚刚把这个 key 放入了 Map。
  • 因此，T1 得到的 containsKey 的结果，已经无法印证刚才 get 的结果了。刚才的状态已经“过期”了。这就是并发中的竞态条件。

为了避免这种无法解决的逻辑悖论，Doug Lea（CHM 的作者）决定直接在源头切断——禁止 null。如果你拿到 null，那就只有一种可能：key 不存在。

4. 源码实现的容错性 此外，从源码实现角度看，CHM 在很多地方利用 value == null 来判断节点状态（例如判断节点是否被迁移、是否需要加锁等）。如果允许用户存 null，会极大地增加底层并发控制逻辑的复杂度，容易引入难以排查的 Bug。

5. 总结

  • HashMap 设计用于单线程，可以容忍二义性，通过组合调用解决。
  • ConcurrentHashMap 设计用于高并发，必须消除二义性，保证原子操作的语义清晰。
  • 这也是大多数并发集合（如 ArrayBlockingQueue, CopyOnWriteArrayList）都不允许 null 的共同原因。这是一个为了线程安全和逻辑严谨性所做的设计取舍 (Trade-off)。