数据结构算法 - ConcurrentHashMap 源码解析
五个线程同时往 HashMap 中 put 数据会发生什么？
ConcurrentHashMap 是怎么保证线程安全的？
在分析 HashMap 源码时还遗留这两个问题，这次我们站在 Java 多线程内存模型和 synchronized 的实现原理，这两个角度来彻底分析一下。至于 JDK 1.8 的红黑树不是本文探讨的内容。
1. Java 多线程内存模型
五个线程同时往 HashMap 中 put 数据会出现两种现象，大概率会出现数据丢失，小概率会出现死循环，我们不妨写个测试代码自己验证一下。那为什么会出现这两种现象，我们先来回顾一下之前的Java 多线程内存模型。请看图：
Java内存模型中规定了所有的变量都存储在主内存中，每条线程还有自己的工作内存，线程的工作内存中保存了该线程使用到的变量到主内存副本拷贝，线程对变量的所有操作（读取、赋值）都必须在工作内存中进行，而不能直接读写主内存中的变量。不同线程之间无法直接访问对方工作内存中的变量，线程间变量值的传递均需要在主内存来完成，线程、主内存和工作内存的交互关系如上图所示。
1、Segment默认是16，理论上，最多同时支持16个线程并发读写，但是是操作不同的Segment
2、初始化时可以指定Segment数量
3、Segment继承自ReentrantLock,每一个Segment都会有一把锁，保证线程安全
4、采用链表方式解决hash冲突
原理上来说：
和 HashMap 非常类似，唯一的区别就是其中的核心数据如 value ，以及链表都是 volatile 修饰的，保证了获取时的可见性。
ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
思考？
超过16个线程是否就会出现线程不安全的情况？不会，只是会出现线程的等待竞争的情况。
采用链表解决hash冲突的缺点：那就是查询遍历链表效率太低。
源码分析：
1、首先是通过 key 定位到 Segment，之后在对应的 Segment 中进行具体的 put。
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
2、在Segment中通过scanAndLockForPut加锁后，进行添加操作，然后解锁
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。
不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。
最后会解除在 1 中所获取当前 Segment 的锁。
分析Segment加锁代码：
虽然 HashEntry 中的 value 是用 volatile 关键词修饰的，但是并不能保证并发的原子性，所以 put 操作时仍然需要加锁处理。
首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。
其中 Segment 继承于 ReentrantLock
1、尝试自旋获取锁。
2、如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。
jdk1.8开始， ConcurrentHashMap的结构：
1、取消了Segment 分段锁，采用 synchronized 和 CAS 来实现线程安全
2、当链表长度大于8时，转为红黑色结构。
线程不安全的原因分析：
现在我们来想象一下，假设线程 1 把数据读到了自己的工作内存中，在 tab 角标为 1 的链表头插入了一条新的数据，倘若这时还没来得及将新增的数据刷新到主内中。接着线程 2 就把数据读到了自己的工作内存中，在 tab 角标为 1 的链表头插入了一条新的数据。接着线程 1 把新增数据刷新到主内存中，线程 2 也把数据新增数据刷新到主内存中，那么线程 2 就会覆盖线程 1 的新增数据，从而导致数据丢失的情况。这里需要注意的是，只有两个线程都是操作 tab 的同一个 index 链表才会导致数据丢失的情况，如果不是同一个 index 链表就不会有覆盖和丢失这一说。
简单的说，多个线程进行put操作时，由于key值的hashcode值相等，导致向同一个tab里面的链表或者树节点上的空位存入值，这样，就会出现相互覆盖的情况。
2. synchronized 的底层实现原理
关于 HashMap 的线程不安全问题，Java 给我们提供了三种方案：
1. 第一种是 HashTable
2. 第二种是 Collections.synchronizedMap()
3. 第三种是 ConcurrentHashMap
而第一种和第二种都是通过用 synchronized 同步方法来保证线程安全，性能上有所欠缺不推荐大家使用。ConcurrentHashMap 在 JDK 1.8 之前采用的是 Segment 分段锁来实现的，而 JDK 1.8 之后则采用 synchronized 和 CAS 来实现。
HashTable 通过锁住整个 put 和 get 方法来实现线程安全并不是很合理，因为一个线程在 put 的时候，另外一个线程不能再 put 和 get 必须进入等待状态。同理一个线程在 get 的时候，另外一个线程也不能再 get 和 put 。上面通过分析只有两个线程都是操作 tab 的同一个 index 链表才会导致数据丢失的情况，如果不是同一个 index 链表就不会有覆盖和丢失这一说。因此也没必要锁住整个方法，只需要锁住每个 tab 的 index 链即可。
ConcurrentHashMap 在 JDK 1.8 之前采用的是 Segment 继承自 ReentrantLock 来锁住 tab 的 index 链，而 JDK 1.8 之后则采用 synchronized 来实现，这两者又有什么区别？我们首先看下 synchronized 的底层是怎么实现线程安全的。Java中的每一个对象都可以作为锁。具体表现有以下3种形式。
// 1.对于普通同步方法，锁是当前实例对象。this
public synchronized void method(){
}
// 2.对于静态同步方法，锁是当前类的Class对象。this.class
public static synchronized void method(){
}
// 3.对于同步方法块，锁是Synchonized括号里配置的对象。object
public static synchronized void method(){
synchronized(object){
}
}
我们可能会想锁到底存在哪里呢？锁里面会存储什么信息呢？其实 synchronized 同步的代码块，虚拟机在同步代码块开始前会插入一条 monitorenter 指令，在代码块的末尾会插入一条 monitorexit 指令。而每个对象的 Mark Word 头信息里都会存储 Monitor 信息，也就是当前对象的锁信息，当然 Mark Word 头信息还包含对象的 hashCode 和 GC 的分代年龄，具体请看下表：
Lock 的实现原理和 synchronized 有些类似，都是通过线程的原子性来保证线程同步，具体的实现的方式大家可以去看下 ReentrantLock 的源码实现。
那为什么在 JDK 1.8 之后要采用 synchronized 和 CAS 来实现？
在 JDK 1.6 为了减少获得锁和释放锁带来的性能消耗，引入了“偏向锁”和“轻量级锁”，级别从低到高依次是：无锁状态、偏向锁状态、轻量级锁状态和重量级锁状态，这几个状态会随着竞争情况逐渐升级。锁可以升级但不能降级，意味着偏向锁升级成轻量级锁后不能降级成偏向锁。这种锁升级却不能降级的策略，目的是为了提高获得锁和释放锁的效率。
当线程 1 进入同步代码块遇到 monitorenter 指令，首先判断锁的状态发现是 0 ，采用 CAS 将锁的状态设置为 1，偏向锁设置为 1，锁的标致位设置为 1 ，继续执行同步代码块里面的指令。这时若线程 2 也来到了同步代码块，也会遇到 monitorenter 指令，首先判断锁的状态发现是 1 进入等待中，等线程 1 执行完同步代码块遇到 monitorenter 指令，首先会清空锁的状态然后唤醒线程 2 。如此反复即可保证线程安全。
偏向锁
大多数情况下，锁不仅不存在多线程竞争，而且总是由同一线程多次获得，为了让线程获得锁的代价更低而引入了偏向锁。当一个线程访问同步块并获取锁时，会在对象头和栈帧中的锁记录里存储锁偏向的线程 ID，以后该线程在进入和退出同步块时不需要进行 CAS 操作来加锁和解锁，只需简单地测试一下对象头的 Mark Word 里是否存储着指向当前线程的偏向锁。如果测试成功，表示线程已经获得了锁。如果测试失败，则需要再测试一下 Mark Word 中偏向锁的标识是否设置成1（表示当前是偏向锁）：如果没有设置，则使用 CAS 竞争锁；如果设置了，则尝试使用CAS将对象头的偏向锁指向当前线程。
轻量级锁
线程在执行同步块之前，JVM 会先在当前线程的栈桢中创建用于存储锁记录的空间，并将对象头中的 Mark Word 复制到锁记录中。然后线程尝试使用 CAS 将对象头中的 Mark Word 替换为指向锁记录的针。如果成功，当前线程获得锁，如果失败，表示其他线程竞争锁，当前线程便尝试使用自旋来获取锁。
重量级锁
轻量级锁采用自旋的方式不断的尝试获取锁，如果长时间获取不到锁势必会不断消耗 CPU 的资源。所以当线程竞争比较激烈或者线程迟迟获取不到锁，就会升级为重量级的锁状态，此时线程是阻塞的，且响应时间缓慢。
3. ConcurrentHashMap 源码分析
其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。
也将 1.7 中存放数据的 HashEntry 改为 Node，但作用都是相同的。
其中的 val next 都用了 volatile 修饰，保证了可见性。
put 方法
重点来看看 put 函数：
根据 key 计算出 hashcode 。
判断是否需要进行初始化。
f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
如果都不满足，则利用 synchronized 锁写入数据。
如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。
get 方法：
根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
如果是红黑树那就按照树的方式获取值。
就不满足那就按照链表的方式遍历获取值。
1.8 在 1.7 的数据结构上做了大的改动，采用红黑树之后可以保证查询效率（O(logn)），甚至取消了 ReentrantLock 改为了 synchronized，这样可以看出在新版的 JDK 中对 synchronized 优化是很到位的。
总结：
本文主要介绍了一下几点：
1、ConcurrentHashMap 的数据结构
2、ConcurrentHashMap 是如何解决hash冲突的，这部分其实和hashmap处理方式是一致的
3、分析了ConcurrentHashMap 是如何实现线程安全的