跳至主要內容

集合 - Map与并发容器

硅碳合伙人大约 30 分钟Java基础HashMapConcurrentHashMapTreeMap

开篇：为什么 HashMap 是面试的宠儿？

如果 Java 面试只能考一道题，那大概率就是 HashMap。不夸张地说，HashMap 几乎是每场 Java 面试的"必考嘉宾"。原因很简单：它短短几千行代码里，浓缩了数组、链表、红黑树、哈希算法、位运算、扩容策略等一系列数据结构与算法的精华，堪称一部"微型教科书"。

更重要的是，HashMap 的设计思路直接影响着我们的日常编码。你每天写的 map.put(key, value) 背后到底发生了什么？为什么多线程下它会出问题？什么时候该换成 ConcurrentHashMap？搞懂这些问题，不仅面试能过关，日常写代码也能少踩很多坑。接下来，我们就从底层原理出发，把 Map 家族彻底拆解一遍。

一、HashMap 的工作原理

1.1 数组 + 链表 + 红黑树

先用一个生活类比来理解 HashMap 的结构。

想象你有一本字典。字典的"目录页"就是一个数组，每个页码对应一个位置。当你要查一个词的时候，先通过拼音（hash）算出它在哪一页（数组下标），然后翻到那一页去找。

但有时候，两个词的拼音恰好对应到同一页（哈希冲突），这时候同一页上就会有多个词条排成一列 -- 这就是链表。而当同一页上的词条太多时（超过 8 个），字典就会把这一页的内容重新整理成一棵便于快速查找的树 -- 这就是红黑树。

用技术语言来说，JDK 1.8 的 HashMap 底层结构是 数组 + 链表 + 红黑树：

// HashMap 的核心数组（桶数组）
transient Node<K,V>[] table;

// 链表节点
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;   // key 的 hash 值（扰动后的）
    final K key;       // key 不可变
    V value;           // value 可变
    Node<K,V> next;    // 指向下一个节点（链表结构）
}

关键参数一览：

参数默认值含义
初始容量（capacity）16桶数组的初始长度
负载因子（loadFactor）0.75触发扩容的装填比例
树化阈值（TREEIFY_THRESHOLD）8链表长度达到 8 且数组长度 >= 64 时转红黑树
退化阈值（UNTREEIFY_THRESHOLD）6红黑树节点数 <= 6 时退回链表
最小树化容量（MIN_TREEIFY_CAPACITY）64数组长度不够 64 时优先扩容而不是树化

这里有个细节值得注意：HashMap 采用了延迟初始化策略。当你 new HashMap() 的时候，内部的 table 数组并不会立刻创建。只有等到第一次 put 的时候，才会真正分配内存。这样做的好处是，如果你创建了 HashMap 却没有用，就不会浪费内存。

1.2 put 流程详解

当你调用 map.put("name", "张三") 时，HashMap 内部经历了以下步骤：

先来看入口方法：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

这一行代码看似简单，但暗藏玄机 -- 它先调用 hash(key) 对 key 的 hashCode 做了一次扰动计算（后面会详细讲），然后才把结果传给 putVal。

putVal 方法的核心步骤：

  1. 延迟初始化：如果 table 为 null 或长度为 0，先调用 resize() 创建桶数组
  2. 定位桶：用 (n - 1) & hash 计算桶下标（等价于取模，但更快）
  3. 桶为空：直接创建新 Node 放入
  4. 桶不为空：检查首节点的 key 是否相同（先比 hash，再比 equals）。相同则准备覆盖
  5. 红黑树：如果首节点是 TreeNode，走红黑树的插入逻辑
  6. 链表：遍历链表找到尾部插入。遍历过程中如果发现相同 key 则覆盖。如果插入后链表长度达到 8，调用 treeifyBin() 尝试树化
  7. 扩容检查：插入完成后，如果元素总数超过阈值（capacity * loadFactor），触发扩容

关键变化：JDK 1.7 vs 1.8

特性JDK 1.7JDK 1.8
数据结构数组 + 链表数组 + 链表 + 红黑树
插入方式头插法尾插法
扩容 rehash全量重新计算高位判断，免重算
哈希扰动4 次移位 + 5 次异或1 次移位 + 1 次异或
扩容时机先判断再插入先插入再判断

get 方法

