山羊八股

外观

HashMap扩容时读写操作怎么办

约 1604 字大约 5 分钟

Java基础美团

2025-06-19

⭐ 题目日期：

美团 - 2025/4/25

📝 题解：

在 Java 中，HashMap 在扩容（resize）时处理读写操作的核心机制是 “渐进式扩容” 和 “保证读操作可见性”。它设计得非常巧妙，旨在尽量减少扩容对并发读写的阻塞影响，但 HashMap 本身并不是线程安全的，高并发写操作仍需 ConcurrentHashMap 或外部同步。

以下是扩容期间读写操作的处理方式：

  1. 触发扩容（写操作触发）：

    • 扩容发生在 添加新元素（put, putAll） 时。
    • 当 size > threshold（容量 * 负载因子）时，触发扩容。
    • 创建一个新的、容量是原数组两倍的新数组 newTab。

  2. 渐进式迁移（写操作和部分读操作协助）：

    • 关键点： HashMap 不会一次性 将所有元素从旧数组 table 迁移到新数组 newTab。迁移是 分批次、按桶（链表/树） 进行的。
    • 迁移时机：
      • 后续写操作触发： 当线程执行 put, remove 等写操作时，如果发现当前操作的桶在旧数组上且该桶尚未迁移，该线程会先协助完成这个桶（以及可能相邻的桶）的迁移，然后再执行自己的写操作。
      • 读操作“协助”（仅遍历）： 严格来说，get 操作本身不会触发迁移。但是，Iterator 的遍历操作（如 entrySet().iterator()）在遍历过程中，如果遇到尚未迁移的桶，迭代器会协助迁移该桶（调用 transfer 方法的一部分逻辑），以确保迭代器能遍历到所有元素（包括迁移到新位置和新数组中的元素）。普通的 get(key) 调用不会触发迁移。

  3. 读操作 (get(key)) 的处理：

    • 无锁，可见性保证： 读操作 不需要获取锁。
    • 访问旧数组或新数组： 线程进行 get(key) 时：
      1. 首先访问当前的 table 引用（volatile 修饰）。
      2. 根据 key 的哈希值计算出桶索引。
      3. 如果该桶索引对应的位置还在旧数组上（尚未迁移），则直接在旧数组的这个桶（链表/树）上查找。
      4. 如果该桶索引对应的位置已经迁移到新数组上（迁移完成），则直接在新数组对应的桶上查找。
    • 如何知道在哪个数组上找？ 迁移过程中，每个桶在旧数组中的节点会包含一个特殊的 next 指针（在 Node 中是 next 字段，在 TreeNode 中可能有类似机制）。当迁移完成一个桶后，该桶在旧数组中的头节点会被替换为一个特殊的 ForwardingNode 节点（在 JDK 1.8 的 ConcurrentHashMap 中显式存在，但在 HashMap 中逻辑类似，通过 next 指针隐式实现）。get 操作遍历链表/树时，如果遇到 ForwardingNode 或发现 next 指向了新数组的位置，就知道应该跳转到新数组去查找。
    • 结果： get 操作在扩容期间可以无阻塞地、正确地访问到数据，无论数据是留在旧数组还是已经迁移到新数组。它看到的是某个时间点的快照（可能包含新旧数组的数据）。

  4. 写操作 (put(key, value), remove(key)) 的处理：

    • 可能触发迁移： 如前所述，写操作如果发现目标桶尚未迁移，当前线程会先负责迁移该桶（以及可能根据策略迁移相邻的桶）。
    • 定位桶： 和读操作类似，需要先定位到数据应该所在的桶（可能在旧数组或新数组）。
    • 修改： 在定位到的桶（链表/树）上进行插入、更新或删除操作。
    • 并发问题： 这是 HashMap 非线程安全的关键点！ 如果多个线程同时执行写操作（包括迁移桶本身也是一个写操作），并且这些操作涉及到同一个桶（无论是在旧数组还是新数组上），极有可能导致：
      • 数据覆盖： 一个线程的 put 覆盖了另一个线程刚 put 的值。
      • 链表环/树破坏： 在迁移链表或调整红黑树结构时发生并发修改，导致链表成环或树结构破坏，后续操作可能陷入死循环或数据丢失。
      • size 不准确： size 的更新不是原子的。
    • 结果： 虽然单个写操作内部会协助迁移，但 多个并发写操作（包括协助迁移）之间没有任何同步机制，必然导致数据不一致。

  5. 扩容完成：

    • 当所有桶都从旧数组迁移到新数组后，更新 table 引用指向 newTab。
    • 更新 threshold 为新值（新容量 * 负载因子）。
    • 旧数组可以被垃圾回收。

总结与关键点：

  1. 渐进式扩容： 迁移按桶分批进行，由后续的写操作和迭代器遍历操作触发，避免了一次性迁移的巨大开销和长时间停顿。
  2. 读操作无阻塞且安全： 通过访问 volatile table 引用和 ForwardingNode 机制（或等效逻辑），get 操作可以无锁地、正确地访问到新旧数组中的数据。扩容期间的 get 操作是线程安全的。
  3. 写操作触发迁移但非线程安全： 写操作会协助迁移它访问到的桶，但多个线程并发执行写操作（包括迁移）会导致严重的线程安全问题（数据损坏、死循环）。
  4. HashMap 非线程安全： 这是核心结论。HashMap 的扩容机制设计是为了在单线程环境下高效进行，并尽量减少对读操作的影响。它完全没有考虑多线程并发写入/迁移时的同步问题。
  5. 替代方案：
    • ConcurrentHashMap： 专为高并发设计，使用更精细的锁（分段锁或 CAS + synchronized）和线程安全的扩容机制。
    • Collections.synchronizedMap(new HashMap<>())： 对整个 Map 加锁，保证线程安全但性能较差。
    • 显式同步 (synchronized 或 Lock)： 在使用 HashMap 的代码块外部手动加锁。

简单来说：扩容时，get 操作能正常工作，put/remove 操作会帮忙搬数据（迁移桶），但如果有多个线程同时 put/remove，HashMap 就一定会出乱子。 因此，在多线程环境下需要修改 Map 时，永远不要使用 HashMap，请使用 ConcurrentHashMap。