HashMap与TreeMap在并发场景下各有什么问题？

Question

在并发场景下，HashMap与TreeMap均非线程安全。HashMap在多线程环境下进行扩容操作时，可能引发“死循环”问题（JDK 1.7中尤为明显），导致CPU占用率飙升；同时其get、put操作无同步控制，易出现数据不一致或结构破坏。TreeMap虽基于红黑树实现，提供了有序性，但同样未实现线程同步，在并发插入、删除时可能导致结构失衡或遍历异常。两者均需通过Collections.synchronizedMap包装或使用ConcurrentHashMap、ConcurrentSkipListMap等并发容器来保证线程安全。

Answer 1

并发场景下HashMap与TreeMap的线程安全问题深度解析

1. 基础概念：HashMap与TreeMap的核心特性

HashMap是基于哈希表实现的键值对集合，提供O(1)平均时间复杂度的put和get操作。其内部通过数组+链表（或红黑树）结构存储数据，在JDK 1.8后引入了链表转红黑树机制以优化冲突性能。

TreeMap则基于红黑树实现，保证键的自然排序或自定义比较器顺序，适用于需要有序遍历的场景，但查询和修改操作的时间复杂度为O(log n)。

• HashMap：无序、高性能、非同步
• TreeMap：有序、中等性能、非同步
• 两者均未实现任何内部锁机制

2. 并发风险剖析：从现象到本质

容器类型	典型并发问题	触发条件	JDK版本敏感性
HashMap	扩容时死循环	多线程同时put导致rehash链表反转	JDK 1.7尤为严重
HashMap	数据覆盖/丢失	put操作无CAS或synchronized保护	所有版本均存在
TreeMap	红黑树结构失衡	并发插入删除破坏旋转逻辑	跨版本普遍存在
TreeMap	遍历时抛出ConcurrentModificationException	fast-fail机制检测到modCount变更	所有版本一致行为

3. 死循环原理详解：以JDK 1.7 HashMap为例

在JDK 1.7中，HashMap扩容采用头插法进行链表迁移。当多个线程同时触发resize()时，可能形成环形链表：

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next; // 多线程下next可能已被修改
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];     // 头插法导致引用错乱
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}
    

两个线程A、B同时执行transfer，可能导致e.next指向自身，后续get操作陷入无限循环，CPU使用率飙升至100%。

4. 解决方案对比分析

针对非线程安全问题，常见解决路径包括外部同步包装与使用专用并发容器：

1. Collections.synchronizedMap(new HashMap<>()) —— 全局同步，性能差
2. ConcurrentHashMap —— 分段锁（JDK 1.7）或CAS+synchronized（JDK 1.8+）
3. ConcurrentSkipListMap —— 跳表实现，支持高并发有序访问
4. 手动加锁（如ReentrantReadWriteLock）控制临界区
5. 使用CopyOnWriteMap模式（适用于读多写少）

5. ConcurrentHashMap与ConcurrentSkipListMap性能对比

下表展示了主流并发映射容器的关键指标：

容器	线程安全机制	时间复杂度	内存开销	适用场景
ConcurrentHashMap	Node+CAS+synchronized	O(1) ~ O(log n)	中等	高并发无序缓存
ConcurrentSkipListMap	跳表+CAS	O(log n)	较高	需排序的并发场景
synchronizedMap	方法级synchronized	O(1)或O(log n)	低	低并发兼容旧代码

6. 架构设计建议与最佳实践

在实际系统架构中，应根据业务特征选择合适的数据结构：

// 推荐用法示例
Map<String, Object> concurrentMap = new ConcurrentHashMap<>();
SortedMap<Long, Task> sortedMap = new ConcurrentSkipListMap<>();

// 避免如下写法
Map<String, Object> unsafeMap = Collections.synchronizedMap(new TreeMap<>());
// 虽然线程安全，但性能低于ConcurrentSkipListMap
    

7. 可视化流程：HashMap扩容死循环形成过程

以下mermaid图示展示两个线程如何共同制造环形链表：

graph TD
    A[线程A: e=Entry1, next=Entry2] --> B[线程B抢占CPU]
    B --> C[线程B完成整个链表迁移]
    C --> D[Entry2.next = Entry1]
    D --> E[形成环形引用]
    E --> F[线程A恢复执行，继续头插]
    F --> G[Entry1.next = Entry2，闭环完成]
    G --> H[get操作进入死循环]
    

8. 检测与监控手段

生产环境中可通过以下方式提前预警：

• JVM监控：持续观察GC频率与CPU占用率突增
• 线程Dump分析：查找长时间运行的GET操作线程
• 字节码增强：利用ASM或ByteBuddy拦截非并发容器的构造函数
• 静态扫描：SonarQube规则检测new HashMap()出现在并发上下文
• Arthas诊断：trace命令追踪HashMap.put调用栈

9. 进阶思考：无锁数据结构的发展趋势

现代JDK不断演进并发容器设计理念：

JDK 9引入了改进的hashCode计算防止碰撞攻击；JEP 332推动更高效的并发集合；响应式编程框架如Project Reactor倾向于使用不可变数据结构降低同步开销。未来趋势将更加注重无锁（lock-free）算法与硬件指令集（如LL/SC）结合，提升横向扩展能力。

10. 实战案例：某电商订单缓存事故复盘

某大促期间，系统使用HashMap缓存用户购物车信息，未考虑分布式会话共享。当流量激增触发频繁GC导致线程调度紊乱，多个工作线程同时向同一桶位插入数据，最终引发死循环。监控显示单台机器CPU持续100%达12分钟，影响订单提交成功率下降47%。事后重构采用ConcurrentHashMap并加入LRU淘汰策略，彻底杜绝此类问题。