get 方法的逻辑相对简单，但也值得仔细看看：

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {

        // 1. 检查首节点是否匹配（大部分情况下直接命中）
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;

        if ((e = first.next) != null) {
            // 2. 如果是红黑树，走树的查找 O(log N)
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 3. 否则遍历链表逐个比较 O(N)
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

注意查找时的判断顺序：先比 hash 值（int 比较，极快），hash 相同再比 equals。这种"先快后慢"的策略大大减少了 equals 方法的调用次数。

remove 方法

remove 方法先定位到目标节点，然后根据节点位置做不同的删除操作：

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

删除时的三种情况：

  • 桶的首节点：直接让下一个节点顶上，tab[index] = node.next
  • 链表中间节点：前驱节点的 next 指向后继节点，p.next = node.next
  • 红黑树节点：红黑树的删除操作，删除后如果节点数过少，可能触发退化为链表

HashMap 还提供了一个 key-value 都匹配才删除的重载方法：

// 只有 key 和 value 都匹配才会删除
public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true, true) != null;
}

HashMap 如何定位 key？

HashMap 定位 key 的过程分两步：

  1. 定位桶：通过 (table.length - 1) & hash(key) 算出桶下标
  2. 桶内查找：通过 key.equals(existingKey) 逐个比较

所以，正确使用 HashMap 的前提是：key 对象必须正确实现 hashCode() 和 equals() 方法。如果 hashCode 不一致，会定位到错误的桶；如果 equals 不正确，会在桶内找不到匹配项。

这也是为什么建议用 String、Integer 等不可变对象做 key -- 它们的 hashCode 和 equals 已经由 JDK 正确实现，并且值不可变，不会出现"放进去就找不到"的问题。

HashMap 的 value 可以为 null 吗？

可以，但要小心一个陷阱：

Map<String, Object> map = new HashMap<>();
map.put("key", null); // 合法，value 为 null

if (map.containsKey("key")) {
    String value = (String) map.get("key"); // 返回 null
    System.out.println(value.length());      // 空指针异常！
}

containsKey 返回 true，但 get 返回 null -- 因为存的就是 null。后续的业务代码如果没有做 null 检查就会抛 NPE。这也是 ConcurrentHashMap 禁止 null 值的原因之一。

1.3 扩容机制

扩容就像搬家 -- 房子住不下了，就换个两倍大的房子，然后把家具重新摆放。

当 HashMap 中的元素个数超过 threshold（= capacity * loadFactor）时，就会触发扩容。扩容后容量变为原来的 2 倍。

为什么要扩容？

假设桶数组只有 16 个位置，你往里面塞了 100 个元素。即使 hash 函数再均匀，平均每个桶也会有 6-7 个元素挂成链表，查找效率从 O(1) 退化到 O(N)。扩容就是为了降低哈希冲突的概率，让元素分布更均匀，保持接近 O(1) 的查找效率。

扩容的三种情况

扩容时，HashMap 会遍历旧数组的每个桶，对每个桶中的元素做不同处理：

  1. 桶中只有一个元素（没有链表）：直接 rehash 到新数组
if (e.next == null)
    newTab[e.hash & (newCap - 1)] = e;
  1. 桶中是链表：拆分为高位链表和低位链表
  2. 桶中是红黑树：类似链表拆分，如果拆分后节点数 <= 6，退化为链表

JDK 1.8 的巧妙 rehash

传统做法（JDK 1.7）是对每个元素重新计算 hash % newCapacity，代价很大。JDK 1.8 利用了一个巧妙的位运算技巧：

扩容后，每个元素要么留在原位，要么移动到 "原位 + 旧容量" 的位置。 判断依据就是看 hash 值在旧容量对应的那一位是 0 还是 1。

举个例子，假设旧容量 oldCap = 16（二进制 10000），某个元素原来在下标 3：

hash(a) = ...0 0011  -->  hash & 10000 = 0  --> 留在原位 index=3
hash(b) = ...1 0011  -->  hash & 10000 = 1  --> 移到 index=3+16=19

这个技巧能成立的前提是：容量永远是 2 的幂。扩容为 2 倍后，新的掩码 (newCap - 1) 比旧的掩码 (oldCap - 1) 只多了最高位的一个 1。所以只需要看 hash 在这一位上是 0 还是 1 就行了。

