ConcurrentHashMap基于分段锁+CAS保证线程安全，分段锁基于synchronized

04-16 ConcurrentHashMap（Jdk1.8） - 图1

Put方法

  1. final V putVal(K key, V value, boolean onlyIfAbsent) {
  2.         if (key == null || value == null) throw new NullPointerException();
  3.         //计算 hash 值
  4.         int hash = spread(key.hashCode());
  5.         int binCount = 0;
  6.         //通过自旋的方式来插入数据
  7.         for (Node<K,V>[] tab = table;;) {
  8.             Node<K,V> f; int n, i, fh;
  9.             //如果数组为空，进行数组初始化
  10.             if (tab == null || (n = tab.length) == 0)
  11.                 tab = initTable();
  12.             //计算hash 值对应的数组下标，如果为null，则通过cas来赋值
  13.             //如果赋值成功，则退出自旋
  14.             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  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.             //如果数组当前位置的元素的hash值等于MOVED，表示正在进行扩容，当前线程也进行扩容
  20.             else if ((fh = f.hash) == MOVED)
  21.                 tab = helpTransfer(tab, f);
  22.             else {//到这里就是，f 是该位置的头结点，而且不为空
  23.                 V oldVal = null;
  24.                 synchronized (f) {//锁住该node（该node就是该坐标位置的第一个node）
  25.                     if (tabAt(tab, i) == f) {// 头结点的 hash 值大于 0，说明是链表
  26.                         if (fh >= 0) {
  27.                              //记录链表的长度
  28.                             binCount = 1;
  29.                             for (Node<K,V> e = f;; ++binCount) {
  30.                                 K ek;
  31.                                 //key相等，判断是否要进行值覆盖
  32.                                 if (e.hash == hash &&
  33.                                     ((ek = e.key) == key ||
  34.                                      (ek != null && key.equals(ek)))) {
  35.                                     oldVal = e.val;
  36.                                     if (!onlyIfAbsent)
  37.                                         e.val = value;
  38.                                     break;
  39.                                 }
  40.                                 //了链表的最尾，将这个新值放到链表的最后面（尾插法）
  41.                                 Node<K,V> pred = e;
  42.                                 if ((e = e.next) == null) {
  43.                                     pred.next = new Node<K,V>(hash, key,
  44.                                                               value, null);
  45.                                     break;
  46.                                 }
  47.                             }
  48.                         }
  49.                         else if (f instanceof TreeBin) {// 红黑树
  50.                             Node<K,V> p;
  51.                             binCount = 2;
  52.                             if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  53.                                                            value)) != null) {
  54.                                 oldVal = p.val;
  55.                                 if (!onlyIfAbsent)
  56.                                     p.val = value;
  57.                             }
  58.                         }
  59.                     }
  60.                 }
  61.                 if (binCount != 0) {
  62.                     // 判断是否要将链表转换为红黑树
  63.                     //数组的长大于等于64，而且链表长度大于等于8，会进行树化
  64.                     //否则进行数组扩容
  65.                     if (binCount >= TREEIFY_THRESHOLD)
  66.                         treeifyBin(tab, i);
  67.                     if (oldVal != null)
  68.                         return oldVal;
  69.                     break;
  70.                 }
  71.             }
  72.         }
  73.         addCount(1L, binCount);
  74.         return null;
  75.     }