concurrentHashMap原理

concurrentHashMap的是为了解决HashMap在并发环境中出现的线程安全问题，同时也优化了HashTable在高并发中存在的性能问题，让其性能更接近于HashMap。

高并发问题

HashMap

1.数据丢失问题

2.JDK1.7采用头插法，会导致链表成环，抛出ConcurrentModificationException异常

HashTable

全局使用synchronized锁，读写都需要加锁，性能差。

// Hashtable的解决方案：全局锁 public class Hashtable<K,V> { public synchronized V put(K key, V value) { // 全局一把锁，所有操作串行化 // 性能极差，100个线程要排队 } public synchronized V get(Object key) { // 读操作也要加锁！ // 大多数场景下读多写少，这是巨大的浪费 } }

需要解决的问题

concurrentHashMap需要解决如下两个问题，保证线程安全的前提下，让其读写性能趋近于HashMap，所以下文主要探讨，它是如何解决这两个问题的。

1. 在HashTable的基础上，解决全局锁的性能问题
2. 让读写性能接近HashMap

JDK1.7中的解决方案

洞察：大多数场景下，key的操作其实互补干扰

假设决策：如果key1和key2在不同的段，为什么不让它们并行？

在该版本中，CHM（concurrentHashMap）使用分段锁优化该问题，将一个HashMap分为16段进行存储，在并发操作中，需要首先定位到key在哪一段，将该段加锁，在定位到桶中存储，来保证线程安全的同时，提升大约16倍的性能。

class Segment<K,V> extends ReentrantLock { // 每个Segment都是一个完整的HashMap结构 HashEntry<K,V>[] table; int count; int modCount; int threshold; float loadFactor; }

存在的问题：

1. 内存浪费：每一段都是一个完整的HashMap结构，16套的元数据

2. 不够灵活：并发度固定为16，不能动态调整

3. 访问开销：需要两次哈希计算（定位Segment + 定位桶）

JDK1.8的解决方案

统计数据表明：

80%的put操作，目标同是空的（无竞争）

15%的操作，桶中只有一个元素（竞争小）

5%的操作，桶中有多个元素（需要真正加锁）

设计决策：

switch（竞争程度）：

case 无竞争：用CAS（无锁）

case 低竞争：用synchronized（轻量级锁）

case 高竞争：转红黑树（O(log n)保证）

所以该版本开始CHM使用CAS+synchronized来保证线程安全的同时进一步优化性能。

在put操作时，当桶为空，则使用CAS操作，添加节点；当桶不为空时，则锁住该桶（锁头节点），保证线程安全。get操作完全无锁，至于为什么，下期讲吧。

（源码不分析了，看不懂😭）

并发编程的三个境界

境界1：互斥（悲观锁）

// HashTable的做法：先锁住，再操作 synchronized(this) { } // 思想：默认会有竞争，所以先加锁

境界2：乐观锁（CAS）

// AtomicInteger的做法：先操作，发现冲突再重试 do { oldValue = get(); newValue = oldValue + 1; } while (!compareAndSet(oldValue, newValue)); // 思想：默认没竞争，有冲突再处理

境界3：自适应锁（CHM的做法）

// 智能选择策略 if (无竞争) { 用CAS; // 乐观 } else { 用synchronized; // 悲观 }