源码中通过 (e.hash & oldCap) == 0 来判断：

// 扩容时的链表拆分
Node<K,V> loHead = null, loTail = null; // 低位链表（留在原位）
Node<K,V> hiHead = null, hiTail = null; // 高位链表（移到新位置）
Node<K,V> next;
do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        // 该位为 0，留在原位
        if (loTail == null) loHead = e;
        else loTail.next = e;
        loTail = e;
    } else {
        // 该位为 1，移到 原位 + oldCap
        if (hiTail == null) hiHead = e;
        else hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;           // 低位链表放原位
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;  // 高位链表放新位置
}

这样就不需要对每个元素重新计算桶下标，整体效率大大提升。

红黑树的扩容处理

扩容时红黑树的处理和链表类似。因为 TreeNode 同时维护着链表结构（继承了 Node，有 next 字段），所以可以像链表一样按 (hash & oldCap) == 0 进行高低位拆分。拆分后：

  • 如果某条链的节点数 <= 6：退化为普通链表（untreeify），回收树结构的额外内存
  • 如果节点数 > 6：重新构建红黑树（treeify）

除了扩容之外，remove 操作也可能触发红黑树退化。当删除节点后树的结构过于稀疏时，HashMap 也会把红黑树转回链表。

容量设置建议

既然扩容有性能开销（需要重新分配数组、迁移所有元素），我们自然希望尽量减少扩容次数。阿里巴巴 Java 开发手册建议：创建 HashMap 时指定初始容量。

如果预计放入 n 个元素，建议初始容量设为 n / 0.75 + 1：

// 存 7 个元素：7 / 0.75 + 1 ≈ 10.3，JDK 会向上取到 16
Map<String, Object> map = new HashMap<>(10);

// 或者用 Guava 帮你计算
Map<String, Object> map = Maps.newHashMapWithExpectedSize(7);

Guava 的实现：

static int capacity(int expectedSize) {
    if (expectedSize < 3) {
        return expectedSize + 1;
    } else {
        return expectedSize < 1073741824
            ? (int) ((float) expectedSize / 0.75F + 1.0F)
            : Integer.MAX_VALUE;
    }
}

如果直接写 new HashMap(7)，JDK 会创建容量为 8 的 Map，但到第 6 个元素（8 * 0.75 = 6）就会触发扩容。多花一点初始内存，换来零次扩容，是值得的。

二、HashMap 的关键设计

2.1 为什么容量必须是 2 的幂？

一句话总结：为了用位运算 & 代替取模运算 %，提升计算桶下标的速度。

数学上有一个等式：当 n 是 2 的幂时，X % n == X & (n - 1)。

为什么呢？以 n = 8（二进制 1000）为例：

  • n - 1 = 7，二进制是 0111
  • X & 0111 就是取 X 的最后 3 位，这恰好等于 X 除以 8 的余数

位运算直接操作内存中的二进制数据，不需要做除法，速度远快于取模。所以 HashMap 计算桶下标时用的是：

index = (n - 1) & hash  // 等价于 hash % n，但更快

这就要求 n（容量）必须是 2 的幂。

另外，位运算还有一个好处：可以优雅地处理负数。hashCode 的返回值是 int 类型，范围是 -2^31 到 2^31-1，包含负数。如果用 % 取模，负数取模的结果也是负数，还需要额外处理。但用 & (n-1) 时，因为 n-1 是正数，其最高位一定是 0，做按位与之后结果的最高位也一定是 0，即结果一定是非负数。

如何保证容量始终是 2 的幂？

初始化时：如果你传入 new HashMap(10)，HashMap 不会真的用 10，而是通过 tableSizeFor 方法找到第一个 >= 10 的 2 的幂，也就是 16。

