Java 基础篇之 ConcurrentHashMap

• jdk1.7和jdk1.8的ConcurrentHashMap底层数据结构

  jdk1.7：由一个Segment数组和多个HashEntry组成

  Segment数组就是将一个大的table分割成多个小的table来进行加锁（分段锁思想，继承ReentrantLock），而每一个Segment元素存储的时HashEntry数组。

jdk1.8：废弃了Segment，采用Node数组+链表+红黑树的数据结构来实现

• jdk1.7和jdk1.8的ConcurrentHashMap的区别

  ① 数据结构不同

  ​ jdk1.7是Segment+HashEntry，jdk1.8是Node数组+链表+红黑树

  ② 线程安全机制不同

  ​ jdk1.7是ReentrantLock，jdk1.8是CAS、synchronized

  ③ 锁的粒度不同

  ​ jdk1.7是对进行数据操作的Segment加锁，jdk1.8是对数组元素加锁 （头节点）

  注：获取数据两个版本都是通过volatile来保证数据的可见性。

• jdk1.8 ConcurrentHashMap 的put方法流程

  ① 计算hash值

  ② 如果没有初始化就先调用initTable方法进行初始化过程（CAS）

  ③ 如果没有hash冲突就直接CAS插入

  ④ 如果还在进行扩容操作就先进行扩容

  ⑤ 如果由hash冲突，则加锁来保证线程安全(synchronized)

  ⑥ 如果链表数量大于等于8，且数组长度大于64，则转为红黑树

  ⑦ 如果成功添加就调用addCount方法统计size，并检查是否需要扩容

• jdk1.8 ConcurrentHashMap 的get方法流程
  ① 计算hash值，定位到该table位置，如果首节点符合就直接返回

  ② 如果遇到扩容，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回

  ③ 以上都不符合，就往下遍历节点，匹配就返回，否则最后返回null

• jdk1.8中为啥用synchronized代替ReentrantLock
  jdk1.7版本及以前：使用Segment，初始化为容量为16，而每个Segment都继承了ReentrantLock类，这样每个Segment类本身就是一 个锁，之后Segment内部又是一个HashEntry数组，每个HashEntry里面对应着一个Node链表。

  ​ 那么当put元素时，对其key进行hash，然后对16取模得到对应的Segment的下标，之后调用对应Segment的lock()上锁，也就是每个Segment的锁是分开的，并发量为Segment的个数。

  ​ jdk1.8版本：使用synchronized锁住的是链表的头节点，即锁住的是hash冲突的那条链表，锁的粒度细化了。

  ​