1 JDK 7 HashMap 并发死链

1.1 死链分析

• jdk7 将遍历到的节点放入到链表头，那么在多线程扩容时就容易出现线程死链问题

流程分析

• 假设 （1） ==> （35） ==> （16） 是一条链

• Thread-0 扩容迁移节点时

  e 	 (1)->(35)->(16)->null
  next (35)->(16)->null
  

• 但此时Thread-1提前扩容完成，先遍历到 （1）再遍历到（35），将后遍历到的（35）方到链表头，（16）迁移到了别处

  newTable[1] (35)->(1)->null
  

• 此时 Thread-0 的 状态为

  e (1)->null
  next (35)->(1)->null
  

• Thread-0将（1）放到头结点

  e (35)->null
  next (1)->null
  

• Thread-0再将（35）放到头结点

  e (1)->null
  next 
  

• Thread-0再将（1）放到头结点，于是死链形成

1.2 死链复现

public static void main(String[] args) {


    // 测试 java 7 中哪些数字的 hash 结果相等
    System.out.println("长度为16时，桶下标为1的key");
    for (int i = 0; i < 64; i++) {
        if (hash(i) % 16 == 1) {
            System.out.println(i);
        }
    }
    System.out.println("长度为32时，桶下标为1的key");
    for (int i = 0; i < 64; i++) {
        if (hash(i) % 32 == 1) {
            System.out.println(i);
        }
    }
    // 1, 35, 16, 50 当大小为16时，它们在一个桶内
    final HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    // 放 12 个元素
    map.put(2, null);
    map.put(3, null);
    map.put(4, null);
    map.put(5, null);
    map.put(6, null);
    map.put(7, null);
    map.put(8, null);
    map.put(9, null);
    map.put(10, null);
    map.put(16, null);
    map.put(35, null);
    map.put(1, null);
    System.out.println("扩容前大小[main]:"+map.size());
    new Thread() {
        @Override
        public void run() {
            // 放第 13 个元素, 发生扩容
            map.put(50, null);
            System.out.println("扩容后大小[Thread-0]:"+map.size());
        }
    }.start();
    new Thread() {
        @Override
        public void run() {
            // 放第 13 个元素, 发生扩容
            map.put(50, null);
            System.out.println("扩容后大小[Thread-1]:"+map.size());
        }
    }.start();
}
final static int hash(Object k) {
    int h = 0;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

1.3 总结

• 究其原因，是因为在多线程环境下使用了非线程安全的 map 集合
• JDK 8 虽然将扩容算法做了调整，不再将元素加入链表头（而是保持与扩容前一样的顺序），但仍不意味着能够在多线程环境下能够安全扩容，还会出现其它问题（如扩容丢数据）

2 JDK 8 ConcurrentHashMap

2.1 重要属性和内部类

// 默认为 0
// 当初始化时, 为 -1
// 当扩容时, 为 -(1 + 扩容线程数)
// 当初始化或扩容完成后，为 下一次的扩容的阈值大小
private transient volatile int sizeCtl;
// 整个 ConcurrentHashMap 就是一个 Node[]
static class Node<K,V> implements Map.Entry<K,V> {}
// hash 表
transient volatile Node<K,V>[] table;
// 扩容时的 新 hash 表
private transient volatile Node<K,V>[] nextTable;
// 扩容时如果某个 bin 迁移完毕, 用 ForwardingNode 作为旧 table bin 的头结点
// 如果获取桶下标的值为ForwardingNode ，就去nextTable中找
static final class ForwardingNode<K,V> extends Node<K,V> {}
// 用在 compute 以及 computeIfAbsent 时, 用来占位, 计算完成后替换为普通 Node
static final class ReservationNode<K,V> extends Node<K,V> {}

// treebin:红黑树
// 当同一个哈希码位置上节点数量超过8，就会尝试转为红黑树
// 转换之前，如果哈希表容量没有达到64，会先尝试扩容来减少链表长度
// 当节点数小于6，又会转换回链表

// 作为 treebin 的头节点, 存储 root 和 first
static final class TreeBin<K,V> extends Node<K,V> {}
// 作为 treebin 的节点, 存储 parent, left, right
static final class TreeNode<K,V> extends Node<K,V> {}

2.2 重要方法

// 获取 Node[] 中第 i 个 Node
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i)