static final int tableSizeFor(int cap) {
    int n = cap - 1;       // 先减 1，处理 cap 本身就是 2 的幂的情况
    n |= n >>> 1;          // 把最高位的 1 "扩散"到右边
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

这段代码的算法思路：先把最高位 1 后面的所有位都变成 1（比如 10010 变成 11111），然后加 1 就得到了下一个 2 的幂（100000）。五次右移覆盖了 int 的全部 32 位。

扩容时：newCap = oldCap << 1，左移一位等于乘以 2，2 的幂乘 2 还是 2 的幂，天然保持。

2.2 哈希扰动函数

如果直接用 key.hashCode() 来定位桶，容易出问题。因为桶下标只用到了 hash 的低几位（比如容量 16 时只取低 4 位），高位的信息就被完全浪费了。

想象一下：两个 key 的 hashCode 高位完全不同，但低 4 位碰巧一样，它们就会被分配到同一个桶里 -- 这就是冲突。

JDK 1.8 的扰动函数用一行代码解决了这个问题：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

h ^ (h >>> 16) 做了什么？把 hashCode 的高 16 位和低 16 位做异或运算。这样高位的信息就"混入"了低位，让最终参与桶定位的低位数据同时包含了高位和低位的特征，哈希分布更均匀。

对比 JDK 1.7 的扰动函数：1.7 做了 4 次右移 + 5 次异或，扰动更充分但也更慢。1.8 为什么敢简化？因为 1.8 引入了红黑树，即使发生冲突，链表也不会退化到 O(N)（超过 8 会转树），所以可以在速度和散列质量之间做更激进的平衡。

2.3 链表转红黑树的条件（为什么是 8？）

转换条件有两个：链表长度 >= 8，并且数组长度 >= 64。如果数组长度不够 64，会优先扩容而不是树化（因为扩容能更好地分散元素）。

为什么不一冲突就转红黑树？

两个原因：

  • 空间：红黑树节点（TreeNode）占的内存是链表节点（Node）的大约 2 倍。TreeNode 除了 hash、key、value、next 之外，还有 parent、left、right、prev、red 等字段。
  • 时间：红黑树每次插入都可能需要旋转和变色来维持平衡，插入成本比链表高。在元素少的时候，链表遍历也很快，没必要付出树化的代价。

为什么阈值是 8？

HashMap 源码中有一段精彩的注释，用泊松分布计算了理想情况下桶中元素个数的概率分布：

链表长度 k概率 P(k)
00.60653066
10.30326533
20.07581633
30.01263606
40.00157952
50.00015795
60.00001316
70.00000094
80.00000006
>8不到千万分之一

链表长度达到 8 的概率只有千万分之六，属于极小概率事件。只有在 hash 函数质量极差或者遇到恶意构造的 key 时才会出现。在这种极端场景下转红黑树，是一个非常合理的安全阀设计。

为什么退化阈值是 6 而不是 7？

如果转树阈值 8、退化阈值 7，那在 7 和 8 之间频繁增删就会导致"转树-退化-转树-退化"的来回折腾，严重影响性能。设为 6 留出了 2 个元素的缓冲区，避免了频繁转换。

红黑树小知识

红黑树本质是一种"不那么严格的平衡二叉查找树"。它通过以下规则保持大致平衡：

  • 节点要么是红色，要么是黑色
  • 根节点和所有叶子节点（NIL）是黑色
  • 红色节点的两个子节点必须是黑色（不能有连续的红色）
  • 从任一节点到其所有叶子节点的路径上，黑色节点数量相同

相比严格的 AVL 树（左右子树高度差最多为 1），红黑树的平衡条件更宽松。这意味着：

  • 查找：两者都是 O(log N)，但 AVL 树因为更平衡，查找稍快
  • 插入/删除：红黑树最多 2-3 次旋转，AVL 树可能需要更多旋转

HashMap 选择红黑树而非 AVL 树，就是因为 HashMap 的插入和删除操作频繁，红黑树在这方面的综合性能更好。

2.4 线程不安全的表现

HashMap 不是线程安全的。在多线程环境下会出现以下问题：

1. JDK 1.7 扩容导致死循环

JDK 1.7 的扩容用头插法迁移链表。假设原链表是 A->B->C，两个线程同时触发扩容：

  • 线程 1 执行到 Entry next = e.next（此时 e=A, next=B）后被挂起
  • 线程 2 完成扩容，头插法使链表变成 C->B->A
  • 线程 1 恢复执行，继续用头插法处理。由于线程 2 已经改变了节点的 next 指向，线程 1 在处理 A 和 B 时会形成 A->B->A 的环形链表
  • 下次 get 遍历到这个桶时，就会陷入无限循环，CPU 飙到 100%

JDK 1.8 改用尾插法修复了这个问题（保持链表原有顺序，不会成环）。

2. 并发 put 数据丢失

两个线程同时 put 到同一个空桶：

  • 线程 1 判断 table[i] == null，准备插入
  • 线程 2 也判断 table[i] == null，也准备插入
  • 线程 1 先完成插入
  • 线程 2 覆盖了线程 1 的数据 -- 数据丢了

3. put 和 get 并发导致 get 返回 null

线程 1 正在 put 并触发扩容，数据正在从旧数组迁移到新数组。线程 2 此时来 get，可能在新数组中找不到数据（还没迁移过来），返回 null。

4. size 不准确

++size 不是原子操作（实际上是 read-modify-write 三步），多线程并发 put 后，size 可能比实际元素数少。

注意

HashMap 在多线程环境下不要使用！即使 JDK 1.8 修复了死循环问题，数据丢失和不一致的问题依然存在。如果需要线程安全的 Map，请用 ConcurrentHashMap。

三、其他 Map 实现

3.1 LinkedHashMap：有序的 HashMap

如果 HashMap 是一个无序的工具箱（东西随便放），那 LinkedHashMap 就是一个按放入顺序排列的收纳盒。

LinkedHashMap 继承自 HashMap，在 HashMap 的基础上，用一条双向链表把所有节点串了起来。它的节点在 HashMap.Node 的基础上多了 before 和 after 两个指针：

// LinkedHashMap 的节点，继承自 HashMap.Node
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after; // 双向链表的前驱和后继
}

