ConcurrentHashMap

1.ConcurrentHashMap信息

jdk1.7Segment 数组+HashEntry链表，数组分段锁
final Segment<K,V>[] segments;
jdk1.8数组+链表+红黑树，CAS+synchronized

CAS原理
https://www.jianshu.com/p/5d90ebfe8c2d

2.ConcurrentHashMap内部结构

   /**
     * table数组( Node类型)，保存元素
     */
    transient volatile Node<K,V>[] table;

    /**
     * 控制标识符
     * = 0 表示hash表还未初始化，
     * > 0 当在初始化的时候指定了大小，这会将这个大小保存在sizeCtl中，大小为数组的0.75
     * = -1 表示正在进行初始化操作；  
     * = -N 表示有N-1个线程正在进行扩张
     */
    private transient volatile int sizeCtl;

    /**
     * 转移的时候用的数组
     */
    private transient volatile Node<K,V>[] nextTable;
    
    /** 
     * 内部类结构  实现链表
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;  //final类型 key的hash值
        final K key;  //final类型
        volatile V val;  // volatile类型  保证可见性，避免读加锁
        volatile Node<K,V> next; //表示链表中的下一个节点

        Node(int hash, K key, V val, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }

3.ConcurrentHashMap构造器

构造ConcurrentHashMap时，并没有进行初始化，初始化是在插入第一个元素时进行的，这与其他集合类设计一致（懒加载）。

  /**
     * Creates a new, empty map with the default initial table size (16).
     * 空map，默认数组长度16，sizeCtl=0
     */
    public ConcurrentHashMap() {
    }

    /**
     * 指定容量创建
     * 初始化sizeCtl
     */
    public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        // tableSizeFor
        this.sizeCtl = cap;
    }

    /**
     * 初始容量initialCapacity，加载因子loadFactor
     */
    public ConcurrentHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, 1);
    }

    /**
     * 初始容量initialCapacity，加载因子loadFactor，预估并发度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);
        int cap = (size >= (long)MAXIMUM_CAPACITY) ?
            MAXIMUM_CAPACITY : tableSizeFor((int)size);
        this.sizeCtl = cap;
    }

    /**
     *  找到大于或等于 cap 的最小2的幂 同hashmap，arraydeque
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 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;
    }

4.get方法

定位键值对所在桶的位置(hash) -> 如果定位到了该位置，key是否与链表第一个相同，相同则返回 -> 如果key值不同，则遍历链表，直到找到key值相同

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 1.定位键值对所在桶的位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 当 tab.length为2的n次幂时 (tab.length - 1) & hash == hash % tab.length
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                // 2.查找
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    // 2. 查找链表
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

5.put方法

遍历查找键值对桶位置(hash)
-> 首次初始化
-> 如果当前位置无数据，则CAS新增元素到当前位置
-> 如果当前位置有数据，但数据的hash值为MOVED，协助扩容
-> 如果当前位置有数据，且数据有效，锁住该位置，hash冲突场景
-> sync锁住头结点，遍历链表，如果链表存在key与入参key相同则替换否则新增至链表尾
-> 链表的长度超过阀值则树化

   /**
     * Maps the specified key to the specified value in this table.
     * Neither the key nor the value can be null.
     *
     */
    public V put(K key, V value) {
        return putVal(key, value, false);
    }

    final V putVal(K key, V value, boolean onlyIfAbsent) {
        // key,value都不支持null
        if (key == null || value == null) throw new NullPointerException();
        // 将key的hash值进行再hash，让hash值的高位也参与hash运算，从而减少哈希冲突，类似hashmap
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            // 第一次添加数据，懒加载初始化table
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            // 定位桶数组位置 (n - 1) & hash) 小亮点同hashmap
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                // 当前数组元素为空，cas put元素，这里没有加锁
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;  // no lock when adding to empty bin
            }
            // 当前节点的hash值是MOVED=-1，表示当前map正有线程在扩容，先协助扩容再更新值
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                // hash冲突
                V oldVal = null;
                // hash冲突加锁处理
                synchronized (f) {
                    // 链表头节点处理
                    if (tabAt(tab, i) == f) {
                        // 如果转为树的话hash值为-2，前边扩容hash值为-1
                        if (fh >= 0) {
                            binCount = 1;
                            // 遍历链表
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                // hash，key相同，节点已经存在，更新处理
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                // 同key，不同hash，继续添加新节点到链表尾部，同hashmap
                                Node<K,V> pred = e;
                                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;
                            // 添加该元素到树中
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                // 链表长度达到8后转为红黑树
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        // 树化 详见扩容机制
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        // 计数 详见扩容机制
        addCount(1L, binCount);
        return null;
    }

    // Unsafe类文档待补充
    // Unsafe类getObjectVolatile()方法获取value值，volatile修饰保证可见性，从而保证其是当前最新值
    static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
    }

    static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }

    static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }

6.1.扩容机制

扩容条件：1.达到阈值后扩容，扩容会rehashing，重新计算位置，一种为原位置，一种为原下标+原容量。2.链上长度达到阈值8，但是数组长度不到64，同1扩容rehashing。3.链表长度达到阈值8，数组长度达到64，链表转红黑树。同hashmap。

   /**
     * Initializes table, using the size recorded in sizeCtl.
     * 初始化扩容机制
     */
    private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        // 空数组或长度为0，初始化
        while ((tab = table) == null || tab.length == 0) {
            // sizeCtl<0，意味着另外的线程执行CAS成功在初始化表或扩展表，当前线程只需要让出cpu时间片
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // lost initialization race; just spin
            //SIZECTL：表示当前对象的内存偏移量，sc表示期望值，-1表示要替换的值，设定为-1表示初始化表
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        // 指定长度或默认长度
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        // 0.75*capacity
                        sc = n - (n >>> 2);
                    }
                } finally {
                    // 0.75*capacity
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

    /**
     * Replaces all linked nodes in bin at given index unless table is
     * too small, in which case resizes instead.
     * 链表转树条件：数组长度>=64，且链表长度>=8 同hashmap
     */
    private final void treeifyBin(Node<K,V>[] tab, int index) {
        Node<K,V> b; int n, sc;
        if (tab != null) {
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                // 如果table.length<64 扩容一倍
                tryPresize(n << 1);
            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
                synchronized (b) {
                    if (tabAt(tab, index) == b) {
                        TreeNode<K,V> hd = null, tl = null;
                        for (Node<K,V> e = b; e != null; e = e.next) {
                            // 链表节点转树节点
                            TreeNode<K,V> p =
                                new TreeNode<K,V>(e.hash, e.key, e.val,
                                                  null, null);
                            if ((p.prev = tl) == null)
                                hd = p;
                            else
                                tl.next = p;
                            tl = p;
                        }
                        // synchronized赋值，则不需要cas
                        setTabAt(tab, index, new TreeBin<K,V>(hd));
                    }
                }
            }
        }
    }

    /**
     * 计数扩容机制
     * 1.对 table 的长度加一。通过修改 baseCount，或者使用 CounterCell
     * 2.扩容机制
     *
     * check = binCount 默认是0
     * hash冲突：binCount=链表长度
     * 红黑树：binCount = 2
     *
     */
    private final void addCount(long x, int check) {
        CounterCell[] as; long b, s;
        // CAS更新baseCount
        if ((as = counterCells) != null ||
            !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
             // counterCells非空 或 修改 baseCount 失败
            CounterCell a; long v; int m;
            boolean uncontended = true;
            if (as == null || (m = as.length - 1) < 0 ||
                (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                !(uncontended =
                  U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
                // 多线程修改baseCount时，竞争失败的线程会执行fullAddCount，
                // 把x的值插入到counterCell类中，出现并发使用counterCell
                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);
                // sc = sizeCtl  -N代表有n-1个线程在扩容
                if (sc < 0) {
                    // sc 是一个本地变量， 进入if(sc<0) 这个分支以后， 值没有再改变， 
                    // rs 是 resizeStamp 的返回结果， 是一个正值， 按理来说 sc 是不可能等于 rs + 1 的。
                    // 这里有bug，已被用户“[萧萧_03c6]”发现并提交oracle-jdk-bug库
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        // 其他线程正在扩容，协助扩容
                        transfer(tab, nt);
                }
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    // 仅当前线程在扩容
                    transfer(tab, null);
                s = sumCount();
            }
        }
    }

6.2扩容方法

构建一个nextTable，大小为table两倍
-> 计算一个步长，表示“每个线程处理的数组长度”，用来控制对CPU的使用
-> 每个CPU最少处理16个长度的数组元素,也就是说，如果一个数组的长度只有16，那只有一个线程会对其进行扩容的复制移动操作
-> 计算table某个位置索引 i,该位置上的数据将会被转移到nextTable 中
-> 如果索引i所对应的table的位置上没有存放数据，则放ForwardingNode数据，表明该table 正在进行扩容处理。如果有添加数据的线程添加数据到该位置上，将会发现table的状态。
-> 将索引i位置上的数据进行转移，数据分成两部分，一部分就是数据在nextTable中索引没有变（仍然是i），另一部分则是其索引变成i+n的，将这两部分分别添加到nextTable 中

  /**
    * 过渡节点，当hash 表进行扩容数据转移的时候，其它线程如果还在往原hash 表中添加数据，
    * 这个肯定是有问题的，因此就引入了ForwardingNode节点。
    * 当对原hash 表进行数据转移时，如果hash 表中的位置还没有数据，
    * 那么就存放ForwardingNode 节点，表明现在hash 表正在进行扩容转移数据阶段。
    * 这样，其它线程在操作的时候，遇到ForwardingNode 节点，就知道hash 现在的状态了。
    * 这样就可以协助参与hash表的扩容过程。
    */
    static final class ForwardingNode<K,V> extends Node<K,V> {
        final Node<K,V>[] nextTable;
        ForwardingNode(Node<K,V>[] tab) {
            super(MOVED, null, null, null);
            this.nextTable = tab;
        }
    }
    
    private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        int n = tab.length, stride;
        // CPU步长控制
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
            stride = MIN_TRANSFER_STRIDE; // subdivide range
        
        // 初始化一个table两倍长的nextTab
        if (nextTab == null) {            // initiating
            try {
                @SuppressWarnings("unchecked")
                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;
            // 转移角标值  老table长度
            transferIndex = n;
        }
        int nextn = nextTab.length;
        // 空节点标志 hash值为MOVED[-1] 并发控制，其他线程发现为该节点则跳过
        ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
        boolean advance = true;
        boolean finishing = false; // to ensure sweep before committing nextTab
        // 遍历每个角标中的链表元素，通过CAS设置transferIndex属性值        
        // i指当前处理的角标，bound指当前线程可以处理的桶区间最小下标
        for (int i = 0, bound = 0;;) {
            Node<K,V> f; int fh;
            // 多线程控制角标i--  通过i--可以依次遍历原hash表中的节点
            while (advance) {
                int nextIndex, nextBound;
                if (--i >= bound || finishing)
                    // i初始赋值为当前线程可以处理的最大角标，bound为当前线程可以处理的最小角标
                    // 则当i角标可执行范围执行完毕后，需要在后边重新申领i的最大角标
                    advance = false;
                else if ((nextIndex = transferIndex) <= 0) {
                    i = -1;
                    advance = false;
                }
                // CAS 修改 transferIndex，即 length - 区间值，留下剩余的区间值供后面的线程使用
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {
                    // 当前线程可以处理的桶区间最小角标
                    bound = nextBound;
                    // 申领为当前线程可以处理的最大角标
                    i = nextIndex - 1;
                    advance = false;
                }
            }
            if (i < 0 || i >= n || i + n >= nextn) {
                int sc;
                //所有节点完成复制，nextTable赋值给table 清空临时对象nextTable 
                if (finishing) {
                    nextTable = null;
                    table = nextTab;
                    // 阈值=1.5*原=0.75*现
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }
                // CAS更新这个扩容阈值，sizectl值每减一，代表新加一个线程参加了扩容
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        // 有线程在辅助扩容
                        return;
                    // 最后一个辅助线程完成扩容
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            // 角标i的位置上没有数据，则放入ForwardingNode指针 
            else if ((f = tabAt(tab, i)) == null)
                advance = casTabAt(tab, i, null, fwd);
            // 如果遍历到ForwardingNode节点，hash值为MOVED[-1]  说明这个角标已经被处理过 直接跳过
            else if ((fh = f.hash) == MOVED)
                advance = true; // already processed
            else {
                // 当前角标有实际值且非占位符，加锁，防止往老数组上填加数据
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        Node<K,V> ln, hn;
                        if (fh >= 0) { // 链表节点
                            // 因为n的值为数组的长度，且是2的幂次，即在&操作的结果只可能是0或者n
                             // 即 0-->放在新表的相同位置 n-->放在新表的（n+原来位置）
                            int runBit = fh & n;
                            Node<K,V> lastRun = f;
                            // 生成两个链表
                            for (Node<K,V> p = f.next; p != null; p = p.next) {
                                int b = p.hash & n;
                                if (b != runBit) {
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                            if (runBit == 0) {
                                ln = lastRun;
                                hn = null;
                            }
                            else {
                                hn = lastRun;
                                ln = null;
                            }
                            for (Node<K,V> p = f; p != lastRun; p = p.next) {
                                int ph = p.hash; K pk = p.key; V pv = p.val;
                                if ((ph & n) == 0)
                                    ln = new Node<K,V>(ph, pk, pv, ln);
                                else
                                    hn = new Node<K,V>(ph, pk, pv, hn);
                            }
                            //在nextTable的i位置上插入一个链表
                            setTabAt(nextTab, i, ln);
                            //在nextTable的i+n的位置上插入另一个链表
                            setTabAt(nextTab, i + n, hn);
                            //在table的i位置上插入forwardNode节点  表示已经处理过该节点
                            setTabAt(tab, i, fwd);
                            //设置advance为true 返回到上面的while循环中 就可以执行i--操作，开始下一角标处理
                            advance = true;
                        }
                        // 树
                        else if (f instanceof TreeBin) {
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            TreeNode<K,V> lo = null, loTail = null;
                            TreeNode<K,V> hi = null, hiTail = null;
                            int lc = 0, hc = 0;
                            for (Node<K,V> e = t.first; e != null; e = e.next) {
                                int h = e.hash;
                                TreeNode<K,V> p = new TreeNode<K,V>
                                    (h, e.key, e.val, null, null);
                                if ((h & n) == 0) {
                                    if ((p.prev = loTail) == null)
                                        lo = p;
                                    else
                                        loTail.next = p;
                                    loTail = p;
                                    ++lc;
                                }
                                else {
                                    if ((p.prev = hiTail) == null)
                                        hi = p;
                                    else
                                        hiTail.next = p;
                                    hiTail = p;
                                    ++hc;
                                }
                            }
                            // <=6个节点 树转链表 
                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                                (hc != 0) ? new TreeBin<K,V>(lo) : t;
                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                (lc != 0) ? new TreeBin<K,V>(hi) : t;
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                    }
                }
            }
        }
    }

    /**
     * Helps transfer if a resize is in progress.
     * table不为空，且key对应的Node节点也不为空，但Node头结点的hash值为MOVED(-1)，则表示需要扩容，此时扩容
     */
    final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
        Node<K,V>[] nextTab; int sc;
        if (tab != null && (f instanceof ForwardingNode) &&
            (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
            int rs = resizeStamp(tab.length);
            // sizeCtl  < 0 表明还在扩容
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {
                // 判断标识符是否变化，判断扩容是否结束，判断是否达到最大线程数，判断扩容转移下标是否在调整（扩容结束），如果满足任意条件，结束循环。
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
                    break;
                // sizeCtl + 1 表明增加了一个线程帮助扩容
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                    transfer(tab, nextTab);
                    break;
                }
            }
            return nextTab;
        }
        return table;
    }

7.remove方法

定位键值对所在桶的位置
-> 如果节点hash值为MOVED则帮助扩容
-> hash冲突则加锁sync锁住该位置
-> 遍历链表/红黑树查找删除节点

final V replaceNode(Object key, V value, Object cv) {
    int hash = spread(key.hashCode());
    // 遍历数组
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        // hash不存在
        if (tab == null || (n = tab.length) == 0 ||
            (f = tabAt(tab, i = (n - 1) & hash)) == null)
            break;
        // 正在扩容，协助扩容    
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            boolean validated = false;
            // 加锁 锁住该位置
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        validated = true;
                        // 遍历链表
                        for (Node<K,V> e = f, pred = null;;) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                V ev = e.val;
                                if (cv == null || cv == ev ||
                                    (ev != null && cv.equals(ev))) {
                                    oldVal = ev;
                                    if (value != null)
                                        e.val = value;
                                    else if (pred != null)
                                        // 非链表头节点，直接删除该节点
                                        pred.next = e.next;
                                    else
                                        // 更新链表头节点 - 更新后继
                                        setTabAt(tab, i, e.next);
                                }
                                break;
                            }
                            pred = e;
                            if ((e = e.next) == null)
                                break;
                        }
                    }
                    // 树
                    else if (f instanceof TreeBin) {
                        validated = true;
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> r, p;
                        if ((r = t.root) != null &&
                            (p = r.findTreeNode(hash, key, null)) != null) {
                            V pv = p.val;
                            if (cv == null || cv == pv ||
                                (pv != null && cv.equals(pv))) {
                                oldVal = pv;
                                if (value != null)
                                    p.val = value;
                                // 树中删除节点，树太小则转链表
                                else if (t.removeTreeNode(p))
                                    setTabAt(tab, i, untreeify(t.first));
                            }
                        }
                    }
                }
            }
            if (validated) {
                if (oldVal != null) {
                    if (value == null)
                        addCount(-1L, -1);
                    return oldVal;
                }
                break;
            }
        }
    }
    return null;
}

