ConCurrentHashMap底层结构

ConcurrentHashMap是线程安全的HashMap。

1. 在jdk1.7中，ConCurrentHashMap采用分段锁机制，将数据分成一段一段的存储，给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。
   1.1 ConCurrentHashMap由一个Segment数组和多个HashEntry组成。Segment和HashEntry都是静态内部类。
   1.1 Segment继承重入锁ReentrantLock，一个Segment包含一个HashEntry数组。
   1.2 HashEntry用于封装映射表的键-值对，每个HashEntry是一个链表结构的元素。
   1.3 当对HashEntry数组中的元素进行修改时，首先会获取它对应的Segment锁。
   1.4 put操作：key会进行两次hash，第一次key的hash用于定位Segment位置，如果该Segment还未被赋值，则通过CAS进行赋值。第二次key的hash用于找到HashEntry位置，定位到HashEntry的链表头部。
   1.5 get操作：也是会经过两次hash，第一次key的hash用于定位Segment位置，第二次key的hash用于找到HashEntry位置。，然后遍历该HashEntry下的链表进行对比，成功就返回，不成功就返回nul
   

   jdk1.7 ConCurrentHashMap.png

2. jdk1.8中，采用Node+CAS+Synchronized来保证并发安全。取消了Segment类，直接锁定HashEntry，降低了锁的粒度。
   2.1 Node是ConcurrentHashMap存储结构的基本单元，继承于HashMap中的Entry，用于存储数据。
   2.2 put操作：根据key计算出hashCode，根据hashCode定位Node，判断当前Node是否为null，为null则写入数据，利用CAS自旋机制保证写入数据成功。不为null，则利用Synchronized锁写入数据。如果数量大于8则要转换为红黑树。
   2.3 get操作：根据计算出来的 hashcode 寻址，是红黑树那就按照树的方式获取值。如果不满足那就按照链表的方式遍历获取值。
   

   jdk1.8 ConCurrentHashMap.png