// cas 修改 Node[] 中第 i 个 Node 的值, c 为旧值, v 为新值
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v)

// 直接修改 Node[] 中第 i 个 Node 的值, v 为新值
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v)

2.3 构造器分析

可以看到实现了懒惰初始化，在构造方法中仅仅计算了 table 的大小，以后在第一次使用时才会真正创建

// initialCapacity：初始大小，loadFactor：0.75 扩容阈值，concurrencyLevel：并发度
public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
    if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
        throw new IllegalArgumentException();
    // 初始容量小于并发度
    if (initialCapacity < concurrencyLevel)   // Use at least as many bins
        initialCapacity = concurrencyLevel;   // as estimated threads
    long size = (long)(1.0 + (long)initialCapacity / loadFactor);
    // tableSizeFor 仍然是保证计算的大小是 2^n, 即 16,32,64 ...
    int cap = (size >= (long)MAXIMUM_CAPACITY) ?
        MAXIMUM_CAPACITY : tableSizeFor((int)size);
    this.sizeCtl = cap;
}

2.4 get方法 - 无锁(亮点)

整个get方法中都没有锁

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    // spread 方法能确保返回结果是正数
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) { // (n - 1) & h)就是取模运算，计算桶下标
        // 比较头结点的是否等于h
        if ((eh = e.hash) == h) {
        	// 如果头结点已经是要查找的 key
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        // ForwardingNode 情况，调用ForwardingNode的find()方法去新哈希表中寻找
        // hash 为负数表示该 bin 在扩容中或是 treebin, 这时调用 find 方法来查找
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        // 正常遍历链表, 用 equals 比较
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

2.3 put 流程 - CAS

以下数组简称（table），链表简称（bin）

2.3.1 总体流程

public V put(K key, V value) {
	return putVal(key, value, false);
}
// onlyIfAbsent:false，不更新value；true，覆盖旧值
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    // 其中 spread 方法会综合高位低位, 具有更好的 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)
        	// 初始化 table 使用了 cas, 无需 synchronized 创建成功, 进入下一轮循环
            tab = initTable();
        // 判断桶下标的头结点是否为空，为空，要创建链表头节点
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
        	// 添加链表头使用了 cas, 无需 synchronized
        	// cas失败，进入下一轮循环
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        // 帮忙扩容
        // 如果头结点为ForwardingNode，当前线程会锁住该链表帮助扩容
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else { // 不是扩容情况，并且桶下标是冲突的，在这种情况下开始加锁
            V oldVal = null;
            // 锁住链表头节点 
            synchronized (f) {
           		// 再次确认链表头节点没有被移动
                if (tabAt(tab, i) == f) {
                	// 大于0，普通情况，是链表
                    if (fh >= 0) {
                        binCount = 1;
                        // 遍历链表
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // 找到相同的 key
                            // 1.哈希码是否相等
                            // 2.key是不是同一个对象
                            // 3.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;
                            // 已经是最后的节点了, 新增 Node, 追加至链表尾
                            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;
                        // 先将f转为红黑树节点，再使用putTreeVal 添加节点
                        // putTreeVal 会看 key 是否已经在树中, 是, 则返回对应的 TreeNode
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            // 释放链表头节点的锁
            }
            // 链表长度
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                	// 如果链表长度 >= 树化阈值(8), 进行链表转为红黑树
                	// 会先进行扩容，如果哈希表长度大于64，链表长度还是大于8，就会转为红黑是
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // 增加 size 计数
    addCount(1L, binCount);
    return null;
}

2.3.2 细节之initTable()

保证原子性

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
    	// sizeCtl 为 -1，表示线程正在创建中，会让出cpu
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
        // cas尝试将 sizeCtl 设置为 -1（表示初始化 table）
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
            	// 获得锁, 创建 table, 这时其它线程会在 while() 循环中 yield 直至 table 创建
                if ((tab = table) == null || tab.length == 0) {
                	// 根据初始值设置，默认为16
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    // 计算出下次扩容的阈值
                    sc = n - (n >>> 2);
                }
            } finally {
            	// 将 sizeCtl 设为 容量，让其它线程退出循环
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

2.3.3 细节之addCount()

• 有两个作用
  • 维护整个HashMap的size计数
  • 如果size计数超过阈值，就会进行扩容操作

// x:计数值1L check:链表长度
private final void addCount(long x, int check) {
    CounterCell[] as; long b, s;
    // 已经有了 counterCells, 向 cell 累加
    if ((as = counterCells) != null ||
    	// 还没有, 向 baseCount 累加
        !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        CounterCell a; long v; int m;
        boolean uncontended = true;
        // 还没有 counterCells
        if (as == null || (m = as.length - 1) < 0 ||
        	// 还没有 cell，累加单元
            (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
            // cell cas 增加计数失败
            !(uncontended =  U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
            fullAddCount(x, uncontended);
            return;
        }
        if (check <= 1)
            return;
        // 获取元素个数，是否扩容
        s = sumCount();
    }
    if (check >= 0) {
        Node<K,V>[] tab, nt; int n, sc;
        while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
               (n = tab.length) < MAXIMUM_CAPACITY) {
            int rs = resizeStamp(n);
            if (sc < 0) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)
                    break;
                // newtable 已经创建了，帮忙扩容
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            // 需要扩容，这时 newtable 未创建
            else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                         (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null);
            s = sumCount();
        }
    }
}

2.4 size计算流程

• size 计算实际发生在 put，remove 改变集合元素的操作之中
  • 没有竞争发生，向 baseCount 累加计数
  • 有竞争发生，新建 counterCells，向其中的一个 cell 累加计数
    • counterCells 初始有两个 cell
    • 如果计数竞争比较激烈，会创建新的 cell 来累加计数

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
            (int)n);
}

final long sumCount() {
    CounterCell[] as = counterCells; CounterCell a;
    long sum = baseCount;
    // 将 baseCount 计数与所有 cell 计数累加
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;
        }
    }
    return sum;
}

