⭐ 题目日期：

美团 - 2024/12/23

📝 题解：

---

HashMap非线程安全的底层原因分析

HashMap在多线程环境下不安全的核心在于其内部实现缺乏同步机制，导致并发操作时出现竞态条件（Race Conditions）和数据不一致。以下是具体原因的逐层解析：

---

1. 数据插入时的竞态条件

• 场景：两个线程同时调用put()插入不同的键，但哈希到同一桶位置。
• 底层逻辑：
  • 步骤1：检查桶是否为空（if ((p = tab[i = (n - 1) & hash]) == null）。
  • 步骤2：若为空，则直接插入新节点（tab[i] = newNode(...)）。
• 问题：
  若线程A和线程B同时通过步骤1的检查（均认为桶为空），会先后执行步骤2。
  结果：后执行的线程覆盖先执行线程的节点，导致数据丢失。

---

2. 扩容（Resize）导致的数据丢失与死循环

JDK 1.7 头插法引发的死循环

• 扩容流程：
  旧数组元素通过头插法迁移至新数组（链表顺序反转）。
• 并发问题：
  若线程A和线程B同时扩容，可能导致：
  • 环形链表：线程A迁移节点1→2→3，线程B迁移节点3→2→1，形成循环引用。
  • 后果：后续get()操作遍历链表时陷入死循环，CPU占用率飙升。

JDK 1.8 尾插法优化后的问题

• 改进：改用尾插法，避免环形链表。
• 残留问题：
  • 数据覆盖：多线程同时迁移同一桶的节点，导致部分数据丢失。
  • size计算错误：size字段的自增操作（++size）非原子性，可能导致实际元素数量与size值不符。

---

3. 结构修改与遍历冲突

• modCount机制：
  HashMap通过modCount记录结构性修改（如put、remove）。
• 问题：
  • 线程A遍历（如迭代器）时，线程B执行put或remove，导致modCount变化。
  • 线程A检测到modCount != expectedModCount，抛出ConcurrentModificationException。

---

4. 非原子操作与可见性问题

• 共享变量未同步：
  table数组、size、threshold等字段未用volatile修饰，多线程间修改不可见。
• 示例：
  线程A扩容后更新table，线程B可能仍使用旧的table引用，导致操作错误。

---

代码示例：JDK 1.8的putVal竞态条件

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 竞态条件点：检查桶是否为空
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null); // 非原子插入
    else {
        // 处理哈希冲突...
    }
    ++modCount; // 非原子自增
    if (++size > threshold) // size非原子更新
        resize();
    return null;
}

• 竞态点分析：
  • 多个线程可能同时通过if ((p = tab[i...] == null)检查，导致数据覆盖。
  • size的自增操作非原子，可能引发扩容误判。

---

解决方案对比

方案	原理	适用场景
ConcurrentHashMap	分段锁/CAS + synchronized细粒度锁	高并发读写
Collections.synchronizedMap	全表synchronized包装	低并发或兼容旧代码
手动加锁	显式控制synchronized或Lock	简单逻辑，性能要求不高

---

总结

• 底层根源：HashMap未对关键操作（如桶插入、扩容、size更新）做同步控制，导致竞态条件与数据不一致。
• 线程安全替代：优先使用ConcurrentHashMap，其通过CAS、分段锁等机制实现高效并发。
• 设计启示：多线程环境下，共享可变状态必须通过锁或原子操作保护，避免无约束的并发访问。