LinkedHashMap 支持两种排序模式（通过构造函数的 accessOrder 参数控制）：

  • 插入顺序（默认，accessOrder=false）：谁先 put 谁排前面，遍历顺序与插入顺序一致
  • 访问顺序（accessOrder=true）：每次 get 或 put 一个已有的 key，都会把对应节点移到链表末尾。最近被访问过的在后面，最久未访问的在前面

访问顺序模式天然适合实现 LRU 缓存（Least Recently Used，最近最少使用）。链表头部就是最久未访问的元素，淘汰时直接移除头部即可：

// 一个简单但完整的 LRU 缓存实现，只需要几行代码
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // true = 访问顺序
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize; // 超过容量就移除最老的（链表头部）
    }
}

3.2 TreeMap：排序的 Map

如果说 HashMap 是按"身份证号"快速检索，那 TreeMap 就是按"姓名拼音"把所有人排好序。

TreeMap 实现了 SortedMap 接口，内部使用红黑树存储。它的特点是：key 始终有序。默认按 key 的自然顺序（需实现 Comparable），也可以传入自定义的 Comparator。

// 按 key 自然顺序排序
TreeMap<String, Integer> map = new TreeMap<>();
map.put("banana", 2);
map.put("apple", 1);
map.put("cherry", 3);
// 遍历顺序：apple -> banana -> cherry

// 按 key 长度排序
TreeMap<String, Integer> map2 = new TreeMap<>(
    Comparator.comparingInt(String::length)
);

TreeMap 的 get/put 时间复杂度是 O(log N)，比 HashMap 的 O(1) 慢，但它提供了一些 HashMap 没有的能力：范围查询（subMap、headMap、tailMap）、获取最大/最小 key（firstKey、lastKey）等。

使用 TreeMap 的前提：key 必须是可比较的 -- 要么 key 的类实现了 Comparable 接口，要么在构造 TreeMap 时传入 Comparator。否则会抛出 ClassCastException。

特性HashMapLinkedHashMapTreeMap
底层结构数组+链表+红黑树HashMap + 双向链表红黑树
是否有序无序插入/访问顺序按 key 排序
get/put 时间复杂度O(1)O(1)O(log N)
是否允许 null key允许允许不允许（需比较）
适用场景通用查找LRU 缓存需要排序遍历

3.3 Hashtable：过时的线程安全 Map

Hashtable 是 Java 早期（JDK 1.0）的线程安全 Map 实现，它的做法简单粗暴 -- 给每个公有方法都加 synchronized：

public synchronized V put(K key, V value) { ... }
public synchronized V get(Object key) { ... }
public synchronized int size() { ... }

这意味着同一时刻只有一个线程能操作整个 Map，无论是读还是写，并发性能极差。

Hashtable 和 HashMap 的其他区别：

  • key 和 value 都不允许为 null（会抛 NullPointerException）
  • 默认初始容量为 11，扩容为 2n+1（不要求是 2 的幂）
  • 继承自古老的 Dictionary 类（HashMap 继承 AbstractMap）