2.5 扩容流程

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
  int n = tab.length, stride;
  if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
      stride = MIN_TRANSFER_STRIDE; // subdivide range
  if (nextTab == null) {            // initiating nextTab
      try {
          @SuppressWarnings("unchecked")
          // 将原始数值值移位，就是乘2
          Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
          nextTab = nt;
      } catch (Throwable ex) {      // try to cope with OOME
          sizeCtl = Integer.MAX_VALUE;
          return;
      }
      nextTable = nextTab;
      transferIndex = n;
  }
  int nextn = nextTab.length;
  ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
  boolean advance = true;
  boolean finishing = false; // to ensure sweep before committing nextTab
  // 以链表为单位进行移动
  for (int i = 0, bound = 0;;) {
      Node<K,V> f; int fh;
      while (advance) {...}
      if (i < 0 || i >= n || i + n >= nextn) {...}
      // 链表头为空，表示处理完成，将链表头替换成ForwardingNode
      else if ((f = tabAt(tab, i)) == null)
          advance = casTabAt(tab, i, null, fwd);
      // 已经是 ForwardingNode，表示已经处理
      else if ((fh = f.hash) == MOVED)
          advance = true; // already processed
      else {// 链表头有元素，就锁住头元素进行处理
          synchronized (f) {
              if (tabAt(tab, i) == f) {
                  Node<K,V> ln, hn;
                  // 哈希值大于0，普通节点
                  if (fh >= 0) {...}
                  // 红黑树逻辑
                  else if (f instanceof TreeBin) {...}
              }
          }
      }
  }
}

2.6 总结

Java 8 数组（Node） +（ 链表 Node | 红黑树 TreeNode ） 以下数组简称（table），链表简称（bin）

• 初始化，使用 cas 来保证并发安全，懒惰初始化 table
• 树化，当 table.length < 64 时，先尝试扩容，超过 64 时，并且 bin.length > 8 时，会将链表树化，树化过程会用 synchronized 锁住链表头
• put，如果该 bin 尚未创建，只需要使用 cas 创建 bin；如果已经有了，锁住链表头进行后续 put 操作，元素添加至 bin 的尾部
• get，无锁操作仅需要保证可见性，扩容过程中 get 操作拿到的是 ForwardingNode 它会让 get 操作在新table 进行搜索
• 扩容，扩容时以 bin 为单位进行，需要对 bin 进行 synchronized，但这时妙的是其它竞争线程也不是无事可做，它们会帮助把其它 bin 进行扩容，扩容时平均只有 1/6 的节点会把复制到新 table 中
• size，元素个数保存在 baseCount 中，并发时的个数变动保存在 CounterCell[] 当中。最后统计数量时累加即可

3 JDK 7 ConcurrentHashMap - TODO