ConcurrentHashMap

一、分析 Java 8 版本的 ConcurrentHashMap 的重要源码

• Node 节点

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash; 
        final K key; 
        volatile V val;
        volatile Node<K,V>next;
    }
  

• put 方法源码分析

  final V putVal(K key, V value, boolean onlyIfAbsent) { 
      if (key == null || value == null) { 
          throw new NullPointerException(); 
      }
      //计算 hash 值 
      int hash = spread(key.hashCode()); 
      int binCount = 0; 
      for (Node<K, V>[] tab = table; ; ) { 
          Node<K, V> f; 
          int n, i, fh; 
          //如果数组是空的，就进行初始化 
          if (tab == null || (n = tab.length) == 0) { 
              tab = initTable(); 
          }
          // 找该 hash 对应的数组下标 
          else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { 
              //如果该位置是空的，就用 CAS 的方式放入新值 
              if (casTabAt(tab, i, null, 
                  new Node<K, V>(hash, key, value, null))) { 
                  break; 
              } 
          }
          // hash值等于 MOVED 代表在扩容 
          else if ((fh = f.hash) == MOVED) { 
              tab = helpTransfer(tab, f); 
          }
          // 槽点上是有值的情况 
          else {
              V oldVal = null; 
              // 用 synchronized 锁住当前槽点，保证并发安全 
              synchronized (f) { 
                  if (tabAt(tab, i) == f) { 
                      // 如果是链表的形式 
                      if (fh >= 0) { 
                          binCount = 1; 
                          // 遍历链表 
                          for (Node<K, V> e = f; ; ++binCount) { 
                              K ek;
                              // 如果发现该 key 已存在，就判断是否需要进行覆盖，然后返回 
                              if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { 
                                  oldVal = e.val; 
                                  if (!onlyIfAbsent) { 
                                      e.val = value; 
                                  }
                                  break; 
                              } 
                              Node<K, V> pred = e;
                              // 到了链表的尾部也没有发现该 key，说明之前不存在， 就把新值添加到链表的最后 
                              if ((e = e.next) == null) { 
                                  pred.next = new Node<K, V>(hash, key, value, null); 
                                  break; 
                              } 
                         } 
                  }
                  // 如果是红黑树的形式 
                  else if (f instanceof TreeBin) { 
                      Node<K, V> p; 
                      binCount = 2; 
                      // 调用 putTreeVal 方法往红黑树里增加数据 
                      if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key, value)) != null) { 
                          oldVal = p.val; 
                          if (!onlyIfAbsent) { 
                              p.val = value; 
                          } 
                      } 
                  } 
              } 
        }
        if (binCount != 0) {
            // 检查是否满足条件并把链表转换为红黑树的形式，，默认的 TREEIFY_THRESHOLD 阈值是 8 
            if (binCount >= TREEIFY_THRESHOLD) { 
                treeifyBin(tab, i); 
            } 
            // putVal 的返回是添加前的旧值，所以返回 oldVal 
            if (oldVal != null) { 
                return oldVal; 
            } 
            break; 
        } 
      } 
    }
    addCount(1L, binCount); 
    return null; 
  }
  

• get 方法源码分析

  public V get(Object key) { 
      Node<K,V>[] tab; 
      Node<K,V> e, p; 
      int n, eh; 
      K ek; 
      //计算 hash 值 
      int h = spread(key.hashCode()); 
      //如果整个数组是空的，或者当前槽点的数据是空的，说明 key 对应的 value 不存在，直接返回 null 
      if ((tab = table) != null 
          && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) {
          // 判断头结点是否就是我们需要的结点，如果是则直接返回 
          if ((eh = e.hash) == h) { 
              if ((ek = e.key) == key || (ek != null && key.equals(ek))) 
                  return e.val; 
          }
          //如果头结点 hash 值小于 0，说明是红黑树或者正在扩容，就用对应的 find 方法来查找
          else if (eh < 0) 
              return (p = e.find(h, key)) != null ? p.val : null;
          //遍历链表来查找 
          while ((e = e.next) != null) { 
              if (e.hash == h 
                  && ((ek = e.key) == key || (ek != null && key.equals(ek)))) 
                  return e.val; 
         } 
      }
      return null;
  

二、对比 Java 7 和 Java 8 的异同和优缺点

• 数据结构
  Java 7 采用 Segment 分段锁来实现
  Java 8 中的 ConcurrentHashMap 使用数组 + 链表 + 红黑树
  
  
• 并发度
  Java 7 ：每个 Segment 独立加锁，最大并发个数就是 Segment 的个数(默认是 16)
  Java 8 ：锁粒度更细，并发度比之前有提高
• 保证并发安全的原理
  Java 7 ：采用 Segment 分段锁来保证安全
  Java 8 ：采用 Node + CAS + synchronized 保证安全
• 遇到 Hash 碰撞
  Java 7：使用拉链法
  Java 8：先使用拉链法，在链表长度超过一定阈值时，将链表转换为红黑树
• 查询时间复杂度
  Java 7：遍历链表的时间复杂度是 O(n)，n 为链表长度
  Java 8：如果变成遍历红黑树，时间复杂度降低为 O(log(n))，n 为树的节点个数