结论：永远不要在新代码中使用 Hashtable。 需要线程安全的 Map，用 ConcurrentHashMap。

四、ConcurrentHashMap 深入

4.1 JDK 7：分段锁 Segment

用一个生活类比来理解分段锁。

想象一家银行，如果只有一个柜台窗口，所有客户都要排一条长队。但如果银行开了 16 个窗口，同一时刻就可以有 16 个客户同时办业务 -- 只要他们去的不是同一个窗口。这就是分段锁的核心思想：把一把大锁拆成多把小锁，每把锁只管一小部分数据。

JDK 1.7 的 ConcurrentHashMap 内部有一个 Segment 数组（默认 16 个），每个 Segment 本质上是一个小的 HashMap，并且继承了 ReentrantLock，拥有自己独立的锁：

static final class Segment<K,V> extends ReentrantLock
                             implements Serializable {
    transient volatile HashEntry<K,V>[] table; // 每个 Segment 有自己的桶数组
    transient int count;
    transient int modCount;
    transient int threshold;
    final float loadFactor;
}

put 操作时：先根据 key 的 hash 高位定位到某个 Segment，然后只锁这一个 Segment，其他 Segment 不受影响。这样理论上最多支持 16 个线程同时写入（如果它们写的是不同的 Segment）。

但分段锁也有局限性：

  • 段的数量在创建时固定，无法动态调整。高并发时如果多个线程恰好访问同一个段，仍然需要排队
  • 每个 Segment 是独立的数据结构（包含自己的桶数组、计数器等），内存开销较大
  • 跨段操作（如 size()、containsValue()）需要依次锁定所有段，代价很高

4.2 JDK 8：CAS + synchronized

JDK 1.8 对 ConcurrentHashMap 进行了革命性的重构：彻底抛弃 Segment 分段锁，改用 "CAS + synchronized" 的节点级别锁方案。

继续用银行的比喻：以前是 16 个柜台窗口，每个窗口管一批客户。现在改成了自助机 + 单独服务室 -- 大部分操作在自助机上无锁完成（CAS），只有真正需要"面谈"时才进单独的小房间（synchronized 锁住单个桶的头节点）。

