ConcurrentHashMap

java并发包中的最常用类，我们来剖析下

我的环境是JDK8，JDK9中的实现变化并不大；不过JDK9中提供了UnSafe类的源码，待我撕完这个Map，我再来看UnSafe

JDK7中，ConcurrentHashMap是用分段锁来实现的，初始使用了16把分段锁，来分段主管整个Map，你要操作，具体的自行研究吧，总之是个淘汰的技术；

JDK8的加锁粒度更低，是到每个hash槽级别，并且并发都是用的UnSafe类的CompareAndSwap实现，更底层，性能更好；

先来看看创建一个ConcurrentHashMap：
ConcurrentHashMap<Integer,Integer> map = new ConcurrentHashMap<>();
不指定初始化容量的话，初始是16

/**
     * Creates a new, empty map with the default initial table size (16).
     */
    public ConcurrentHashMap() {
    }

指定容量的话,会处理比指定容量大一点的2的N次方
比如指定的1101=13，首先进行initialCapacity + (initialCapacity >>> 1) + 1=1101+110+1=10100=20
进入方法tableSizeFor后，首先减一n = c - 1=10011
进行了一连串的|=操作，10011|1001=11011|110=11111|....
最后+1=100000=32，没有取到16，比1101=13；

public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }
private static final int tableSizeFor(int c) {
        int n = c - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

我来解释下这一连串的|=骚操作，取自书籍《Hackers Delight, sec 3.2》
目标是把后面全部补全1，一直到n |= n >>> 16能把32位长的int给补全了

n=举个例子                        1 0 0 0 0 0 0
n |= n >>> 1;                    1 1 0 0 0 0 0
n |= n >>> 2;                    1 1 1 1 0 0 0
n |= n >>> 4;                    1 1 1 1 1 1 1
n |= n >>> 8;              
n |= n >>> 16;

初始化到这里基本就挖完了，要想效率高，通用的位移方法都是最搞笑的，mark一下，回头把《Hackers Delight》给啃了，应该是本好书

接下来就要看看put方法了：
直接写注解了，看官看注解吧

public V put(K key, V value) {
        return putVal(key, value, false);
    }

    /** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        //入参判空
        if (key == null || value == null) throw new NullPointerException();
       //hash值处理，高位传播至低位(h ^ (h >>> 16)) & HASH_BITS
       //主要是为了防撞
        int hash = spread(key.hashCode());
        int binCount = 0;
        //开启一个循环，同时还定义了个变量，并赋值，JDK老那么搞，为了节约代码行数么^v^
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            //tab空的就初始化吧
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            //这个格子没有值，那就通过CAS操作塞值进去
            //失败的话就走到了尽头，重新开始这个循环重新判断
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            //这种情况是正在扩容，就加入扩容流程，看看应该放到哪里去
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            //走到这里，表示这个格子里有值，你得用链表或者B数来加进去了
            else {
                V oldVal = null;
                //同一个格子发生同时put的概率不太大，直接悲观锁同步吧，按顺序执行，免得还要考虑并发问题
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            //这里是挂链表
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                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;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        //这里是加到B树中
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                //这里是判断是否需要改成B树了
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

以上的亮点，主要是两个：
一个是使用了synchronized同步，由于JAVA9中其实对synchronized优化已经很大，而且这种场景下，发生碰撞的概率并不大，概率大那hash本身就是有问题了，所以用synchronized并不慢，我们实际用技术的时候，也要根据业务场景来，并不能执着于优化，也要区分发生这种情况的概率；
二是使用了B树，在一定条件下即转成了B树而不是一直扩容map本身和使用链表，条件是tab容量达到了64，链表数量达到了8
static final int MIN_TREEIFY_CAPACITY = 64;
static final int TREEIFY_THRESHOLD = 8;

我们来看看求长度的size()方法

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;
        if (as != null) {
            for (int i = 0; i < as.length; ++i) {
                if ((a = as[i]) != null)
                    sum += a.value;
            }
        }
        return sum;
    }

计数是提前就维护好的，但是不是一个变量，是一个数组；
每次都要将数组中的值加起来才行
为啥那么做，在并发状态下，又想准确计数，计数的时候需要同步(猜猜也知道肯定是cas来递增的)，又想高并发，就有种老版本中分段锁的味道了。
未完待续......