1. JDK 1.7

image.png
HashTable 数据结构和 HashMap 相同，桶+链表 ，只不过HashTable 是Entry[] ，Entry next
而HashMap 是Node[],Entry next
ConcurrentHashMap 1.7的时候 相当于 多个 HashTable 组合在一起，每个 桶单独拥有一个锁；

区别：
【1】put和 get 两次Hash到达指定的HashEntry，第一次hash到达Segment,第二次到达Segment里面的Entry,然后在遍历entry链表
【2】Segment的初始化容量是16;
【3】HashEntry最小的容量为2

2. JDK 1.8

基本数据结构和 HashMap 相同；

【1】数据结构上：
JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树

【2】JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是Node（首节点）
JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也增加了
【3】从1.7到1.8版本，由于HashEntry从链表 变成了红黑树所以 concurrentHashMap的时间复杂度从O(n)到O(log(n))

2.1 JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock

【1】JDK1.6后 基于JVM的synchronized优化空间更大，使用内嵌的关键字比使用API更加自然；
在相对而言的低粒度加锁方式，synchronized并不比ReentrantLock差，在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界，更加的灵活，而在低粒度中，Condition的优势就没有了

【2】在大量的数据操作下，对于JVM的内存压力，基于API的ReentrantLock会开销更多的内存，虽然不是瓶颈，但是也是一个选择依据

3.ConcurrentHashMap put 流程

  1. public V put(K key, V value) {
  2.     return putVal(key, value, false);
  3. }
  4. /** Implementation for put and putIfAbsent */
  5. final V putVal(K key, V value, boolean onlyIfAbsent) {
  6.     if (key == null || value == null) throw new NullPointerException();
  7.     int hash = spread(key.hashCode()); //两次hash，减少hash冲突，可以均匀分布
  8.     int binCount = 0;
  9.     for (Node<K,V>[] tab = table;;) { //对这个table进行迭代
  10.         Node<K,V> f; int n, i, fh;
  11.         //这里就是上面构造方法没有进行初始化，在这里进行判断，为null就调用initTable进行初始化，属于懒汉模式初始化
  12.         if (tab == null || (n = tab.length) == 0)
  13.             tab = initTable();
  14.         else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//如果i位置没有数据，就直接无锁插入
  15.             if (casTabAt(tab, i, null,
  16.                          new Node<K,V>(hash, key, value, null)))
  17.                 break;                   // no lock when adding to empty bin
  18.         }
  19.         else if ((fh = f.hash) == MOVED)//如果在进行扩容，则先进行扩容操作
  20.             tab = helpTransfer(tab, f);
  21.         else {
  22.             V oldVal = null;
  23.             //如果以上条件都不满足，那就要进行加锁操作，也就是存在hash冲突，锁住链表或者红黑树的头结点
  24.             synchronized (f) {
  25.                 if (tabAt(tab, i) == f) {
  26.                     if (fh >= 0) { //表示该节点是链表结构
  27.                         binCount = 1;
  28.                         for (Node<K,V> e = f;; ++binCount) {
  29.                             K ek;
  30.                             //这里涉及到相同的key进行put就会覆盖原先的value
  31.                             if (e.hash == hash &&
  32.                                 ((ek = e.key) == key ||
  33.                                  (ek != null && key.equals(ek)))) {
  34.                                 oldVal = e.val;
  35.                                 if (!onlyIfAbsent)
  36.                                     e.val = value;
  37.                                 break;
  38.                             }
  39.                             Node<K,V> pred = e;
  40.                             if ((e = e.next) == null) {  //插入链表尾部
  41.                                 pred.next = new Node<K,V>(hash, key,
  42.                                                           value, null);
  43.                                 break;
  44.                             }
  45.                         }
  46.                     }
  47.                     else if (f instanceof TreeBin) {//红黑树结构
  48.                         Node<K,V> p;
  49.                         binCount = 2;
  50.                         //红黑树结构旋转插入
  51.                         if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  52.                                                        value)) != null) {
  53.                             oldVal = p.val;
  54.                             if (!onlyIfAbsent)
  55.                                 p.val = value;
  56.                         }
  57.                     }
  58.                 }
  59.             }
  60.             if (binCount != 0) { //如果链表的长度大于8时就会进行红黑树的转换
  61.                 if (binCount >= TREEIFY_THRESHOLD)
  62.                     treeifyBin(tab, i);
  63.                 if (oldVal != null)
  64.                     return oldVal;
  65.                 break;
  66.             }
  67.         }
  68.     }
  69.     addCount(1L, binCount);//统计size，并且检查是否需要扩容
  70.     return null;
  71. }
  1. 如果没有初始化就先调用initTable（）方法来进行初始化过程
  2. 如果没有hash冲突，且链表头部为空，就直接CAS插入。
  3. 如果还在进行扩容操作就先将次线程参与到扩容中。
  4. 如果存在hash冲突，就加锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入；
  5. 最后一个如果该链表的数量大于阈值8，就要先转换成黑红树的结构，break再一次进入循环(阿里面试官问题，默认的链表大小，超过了这个值就会转换为红黑树);
  6. 如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容；

2.2 ConcurrentHashMap 如何扩容

【1】当一个线程进行put 时，发现正在扩容，那么此线程会参与到扩容中。
ConcurrentHashMap 支持多个线程同时扩容。
【2】扩容之前先生成一个新数组，在转移元素时，先将原数组分组，将每组分给不同的线程来进行元素的转移，每个线程负责一组或多组的元素转移工作。

引用

https://blog.csdn.net/xingxiupaioxue/article/details/88062163