8.size方法

结果不一定准确

    /**
     * int最大值限制
     */ 
    public int size() {
        long n = sumCount();
        return ((n < 0L) ? 0 :
                (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                (int)n);
    }

    /**
     * 代替size()方法
     */
    public long mappingCount() {
        long n = sumCount();
        return (n < 0L) ? 0L : n; // ignore transient negative values
    }

    /**
     * baseCounter和数组里每个CounterCell的值之和
     * 多线程同时执行CAS修改baseCount值，失败的线程会将值放到CounterCell中
     */
    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;
    }

9.遍历fail-safe

(1)需要复制集合，产生大量的无效对象，开销大
(2)在复制的集合进行遍历，遍历过程对原集合的修改不会被迭代器检测，不会触发Concurrent Modification Exception
(3)遍历期间原集合发生的修改迭代器是不知道的
(4)无法保证读取的数据是目前原始数据结构中的数据

       /**
         * @return an iterator over the entries of the backing map
         */
        public Iterator<Map.Entry<K,V>> iterator() {
            // 复制的集合，遍历操作基于该集合操作
            ConcurrentHashMap<K,V> m = map;
            Node<K,V>[] t;
            int f = (t = m.table) == null ? 0 : t.length;
            return new ConcurrentHashMap.EntryIterator<K,V>(t, f, 0, f, m);
        }

相关：
https://www.jianshu.com/p/29d8e66bc3bf
https://www.cnblogs.com/yuluoxingkong/p/9265730.html
https://blog.csdn.net/u014634338/article/details/78796357
https://blog.csdn.net/programmer_at/article/details/79715177#143-transfer
https://www.cnblogs.com/zerotomax/p/8687425.html#go7