一、分析 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 为树的节点个数