核心的 put 流程：

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());

    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;

        // 1. table 未初始化：CAS 方式初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();

        // 2. 桶为空：CAS 无锁插入新节点
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break; // CAS 成功，完成插入
        }

        // 3. 发现 ForwardingNode：说明正在扩容，帮助迁移
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);

        // 4. 桶不为空：synchronized 锁住头节点，执行链表/红黑树插入
        else {
            V oldVal = null;
            synchronized (f) {  // 只锁这一个桶的头节点
                if (tabAt(tab, i) == f) {
                    // 链表插入或红黑树插入...
                }
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

四个关键的并发控制点：

操作并发控制方式说明
初始化 tableCAS + 自旋sizeCtl 变量控制，只有一个线程能初始化
插入空桶CAS无锁，失败则自旋重试
插入非空桶synchronized（头节点）锁粒度为单个桶
扩容多线程协作CAS 领取任务，synchronized 锁桶迁移

为什么用 synchronized 而不是 ReentrantLock？

在节点级别加锁的场景下，多个线程同时写同一个桶的概率很低，锁竞争不激烈。在低竞争场景下：

  1. synchronized 有偏向锁和轻量级锁优化，大部分时间不需要升级为重量级锁，性能与 ReentrantLock 相当
  2. JVM 原生支持，可以享受锁消除、锁粗化等运行时优化，这些是 ReentrantLock 不具备的
  3. 不需要手动释放，代码更简洁，避免忘记 unlock 导致的死锁风险
  4. 内存更省：synchronized 利用对象头的 mark word 实现，而 ReentrantLock 是独立对象（还有 AQS 队列），每个节点都实例化一个会浪费大量内存
  5. 竞争失败时可以自旋，避免线程挂起和唤醒的上下文切换开销

4.3 并发扩容

ConcurrentHashMap 的扩容不是一个线程独自完成的，而是多个线程协作完成的。就像公司搬家，不是一个人搬完所有箱子，而是大家分工协作，每人搬一部分。

并发扩容的核心机制：

  1. 任务拆分：根据 CPU 核数计算每个线程负责迁移多少个桶，每个线程最少负责 16 个桶
  2. CAS 领取任务：用 transferIndex 记录当前分配进度。每个参与扩容的线程通过 CAS 从 transferIndex 中"认领"一段桶范围。CAS 保证不会有两个线程领到同一段
  3. ForwardingNode 标记：已迁移完的桶放入 ForwardingNode 标记节点，它有两个作用：
    • 告诉其他线程"这个桶已经搬完了，不用再搬"
    • 如果有 get 请求过来，ForwardingNode 会把请求转发到新数组
  4. 主动帮忙：如果某个线程在 put 时发现正在扩容（遇到 ForwardingNode），它不会傻等，而是调用 helpTransfer() 加入扩容大军

这种设计充分利用了多核 CPU 的优势，扩容速度远快于单线程操作。

4.4 为什么 key 和 value 不能为 null？

这个问题的答案来自 ConcurrentHashMap 的作者 Doug Lea 本人：在并发环境下，null 值会产生二义性（ambiguity）。

在 HashMap 中，map.get(key) 返回 null 时，你可以通过 map.containsKey(key) 来区分：是"存的就是 null"还是"没有这个 key"。在单线程下这没问题，因为两次调用之间不会有其他线程修改数据。

但在 ConcurrentHashMap 中：

  1. 线程 A 调用 map.get(key) 返回 null
  2. 线程 A 调用 map.containsKey(key) 检查
  3. 但在步骤 1 和步骤 2 之间，线程 B 可能已经 put(key, value) 或 remove(key) 了

这时候 containsKey 的结果就不可靠了，你永远无法确定 get 返回 null 的真正原因。这就是并发下的二义性问题。

为了让 API 的语义清晰无歧义，ConcurrentHashMap 从设计上直接禁止了 null key 和 null value。如果传入 null，立刻抛出 NullPointerException。

4.5 ConcurrentHashMap 的弱一致性迭代器

ConcurrentHashMap 的迭代器不会抛出 ConcurrentModificationException，这与 HashMap 的 fail-fast 行为截然不同。

fail-fast vs fail-safe（弱一致性）：

特性fail-fast（HashMap）弱一致性（ConcurrentHashMap）
遍历中修改抛 ConcurrentModificationException不抛异常
实现方式记录 modCount，每次操作前校验遍历时不加锁，容忍短暂不一致
数据一致性不允许并发修改可能读到旧数据或漏掉新数据
适用场景单线程多线程并发

ConcurrentHashMap 的迭代器能保证：一定能看到迭代器创建之前就已经存在的元素，但对于创建之后被其他线程添加或删除的元素，可能看到也可能看不到。这种设计在并发场景下是合理的 -- 它用一定程度的"不精确"换来了更高的并发性能。

4.6 ConcurrentHashMap 中的计数机制

ConcurrentHashMap 需要维护元素总数，但简单的 ++size 在高并发下会成为瓶颈。JDK 1.8 借鉴了 LongAdder 的分段计数思路：

// 低竞争时直接 CAS 更新
private transient volatile long baseCount;

// 高竞争时分散到多个 CounterCell 中
private transient volatile CounterCell[] counterCells;
  • 无竞争：直接 CAS 更新 baseCount
  • 有竞争：CAS 失败后，把增量分散到 counterCells 数组的某个槽位中
  • 读取 size：baseCount + sum(counterCells)

这种设计避免了所有线程争抢同一个变量的问题，在高并发下性能远好于 AtomicLong。

五、常见面试题精选

面试官：HashMap 的容量设置多少合适？

思路：核心是考虑负载因子的影响，避免不必要的扩容。

参考答案：如果预计要存 n 个元素，建议设置容量为 n / 0.75 + 1。比如要存 7 个元素，计算得 7/0.75+1 = 10.3，HashMap 会自动向上取到 16。如果直接写 new HashMap(7)，JDK 会创建容量为 8 的 Map，但第 6 个元素（8*0.75=6）就会触发扩容，这显然不是我们想要的。Guava 提供了 Maps.newHashMapWithExpectedSize(7) 帮我们做这个计算。阿里巴巴 Java 开发手册也明确建议：集合初始化时要指定初始容量。

面试官：HashMap 的 key 可以用可变对象吗？有什么风险？

思路：从 hashCode 和 equals 的角度分析。

参考答案：技术上可以，但强烈不建议。如果 key 在 put 之后被修改导致 hashCode 改变，那之后 get 时会定位到错误的桶，就再也找不到这个值了。最佳实践是用 String、Integer 等不可变对象做 key。如果必须用自定义对象，一定要正确重写 hashCode 和 equals 方法，并且保证参与 hash 计算的字段不可变。

面试官：为什么 HashMap 的默认负载因子是 0.75，不是 0.5 或 1？

思路：时间和空间的权衡 + 数学依据 + 工程考量。

参考答案：0.75 是时间和空间的最佳折中点。负载因子太大（如 1.0），桶装满才扩容，冲突多、查询慢；太小（如 0.5），桶半满就扩容，浪费空间。从数学上看，基于泊松分布推导，当负载因子约 ln(2) ≈ 0.693 时，桶空/非空概率各 50%，理论最优。0.75 接近这个值。此外，0.75 = 3/4，与任何 2 的幂（capacity）相乘都是整数，保证了 threshold（扩容阈值）始终是整数，这是工程上的实用考量。

面试官：HashMap 和 Hashtable 和 ConcurrentHashMap 有什么区别？

思路：从线程安全、null 值、性能、数据结构多维度对比。

参考答案：

维度HashMapHashtableConcurrentHashMap
线程安全不安全安全（方法级 synchronized）安全（CAS + synchronized 节点锁）
null key/value都允许都不允许都不允许
默认容量161116
扩容规则2 倍2 倍 + 12 倍
数据结构数组+链表+红黑树数组+链表数组+链表+红黑树
迭代器fail-fastfail-fast弱一致性（fail-safe）
并发性能--差（全表锁）好（节点锁 + CAS）
推荐使用单线程不推荐并发场景

面试官：JDK 1.7 的 HashMap 在多线程下为什么会死循环？

思路：头插法 + 并发扩容 = 链表成环。

参考答案：JDK 1.7 扩容时用头插法迁移链表。假设原链表 A->B->C，两个线程同时扩容。线程 1 刚记录 e=A, next=B 就被挂起。线程 2 完成扩容后头插法使链表变成 C->B->A（B.next 指向了 A）。线程 1 恢复执行，继续处理 A 时发现 A.next 已经被线程 2 改成了 null（原来指向 B），但 B.next 却指向了 A，最终形成 A<->B 的循环引用。下次 get 遍历到这个桶就会死循环，CPU 100%。JDK 1.8 改用尾插法，保持链表原序，不会成环。

面试官：ConcurrentHashMap 的 size() 准确吗？

思路：分段计数 + 弱一致性。

参考答案：JDK 1.8 的 ConcurrentHashMap 使用了类似 LongAdder 的分段计数策略。有一个 baseCount 和一个 CounterCell 数组。无竞争时 CAS 更新 baseCount；有竞争时分散到 CounterCell 数组中。size() 返回 baseCount 加上所有 CounterCell 的总和。由于是弱一致性的，在高并发场景下返回值可能不是绝对精确的实时值，但对绝大多数业务场景已经足够。

面试官：哈希冲突有哪些解决方法？HashMap 用的是哪种？

思路：列举主要方法，重点说链地址法。

参考答案：常见的有四种方法：

方法原理优点缺点
链地址法冲突的元素用链表串起来实现简单，适合频繁增删冲突多时链表长，查询退化为 O(N)
开放定址法冲突时按规则找下一个空位空间利用率高，缓存友好负载因子高时性能下降，删除复杂
再哈希法换一个哈希函数重新计算不易聚集需要额外计算，多个哈希函数设计困难
公共溢出区冲突元素统一放到溢出表对基本表无影响溢出区大时查找慢

HashMap 使用链地址法，在 JDK 1.8 中链表过长还会转为红黑树，是一种"链地址法 + 树化"的混合策略。开放定址法中的线性探测被 ThreadLocalMap 使用。分布式系统中还会用到一致性哈希来均匀分布数据到多个节点上。

小结

最后记住一句话：单线程用 HashMap，多线程用 ConcurrentHashMap，永远不要用 Hashtable。 如果需要有序遍历，按插入顺序用 LinkedHashMap，按 key 排序用 TreeMap。选对数据结构，是写好代码的第一步。