GVKun编程网logo

java源码学习---ConcurrentHashMap(java concurrenthashmap原理)

11

想了解java源码学习---ConcurrentHashMap的新动态吗?本文将为您提供详细的信息,我们还将为您解答关于javaconcurrenthashmap原理的相关问题,此外,我们还将为您介绍

想了解java源码学习---ConcurrentHashMap的新动态吗?本文将为您提供详细的信息,我们还将为您解答关于java concurrenthashmap原理的相关问题,此外,我们还将为您介绍关于ConcurrentHashMap 与同步 HashMap - ConcurrentHashMap vs Synchronized HashMap、ConcurrentHashMap源码分析-Java8、ConcurrentHashMa源码、HashMap、Hashtable、ConcurrentHashMap、ConcurrentSkipListMap对比及java并发包(java.util.concurrent)的新知识。

本文目录一览:

java源码学习---ConcurrentHashMap(java concurrenthashmap原理)

java源码学习---ConcurrentHashMap(java concurrenthashmap原理)

ConcurrentHashMap与 HashMap 一样,都是键值对数据存储结构,不过 HashMap 是非线程安全,而ConcurrentHashMap是线程安全的,说起线程安全又不得不与HashTable对比一下,HashTable相比ConcurrentHashMap效率低,接下来看看ConcurrentHashMap到底是如何保证线程安全且比HashTable优秀(JDK1.8)

还是从put()开始

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

put()会再调一个putValue(),因为要传入 onlyIfAbsent 参数同意更新元素,与HashMap不一样的是 key的散列算法不是在put()完成,而是在putValue()完成

/**
 * key:储存到HashMapkey
 * value:储存到HashMapkey对应的value
 * onlyIfAbsent:如果包含了该key,则不更新对应的值,众所周知,put()除了新增之外,还有更新的功能,是因为put()调用putVal()时候传的都是false
 */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    //ConcurrentHashMap的键值都不允许为null
    if (key == null || value == null) throw new NullPointerException();
    //计算keyhash    int hash = spread(key.hashCode());
    // 记录当前储存的位置是否需要转行成红黑树结构
    int binCount = 0;
    // 循环ConcurrentHashMapNode数组,找出对于存储的位置
    for (ConcurrentHashMap.Node<K,V>[] tab = table;;) {
        // 定义了几个变量:
        // f:存放在数组相同下标位置的第一个元素
        // n:当前ConcurrentHashMapNode数组的长度
        // i:当前存储元素需要存放的数组下标
        // fh : 存放在数组相同下标位置的第一个元素的hash        ConcurrentHashMap.Node<K,V> f; int n, i, fh;
        // 判断ConcurrentHashMapNode数组长度,如果等于null或者长度等于0的情况,则进行扩容操作
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        // 判断当前元素需要存储的数组位置是否为null,如果是null的情况下则尝试存放数据
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 这里使用了CAS操作(乐观锁),尝试存放元素,如果元素存放成功则直接结束当前put(),否则继续找位置
            if (casTabAt(tab, i, null,
                    new ConcurrentHashMap.Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        // 这里判断当前ConcurrentHashMap是否正在进行扩容操作
        // 如果是在进行扩容操作,则当前线程也帮忙扩容,并且存放元素
        else if ((fh = f.hash) == MOVED)
            // 帮忙进行扩容操作,helpTransfer() 这个函数是帮助正在扩容的线程
            // 一起进行扩容操作并且存放元素
            tab = helpTransfer(tab, f);
        else {
            // 定义了一个指向旧值的变量,当本次put()操作是更新操作时,则使用该变量指向旧值
            // 并且更新完成之后返回旧值
            V oldVal = null;
            // 上面也说过 f 是每个相同元素下标位置的首个元素,
            // 这里对 f 进行了加锁,这样能锁住所有即将存在 i 位置元素的put()操作
            // 并且不影响其他下标位置的元素插入,相比HashTable的方法锁大大提高了性能
            synchronized (f) {
                // 如果 f 没又改变,则继续操作,否则重复第一个循环
                if (tabAt(tab, i) == f) {
                    // 判断当前节点是否链表节点
                    if (fh >= 0) {
                        // 记录当前储存的位置是否需要转行成红黑树结构
                        binCount = 1;
                        // 遍历链表找出存放的位置
                        for (ConcurrentHashMap.Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // 如果遍历到的节点 key一致,则进行更新操作 并且oldVal变量存储旧值,用于后续返回
                            if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                            (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            // 如果一致没有相同的key,则在链表最后添加新节点
                            ConcurrentHashMap.Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new ConcurrentHashMap.Node<K,V>(hash, key,
                                        value, null);
                                break;
                            }
                        }
                    }
                    // 如果当前数组下标节点等于 TreeBin 的时候,则进行按红黑树规则进行添加或修改操作
                    else if (f instanceof ConcurrentHashMap.TreeBin) {
                        ConcurrentHashMap.Node<K,V> p;
                        binCount = 2;
                        if ((p = ((ConcurrentHashMap.TreeBin<K,V>)f).putTreeVal(hash, key,
                                value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            // 判断当前链表的长度是否需要转换成红黑树结构
            // static final int TREEIFY_THRESHOLD = 8;
            // 当链表长度大于等于 8 的时候,则进行转换成红黑树操作
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // 记录当前ConcurrentHashMap长度并且判断是否需要进行扩容操作
    addCount(1L, binCount);
    return null;
}
// 表示当前table正在进行扩容操作
static final int MOVED     = -1; // hash for forwarding nodes
// 用于管理TreeNode,标记元素数据结构为红黑树时
static final int TREEBIN   = -2; // hash for roots of trees

put()操作使用了synchronized 与CAS乐观锁,当存储在数组相同位置的元素为null时候,会使用CAS操作进行尝试存储,如果存储成功则直接走最后的记录长度和判断是否需要扩容流程。数组相同位置的元素不为null,则先使用 synchronized 锁住该对象,这样就锁住了该数组下标的整个数据结构(链表或者红黑树的管理者TreeBin)再进行与HashMap大致相同的链表或者红黑树存储规则

下面随便画了一个 此处 synchronized 锁的图

接下来看看初始化容量函数 initTable()

private final ConcurrentHashMap.Node<K,V>[] initTable() {
    ConcurrentHashMap.Node<K,V>[] tab; int sc;
    // 判断当前ConcurrentHashMap数组长度是否需要扩容
    while ((tab = table) == null || tab.length == 0) {
        // 判断是否有其他线程在进行初始化容量操作
        // 如果 sizeCtl < 0 则说明有其他线程在进行初始化容量操作
        if ((sc = sizeCtl) < 0)
            // 如果有其他线程在进行初始化容量,则降低当前线程的优先级
            Thread.yield(); // lost initialization race; just spin
        // 如果没有其他线程进行初始化容量则使用CAS操作尝试获取到初始化容量的资格
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                // 再判断一次是否需要初始化容量
                // 当首个线程先取得初始化容量资格时候,很大可能已经完成了
                // 其他减低了优先级的线程即使再获取到容量初始化资格都会被该判断阻挡
                if ((tab = table) == null || tab.length == 0) {
                    // 获取默认初始化容量
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    // 初始化ConcurrentHashMap 数组
                    @SuppressWarnings("unchecked")
                    ConcurrentHashMap.Node<K,V>[] nt = (ConcurrentHashMap.Node<K,V>[])new ConcurrentHashMap.Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    // 返回初始化的数组
    return tab;
}

initTable()主要也还是使用到了CAS操作,使只有一个线程经常初始化,并且table使用了volatile修饰线程共享资源,初始化一旦完成,其他线程立马知道了该table已经初始化,在高并发多线程情况下,有些被降低了优先级的线程后面也会通过CAS获取到初始化资格,但是下面还有一个判断table的长度,就无需再进行扩容操作了,所以ConcurrentHashMap的容量初始化是由双重校验+CAS+volatile保证了其线程安全。HashMap里面扩容与初始化容量都是同一个函数,而ConcurrentHashMap则是分开了2个函数,初始化容量一个,扩容一个(transfer())

transient volatile Node<K,V>[] table;

下面看看扩容函数 transfer()与协助扩容函数 helpTransfer()

/**
 *  tab:当前的table
 *  nextTab:扩容后的table
 */
private final void transfer(ConcurrentHashMap.Node<K,V>[] tab, ConcurrentHashMap.Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    // 获取CPU每个核的处理量,默认16
    // private static final int MIN_TRANSFER_STRIDE = 16;
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    // 判断扩容后的 table 是否为null
    // 如果为null则在此处进行创建新 table
    if (nextTab == null) {            // initiating
        try {
            @SuppressWarnings("unchecked")
            ConcurrentHashMap.Node<K,V>[] nt = (ConcurrentHashMap.Node<K,V>[])new ConcurrentHashMap.Node<?,?>[n << 1];
            nextTab = nt;
        } catch (Throwable ex) {      // try to cope with OOME
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        // 记录新的table
        nextTable = nextTab;
        // 记录旧的table长度
        transferIndex = n;
    }
    // 记录新 table的长度
    int nextn = nextTab.length;
    // 创建一个 ForwardingNode 并且说明当前的table正在进行扩容操作
    ConcurrentHashMap.ForwardingNode<K,V> fwd = new ConcurrentHashMap.ForwardingNode<K,V>(nextTab);
    // 记录当前 f 当前数组下标位置的某个元素数据是否需要计算新table下的新下标
    boolean advance = true;
    // 记录是否完成数据扫描
    boolean finishing = false; // to ensure sweep before committing nextTab
    for (int i = 0, bound = 0;;) {
        ConcurrentHashMap.Node<K,V> f; int fh;
        // 遍历旧table中的节点,计算新table中的下标
        while (advance) {
            int nextIndex, nextBound;
            if (--i >= bound || finishing)
                advance = false;
            else if ((nextIndex = transferIndex) <= 0) {
                i = -1;
                advance = false;
            }
            else if (U.compareAndSwapInt
                    (this, TRANSFERINDEX, nextIndex,
                            nextBound = (nextIndex > stride ?
                                    nextIndex - stride : 0))) {
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;
            }
        }
        // 当该旧table全部节点转移到新的table上时,结束扩容
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            if (finishing) {
                // talbe 指向新table
                nextTable = null;
                table = nextTab;
                //扩容阈值设置为原来容量的1.5                sizeCtl = (n << 1) - (n >>> 1);
                return;
            }
            // 使用CAS操作更新这个扩容阈值
            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
            }
        }
        // 判断存放节点的数组下标位置是否为null
        // 如果为null则尝试存放
        else if ((f = tabAt(tab, i)) == null)
            advance = casTabAt(tab, i, null, fwd);
        // 如果不为null则判断改位置是否已经转移完成
        // 如果是则不再转移当前下标位置的元素
        else if ((fh = f.hash) == MOVED)
            advance = true; // already processed
        else {
            // 锁住数组的下标的第一个元素
            synchronized (f) {
                // 判断 f 的值有没有被修改
                // 如果 f 没又改变,则继续操作,否则重复第一个循环
                if (tabAt(tab, i) == f) {
                    ConcurrentHashMap.Node<K,V> ln, hn;
                    // 判断是否链表结构
                    // 如果是,则根据链表结构的存储规则存储元素
                    if (fh >= 0) {
                        int runBit = fh & n;
                        ConcurrentHashMap.Node<K,V> lastRun = f;
                        for (ConcurrentHashMap.Node<K,V> p = f.next; p != null; p = p.next) {
                            // 把节点存放新table的原位或者移动 n 位存放
                            // 其实就是计算该节点是存放在当前下标位置还是 i+n的下标位置
                            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 (ConcurrentHashMap.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 ConcurrentHashMap.Node<K,V>(ph, pk, pv, ln);
                            else
                                hn = new ConcurrentHashMap.Node<K,V>(ph, pk, pv, hn);
                        }
                        // 通过上面的计算把ln链表放在原本的下标位置
                        // hn链表放在 原本下标+n的位置
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        // 在旧table存放 ForwardingNode 代表该数组下标位置的数据已经完成转移
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                    // 判断是否红黑树结构
                    // 如果是,则根据红黑树结构的存储规则存储元素
                    else if (f instanceof ConcurrentHashMap.TreeBin) {
                        ConcurrentHashMap.TreeBin<K,V> t = (ConcurrentHashMap.TreeBin<K,V>)f;
                        ConcurrentHashMap.TreeNode<K,V> lo = null, loTail = null;
                        ConcurrentHashMap.TreeNode<K,V> hi = null, hiTail = null;
                        int lc = 0, hc = 0;
                        for (ConcurrentHashMap.Node<K,V> e = t.first; e != null; e = e.next) {
                            int h = e.hash;
                            ConcurrentHashMap.TreeNode<K,V> p = new ConcurrentHashMap.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则转换成链表
                        // static final int UNTREEIFY_THRESHOLD = 6;
                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                                (hc != 0) ? new ConcurrentHashMap.TreeBin<K,V>(lo) : t;
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                (lc != 0) ? new ConcurrentHashMap.TreeBin<K,V>(hi) : t;
                        // 把计算后存放在原来位置的 ln继续存放在原来的位置
                        // hn存放在 i+n 的位置
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        // 在旧table存放 ForwardingNode 代表该数组下标位置的数据已经完成转移
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                }
            }
        }
    }
}
final ConcurrentHashMap.Node<K,V>[] helpTransfer(ConcurrentHashMap.Node<K,V>[] tab, ConcurrentHashMap.Node<K,V> f) {
    ConcurrentHashMap.Node<K,V>[] nextTab; int sc;
    // 判断当前 table是否在进行扩容操作
    if (tab != null && (f instanceof ConcurrentHashMap.ForwardingNode) &&
            (nextTab = ((ConcurrentHashMap.ForwardingNode<K,V>)f).nextTable) != null) {
        // 获取扩容后的table大小
        int rs = resizeStamp(tab.length);
        // 再次判断扩容操作是否还在进行,并且是同一次扩容操作
        while (nextTab == nextTable && table == tab &&
                (sc = sizeCtl) < 0) {
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
                break;
            // 通过CAS扩容操作尝试获取扩容操作资格
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}

每次扩容是容量原来的2倍,并且旧table原元素只会存放在新table的 i 或者 i+n 的位置而不是重新计算hash新的 i ,并且put()操作的时候有可能会帮忙一起扩容,分担了单线程操作的压力,当旧的 i 位置的节点全部转移完成使用 ForwardingNode 标记当前位置所以节点已经转移完成,下面是一个简单的扩容后可能存放的位置图

会引起扩容操作的2个函数addCount()与treeifyBin()

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)) {
        CounterCell a; long v; int m;
        boolean uncontended = true;
        // 多线程修改baseCount时,没修改成功的线程会执行fullAddCount(),x的值添加到counterCell类中
        if (as == null || (m = as.length - 1) < 0 ||
                (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                !(uncontended =
                        U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
            fullAddCount(x, uncontended);
            return;
        }
        if (check <= 1)
            return;
        s = sumCount();
    }
    // check >= 0 的时候证明需要扩容
    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                    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();
        }
    }
}
private final void treeifyBin(Node<K,V>[] tab, int index) {
    Node<K,V> b; int n, sc;
    if (tab != null) {
        //如果table的长度<64 就扩大一倍
        // 就是说当前 table的长度>64 且链表节点数量 >= 8时候才会转换成红黑树 
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            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;
                    }
                    //在原来下标的位置 用TreeBin替换掉原来的Node对象
                    setTabAt(tab, index, new TreeBin<K,V>(hd));
                }
            }
        }
    }
}

addCount()的主要作用是增加当前ConcurrentHashMap的元素数量并且判断是否需要扩容,当容量已经达到了扩容阈值则进行扩容操作

treeifyBin()则是用于进行树结构转换和判断是否需要扩容,当容量 < 64 时则进行扩容而非转换成树结构,只有容量>64且链表长度>=8时才会进行树结构转换

与HashMap不同的是多了2个内部类:ForwardingNode 与  TreeBin

ForwardingNode:只有扩容操作的时候才会使用到,标记数组的 i 位置是否已经完成

TreeBin:HashMap是直接使用TreeNode,而ConcurrentHashMap则是通过TreeBin来管理TreeNode来使用

 

ConcurrentHashMap通过CAS和巧妙地运用synchronized 提供了一个安全和高效而且非常精彩解决方案

ConcurrentHashMap的一些简单学习记录到此结束,世界真的很大

ConcurrentHashMap 与同步 HashMap - ConcurrentHashMap vs Synchronized HashMap

ConcurrentHashMap 与同步 HashMap - ConcurrentHashMap vs Synchronized HashMap

问题:

What is the difference between using the wrapper class, SynchronizedMap , on a HashMap and ConcurrentHashMap ?HashMapConcurrentHashMap 上使用包装类 SynchronizedMap 什么区别?

Is it just being able to modify the HashMap while iterating it ( ConcurrentHashMap )? 它是否只能在迭代时修改 HashMap ( ConcurrentHashMap )?


解决方案:

参考: https://stackoom.com/en/question/5Q44

ConcurrentHashMap源码分析-Java8

ConcurrentHashMap源码分析-Java8

<h4 id="1concurrenthashmap特性">1.ConcurrentHashMap特性

说明:因为ConcurrentHashMap单词太长,所以下面均适用CHM替代ConcurrentHashMap

  • 同为线程安全集合,但CHM没有任何访问操作需要锁定全表。这也注定了CHM上的操作效率之高。
  • 表访问需要volatile/atomic读,写和CAS.这通过使用内在函数(sun.misc.Unsafe)完成。
  • 向一个空bin中插入节点是通过CAS完成的,其它的更新操作(insert,delete,update)都需要锁lock。
  • 从JDK8开始,CHM使用CAS算法替代了Segment的概念,保证线程安全。
  • 构成结构:bin数组+链表+红黑树 红黑树被包装在TreeBin内
  • 扩容机制:2倍扩容
  • 常量:
    • 默认容量:16;
    • 负载因子:0.75 说明:在构造函数中重写此值只会影响初始表的容量,而不会使用实际的浮点值。
    • 链表转红黑树阈值:8
    • 红黑树转链表阈值:6
    • table转为红黑树阈值:64
    • resize时的最小并行度:16(因为默认16个bin)
  • CHM的key,value都不能为null
  • 访问操作(get等)和更新操作(remove等)同时发生时,根据happens-before原则,更新操作先执行,读操作后执行,从而保证了检索操作获取的值一定是最新值。
  • 聚合状态方法的结果包括:size,isEmpty,containsValue通常都是仅当map不在其它线程中进行并发更新时才有用。
  • 批量操作可以接受一个并行阈值参数parallelismThreshold。
    • 如果当前map的size预估值比给定的阈值小,则方法顺序执行。
    • 如果给定阈值=Long.MAX_VALUE,则不会出现并行操作。
    • 如果给定阈值=1,则会导致并行最大化,通过使用ForkJoinPool.commonPool()方法,对子任务分离。
  • 并行操作通常比顺序操作快,但不能保证一定是这样。并行操作更慢的情况有:
    • 如果并行计算的基础工作比计算本身更昂贵,那么小map上的并行操作可能比顺序形式执行更慢。
    • 如果所有处理器都忙于执行不相关的任务,并行化可能无法实现太多的实际并行性。(无法形成流水线操作)
  • 支持序列化,不支持浅拷贝
  • 两个线程访问同一个bin中不同的元素的锁争用概率为:1 / (8 * #elements)
  • TreeBins存在的意义:保护了我们免于因过度resize带来的最坏影响。
  • 每一个bin中的元素到达新的bin后要么索引不变,要么产生2的次幂的位移。我们通过捕获旧节点可以重用的情况来消除不必要的节点创建。平均而言,当table进行resize时,只有1/6的节点需要进行clone。
  • table进行resize时,其它线程可以加入协助resize的过程(这不是为了获取锁),从而使得平均聚合等待时间变短。
  • 在遇到转发节点时,遍历会移动到新table而无需重新访问节点
  • 能够用TreeMap替代TreeBin?
    • 不能。
    • 原因:TreeBins的查询及与查询相关的操作都使用了一种特殊的比较形式。TreeBins中包含的元素可能在实现Comparable上的原则不一样,所以对于它们之间的比较,则无法调用Compareto()方法。为了解决这一问题,tree通过hash值对其排序。如果Comparable.compareto 可用的话,再用这个方法对元素排序。在查找节点时,如果元素不具有可比性或比较为0,则可能需要对此节点对左右孩子都进行查询。如果所有元素都不是可比较的并且具有相同的哈希值,则需要对全table进行扫描。
  • TreeBins也需要额外的锁定机制。list更新过程中依旧可以进行遍历,但是红黑树在更新时却不能进行遍历,因为红黑树的调整可能会改变树的根节点,也可能改变各个节点之间的连接情况。
  • TreeBins包含一个简单的读写锁定机制,依赖于主要的同步策略:
    • 插入,删除的结构调整会调用lock机制;
    • 如果在结构调整前有读操作,则必须读操作完成后,再进行结构的调整操作。遵循happes-before原则。
  • 扩展AbstractMap,但这只是仅仅为了与这个类的以前版本兼容。

方法、域的分析

  • hash值求法
    • spread(int h)
      • 哈希值=(h ^ (h >>> 16)) & HASH_BITS;//消除异或结果的最高位影响
      • h:key的hashcode
    • 方法分析:hash值无符号右移16位原因:因为table使用的是2的整数次幂的掩码,仅在当前掩码之上的位上变化的散列集将会总是碰撞。(比如,Float键的集合在小table中保持连续的整数)所以我们应用一个转换,将高位的影响向下扩展。这是在速度,性能,分布上做的一个平衡。 因为许多常见的哈希集合已经合理分布(它们就不会在spread机制中受益)因为我们已经使用了红黑树对bin中的大量碰撞做了处理,因此我们只是以最简单的方式做一些移位,然后进行异或运算,以减少系统损失,并合并由于表边界而不会用于索引计算的最高位的影响(也就是&运算)。
  • 扩容方法:
    • tableSizefor(int c)
      • c: c=1.5*capaticy+1;
      • 返回值:>=c的第一个2的整数次幂
    • 方法分析: 如果c为2的整数次幂,则返回c; 如果c不是2的整数次幂,则返回第一个比c大的2的整数次幂; eg:c=16,则返回结果为16;c=30,则返回结果为32;
  • 三个访问table的方法
    • 方法说明:
      • 都是属于volatile类型的方法,所以即使在resize的过程中,访问对table中的元素获取的结果也是正确的
      • 对setTabAt()方法的调用总是发生在lock区域内,所以原则上不需要完整的volatile语义,但是目前的代码还是保守地选择了volatile方式。
    • 方法
      • static final Node tabAt(Node[] tab, int i)
      • static final boolean casTabAt(Node[] tab, int i, Node c, Node v)
      • static final void setTabAt(Node[] tab, int i, Node v)
  • bin数组:transient volatile Node[] table;
  • sizeCtl:用于控制table初始化和resize的一个变量。
    • 值为负数:table正在初始化or正在resize
    • sizeCtl=-1:正在初始化;
    • sizeCtl=-(1+n):当前有n个线程正在进行resize;
    • 当table未初始化时,保存创建时使用的初始表大小,或默认为0。初始化后,保存下一个要调整table大小的元素计数值。
  • 4个构造函数
    • ConcurrentHashMap()
    • ConcurrentHashMap(int initialCapacity)
    • ConcurrentHashMap(Map

package sourcecode.analysis;
/**
 * @Author: cxh
 * @CreateTime: 18/4/3 16:29
 * @ProjectName: JavaBaseTest
 */

import java.io.ObjectStreamField;
import java.io.Serializable;
import <a href="https://www.jb51.cc/tag/javalang/" target="_blank">java.lang</a>.*;
import <a href="https://www.jb51.cc/tag/javalang/" target="_blank">java.lang</a>.reflect.P<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>meterizedType;
import <a href="https://www.jb51.cc/tag/javalang/" target="_blank">java.lang</a>.reflect.Type;
import java.util.AbstractMap;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>tor;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.I<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.CountedCompleter;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.<a href="https://www.jb51.cc/tag/atomicreference/" target="_blank">atomicreference</a>;
import java.util.concurrent.locks.LockSupport;
import java.util.concurrent.locks.<a href="https://www.jb51.cc/tag/reentrantlock/" target="_blank">reentrantlock</a>;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.BinaryOperator;
import java.util.function.Consumer;
import java.util.function.DoubleBinaryOperator;
import java.util.function.Function;
import java.util.function.IntBinaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.T<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleBiFunction;
import java.util.function.T<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleFunction;
import java.util.function.ToIntBiFunction;
import java.util.function.ToIntFunction;
import java.util.function.ToLongBiFunction;
import java.util.function.ToLongFunction;
import java.util.stream.Stream;

/**
 * Hashtable<a href="https://www.jb51.cc/tag/zhichi/" target="_blank">支持</a>高并发检索,同时<a href="https://www.jb51.cc/tag/zhichi/" target="_blank">支持</a>高并发更新.
 * ConcurrentHashMap和Hashtable遵守相同的<a href="https://www.jb51.cc/tag/gongneng/" target="_blank">功能</a>规范,并且包含与Hashtable每种<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>相对应的<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>版本.
 * 但是,尽管所有操作都是线程安全的,但检索操作并不需要锁定,并且没有任何访问操作需要锁定全表.
 * 这个类可以在依赖线程安全性的程序中与Hashtable完全互操作,但不依赖于它的同步细节.
 *
 * 检索操作(<a href="https://www.jb51.cc/tag/baokuo/" target="_blank">包括</a>get)通常不会对表加锁,因此可能会和更新操作(如put,remove)同时发生.
 * 检索反映了最近完成的更新操作的结果.更正式的说:对<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>key的value的更新操作和读操作遵守happens-before
 * 原则,所以同时发生检索和更新操作时,更新操作先执行,读操作<a href="https://www.jb51.cc/tag/houzhixing/" target="_blank">后执行</a>,从而保证了检索操作<a href="https://www.jb51.cc/tag/huoqu/" target="_blank">获取</a>的值一定是最新线程
 * 更新的值.
 * 对整体操作(如putAll和clear),并发检索可能只会反映出一部分条目的插入和<a href="https://www.jb51.cc/tag/shanchu/" target="_blank">删除</a>.同样的,I<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tors,Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tors
 * 和Enumerations只是在一定程度上反映了哈希表的状态or反映的是从i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor/enumeration它们创建后哈希表的状态.
 * 它们并不会抛出并发异常ConcurrentModificationException.但是,迭代器被设计为一次只能由<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>线程使用.
 * 请记住,聚合状态<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>的结果<a href="https://www.jb51.cc/tag/baokuo/" target="_blank">包括</a>:size,isEmpty,containsValue通常都是仅当map不在其它线程中进行并发更新时才有用.
 * 否则,这些<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>的结果反映了可能足以用于监视或估计目的的暂态,但不适用于程序控制。
 *
 * 当碰撞冲突很多时(如不同hash值的key通过取模运算后进入了相同的slot),table会<a href="https://www.jb51.cc/tag/zidong/" target="_blank">自动</a>扩容,* slot扩容后大小为原来的2倍(和扩容时0.75<a href="https://www.jb51.cc/tag/fuzai/" target="_blank">负载</a>因子阈值保持一致)
 * 随着映射的<a href="https://www.jb51.cc/tag/tianjia/" target="_blank">添加</a>和<a href="https://www.jb51.cc/tag/shanchu/" target="_blank">删除</a>,这个平均值可能会有很大的变化,但是总的来说,针对散列表,这已经是在时间/空间上做了折衷.
 * 但是,调整这个或任何其他类型的哈希表可能是<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>相对较慢的操作.在可能的情况下,通过构造器<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>,指定initialCapacity
 * 是比较好的方式.另外<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>可选的构造<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>参数loadFactor提供了另一种定制初始表容量的<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>,通过指定要用于计算给定元素数
 * 分配空间量的表密度来<a href="https://www.jb51.cc/tag/zidingyi/" target="_blank">自定义</a>初始表容量.此外,为了与此类的以前版本兼容,构造<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>可以选择指定预期的concurrencyLevel
 * 作为内部大小调整的附加<a href="https://www.jb51.cc/tag/tishi/" target="_blank">提示</a>.
 * 注意:如果很多key都用一样的hashcode,则哈希表的<a href="https://www.jb51.cc/tag/xingneng/" target="_blank">性能</a>一定会降低.为了减弱这种影响,当key是可比较的对象时(实现了
 * Comp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>ble接口),则ConcurrentHashMap可以通过对key的排序来打破这种关系.
 *
 * ConcurrentHashMap的Set<a href="https://www.jb51.cc/tag/duixiangchuangjian/" target="_blank">对象创建</a>方式有:newKeySet(),newKeySet(int),* 如果所有的key都是有效的,且values都无效(or所有的value值都一样),则还有一种视图创建方式:keySet(Object).
 *
 * ConcurrentHashMap可以用作可伸缩频率map(直方图或多重集的一种形式),这可以使用LongAdder作为value,* 通过co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>teIfAbsent来初始化.比如:
 * 向ConcurrentHashMap<String,LongAdder>类型的变量freqs<a href="https://www.jb51.cc/tag/tianjia/" target="_blank">添加</a><a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>count,你可以使用lambda表达式如下:
 * freqs.co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>teIfAbsent(k -> new LongAdder()).increment();
 *
 * 此类及其视图和迭代器实现了Map和I<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor接口的所有可选<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>。
 *
 * ConcurrentHashMap的key和value都不能为null,这一点和hashtable一致.
 *
 * ConcurrentHashMap<a href="https://www.jb51.cc/tag/zhichi/" target="_blank">支持</a>一组顺序操作和并行的批量操作,和大多数Stream<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>不同,该操作被设计为线程安全
 * 且经常应用于即使由其他线程同时更新的映射;例如,在计算共享<a href="https://www.jb51.cc/tag/zhuce/" target="_blank">注册</a>表中值的快照<a href="https://www.jb51.cc/tag/zhaiyao/" target="_blank">摘要</a>时。
 * 有3种操作,每一种有4种形式,接受<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>包含keys,values,Entries,(key,value)参数的<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>.
 * 因为ConcurrentHashMap的元素没有以任何特定的方式排序,并且可能在不同的并行执行中以不同的顺序处理,
 * 所以提供的<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>的正确性不应取决于任何排序,及在过程中可能会瞬时改变的对象or值;除了forEach<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>,其它<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>在理想情况下,* 应该是不会改变ConcurrentHashMap的.
 * Map.Entry上的块操作<a href="https://www.jb51.cc/tag/buzhichi/" target="_blank">不支持</a><a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>setValue().
 *
 * forEach:对每个元素执行给定操作.
 *
 * search:返回在每个元素上应用给定<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>的第<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>可用的非null元素;找到后不再进行后续的<a href="https://www.jb51.cc/tag/sousuo/" target="_blank">搜索</a>.
 *
 * reduce:计算每<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>元素.
 * 设计的reduce<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>不能依赖元素顺序
 *
 * 批量操作可以接受<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>并行阈值参数p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold.
 * 如果当前map的size预估值比给定的阈值小,则<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>顺序执行.
 * 所以,如果给定阈值=Long.MAX_VALUE,则不会出现并行操作.
 *      如果给定阈值=1,则会导致并行最大化,通过使用ForkJoinPool.commonPool()<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>,对子任务分离.
 * 通常情况下,您最初会选择这些极端值中的<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>,然后衡量使用中间开销与吞吐量之<a href="https://www.jb51.cc/tag/jiande/" target="_blank">间的</a>值的<a href="https://www.jb51.cc/tag/xingneng/" target="_blank">性能</a>。
 *
 * 批量操作的并发<a href="https://www.jb51.cc/tag/shuxing/" target="_blank">属性</a>来自ConcurrentHashMap的并发<a href="https://www.jb51.cc/tag/shuxing/" target="_blank">属性</a>:
 * 插入,更新操作happens-before访问操作.
 * 任何批量操作的结果反映了这些每元素关系的组成(但是,除非以某种方式知道它是静止的,否则就整个map而言,不一定是原子的)
 * 相反,因为映射中的键和值永远不会为null,所以null作为当前缺少任何结果的可靠原子指标。
 * 为了保持这个<a href="https://www.jb51.cc/tag/shuxing/" target="_blank">属性</a>,null作为所有非标量约简操作的隐含基础。
 * 对于double,long和int版本,base应该与其他任何值结合时返回其他值(更正式地说,它应该是减少的标识元素)。
 * 最常见的reduce<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>接口有这些<a href="https://www.jb51.cc/tag/shuxing/" target="_blank">属性</a>;例如,用MAX_VALUE或0或作为计算和的初始值。
 *
 * 作为参数提供的<a href="https://www.jb51.cc/tag/sousuo/" target="_blank">搜索</a>和转换<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>应该类似地返回null来指示无结果(<a href="https://www.jb51.cc/tag/zaizhe/" target="_blank">在这</a>种情况下,它不被使用)
 * 在映射的reduce<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>接口中,这也使得变换能够用作过滤器,如果元素不能合并,则返回null.
 * 在search或者reduce操作中使用它们前,您可以通过在“null意味着现在没有”规则下自己组合它们来创建复合转换和过滤。
 *
 * 接受和/或返回Entry参数的<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>维护键值关联.注意可以使用AbstractMap.SimpleEntry(k,v)作为空白entry参数.
 *
 * 批量操作可能会突然完成,从而引发<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank">调用</a><a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>抛出异常.
 * 请记住:在处理这样的异常时,其他并发执行的<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>也可能引发异常,或者即使第<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>异常没有发生,其它异常也可能发生。
 *
 * 并行操作通常比顺序操作快,但不能保证一定是这样.
 * 并行操作更慢的情况有:
 * 1.如果并行计算的基础工作比计算本身更昂贵,那么小map上的并行操作可能比顺序形式执行更慢。
 * 2.如果所有处理器都忙于执行不相关的任务,并行化可能无法实现太多的实际并行性。(无法形成流水线操作)
 *
 * <a href="https://www.jb51.cc/tag/zhichi/" target="_blank">支持</a>序列化,<a href="https://www.jb51.cc/tag/buzhichi/" target="_blank">不支持</a>浅拷贝
 *
 * @since 1.5
 * @author Doug Lea
 * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m <K> the type of keys maintained by this map
 * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m <V> the type of mapped values
 */
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
        implements ConcurrentMap<K,V>,Serializable {
    private static final long serialVersionUID = 7249069246763182397L;

    /*
     * 概述:
     *
     * 这个散列表的主要设计目标是保持并发可读性(通常<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>get(),但也<a href="https://www.jb51.cc/tag/baokuo/" target="_blank">包括</a>迭代器和相关<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>),
     * 同时最小化更新争用。次要目标是保持空间消耗与java.util.HashMap大致相同或更好,并支
     * 持多线程在空表上较高的初始插入速率。
     *
     * 该映射通常用作分箱(分段)散列表。每个键值映射都保存在<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>节点中。大多数节点是具有散列,
     * 键,值和下<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>字段的基本节点类的实例。但是,存在各种子类:TreeNodes排列在平衡树中,而不是列表。
     * TreeBins拥有TreeNodes集合的根。转发节点在调整大小期间放置在bin的头部。 ReservationNodes用作占位符,
     * 同时在co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>teIfAbsent和其它相关的<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>中中建立值.
     * 类型TreeBin,ForwardingNode和ReservationNode不包含普通的key,value或hash值,并且在<a href="https://www.jb51.cc/tag/sousuo/" target="_blank">搜索</a>期间很容易
     * 区分,因为它们具有负散列字段和空键和值字段。 (这些特殊节点要么不常见,要么是暂时的,所以携带一些未使用的
     * 字段的影响是微不足道的。)
     *
     *
     * 在第一次插入时,table大小被惰性初始化为2的整数次幂。表中的每个bin通常包含<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>节点列表(通常,列表只有零个或
     * <a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>节点)。表访问需要volatile/atomic读,写和CAS<a href="https://www.jb51.cc/tag/huoqu/" target="_blank">获取</a>锁。因为在不<a href="https://www.jb51.cc/tag/zengjia/" target="_blank">增加</a>指针的情况这些操作无法实现,
     * 所以我们使用内在<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>(sun.misc.Unsafe)操作。
     *
     * 我们使用节点散列字段的顶部(符号)位来进行控制 -- 由于地址限制,它无论如何都是可用的。具有负散列字段的节点是
     * 被特别处理的,或者map<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>中直接被忽略.
     *
     * 向<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>空bin中插入节点是通过CAS完成的.在大多数key/hash分布中,这是一种很常见的put操作.其它的更新操作
     * (insert,delete,update)都需要锁lock.因为如果每<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>bin都分配<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>单独的lock会比较浪费存储空间,所以改为使用bin列表的
     * 第<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>节点本身作为锁。对这些锁的锁定<a href="https://www.jb51.cc/tag/zhichi/" target="_blank">支持</a>依赖于内置的“同步”监视器。
     *
     * 但是,使用列表的第<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>节点作为锁本身并不足以满足:当<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>节点被锁定时,任何更新都必须首先验证它在锁定之后仍然是第<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>节点,
     * 如果不是,则重试.因为新节点总是追加到列表尾部,所以一旦节点首先进入<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>容器,它将保持第<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>直到被<a href="https://www.jb51.cc/tag/shanchu/" target="_blank">删除</a>或容器变为无效(在调整大小时)。
     *
     * 每个分区都有锁的主要缺点是:由同<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>锁保护的分区列表中的其他节点上的其他更新操作可能会被延迟,比如equals()和映射等相关的<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>执行时,* 会花费很长时间.然而,<a href="https://www.jb51.cc/tag/tongji/" target="_blank">统计</a>上,在<a href="https://www.jb51.cc/tag/suiji/" target="_blank">随机</a>哈希码下,这不是<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>常见问题。理想情况下,给定size的调整阈值为0.75,bin中节点的频率遵循平均
     * 约为0.5的泊松分布,尽管调整size大小时泊松分布方差很大.忽略方差,列表大小k的预期出现是(exp(-0.5)* pow(0.5,k)/ factorial(k))。
     * 第<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>值是:
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * 其它值:只要是在10,000,000范围内,都会小于1.
     *
     * 两个线程访问同<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>bin中不同的元素的锁争用概率为:1 / (8 * #elements)
     *
     * 实际中遇到的哈希码分布有时会明显偏离均匀<a href="https://www.jb51.cc/tag/suiji/" target="_blank">随机</a>性。这<a href="https://www.jb51.cc/tag/baokuo/" target="_blank">包括</a>N>(1 << 30)的情况,所以一些key必然会出现碰撞。
     * 因此,我们使用<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>二级策略,该策略适用于bin中节点数超过阈值的情况。这些TreeBins使用平衡树来保存节点(一种特殊形式的红黑树),
     * 将<a href="https://www.jb51.cc/tag/sousuo/" target="_blank">搜索</a>时间限制在O(log N).TreeBin中的每个<a href="https://www.jb51.cc/tag/sousuo/" target="_blank">搜索</a>步骤至少比常规列表中的<a href="https://www.jb51.cc/tag/sousuo/" target="_blank">搜索</a>步骤慢两倍,但考虑到N不能超过(1 << 64)(在内存地址
     * 用完之前),所以<a href="https://www.jb51.cc/tag/sousuo/" target="_blank">搜索</a>步骤,锁的持有时间等等,都会受到限制,从而<a href="https://www.jb51.cc/tag/sousuo/" target="_blank">搜索</a>节点个数会控制在100个以内.TreeBin节点(TreeNodes)也保持与
     * 常规节点相同的“下<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>”遍历指针,所以可以以相同的方式在迭代器中遍历。
     *
     * 当table中元素个数超过百分比阈值(名义上为0.75,但请参见下文)时,会调整table的大小。
     * 启动线程负责分配并设置替换数组,后续使用这个concurrentHashMap的其它线程在发现元素个数超过<a href="https://www.jb51.cc/tag/fuzai/" target="_blank">负载</a>因子规定大小时,都可以对table进行
     * resize操作.TreeBins的使用保护了我们免于因过度resize带来的最坏影响.
     * resize的过程是将旧table中的每<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>bin都复制到新table的遍历复制过程.然而,线程要求在传输之前通过字段transferIndex传输小块索引,
     * 从而减少争用。字段sizeCtl中的<a href="https://www.jb51.cc/tag/shengcheng/" target="_blank">生成</a>戳记确保重新定位不重叠。因为resize时,按照2的整数次幂进行扩容,所以每<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>bin中的元素到达新的bin
     * 后要么索引不变,要么产生2的次幂的位移.我们通过捕获旧节点可以重用的情况来消除不必要的节点创建,因为它们的下<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>域不会改变.
     * 平均而言,当tableresize时,只有1/6的节点需要进行clone.
     * 被替换掉的节点只要不再被读线程引用,则会被GC回收.
     * 元素都被转移到新table后,旧table的bin中只包含<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>转发节点(其hash域为MOVED),这一节点将新table作为它的key.在遇到转发节点时,查找
     * 和更新操作会转到新table中重新执行.
     *
     * 每<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>bin从旧table到新table的转移都需要<a href="https://www.jb51.cc/tag/huoqu/" target="_blank">获取</a>其bin的锁,这一过程中,可以阻止想要<a href="https://www.jb51.cc/tag/huoqu/" target="_blank">获取</a>这个bin的lock的线程进行等待.
     * 但是其它线程可以加入协助resize的过程(这不是为了<a href="https://www.jb51.cc/tag/huoqu/" target="_blank">获取</a>锁),从而使得平均聚合等待时间变短.
     * 转移还需要保证:无论是新table,还是旧table,只要是可访问的bin,都要保证其能进行遍历.
     * 这部分是通过从最后<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>bin(table.length - 1)开始向第<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>方向进行的。
     * 在遇到转发节点时,遍历会移动到新table而无需重新访问节点。为了保证无序移动时也不跳过中间节点,在遍历期间首次遇到转发节点时会创建<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>
     * 堆栈,以便在稍后处理当前table时保持其位置.对这些保存/恢复机制的需求相对较少,但是当遇到<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>转发节点时,通常会有更多的节点.
     * 所以Traversers使用简单的缓存方案来避免创建这么多新的TableStack节点。
     * 遍历方案也适用于部分遍历bin(通过<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>可选的Traverser构造<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>)来<a href="https://www.jb51.cc/tag/zhichi/" target="_blank">支持</a>分区聚合操作。
     *
     * 用到了表的延迟初始化
     *
     * 元素个数的count值由LongAdder来维护.通过对其特殊设置,避免使用LongAdder来访问导致创建多个CounterCell的隐式竞争检测.
     * 计数器机制避免更新上的争用,但如果在并发访问期间读取频率太高,可能会遇到缓存抖动。为避免频繁读,仅在<a href="https://www.jb51.cc/tag/tianjia/" target="_blank">添加</a>到已拥有两个或更多节点的
     * bin时尝试调整竞争大小。在统一的散列分布下,发生在阈值处的概率约为13%,这意味着只有大约1/8需要检查阈值(并且在调整大小之后,很少这
     * 样做)。
     *
     * TreeBins的<a href="https://www.jb51.cc/tag/chaxun/" target="_blank">查询</a>及与<a href="https://www.jb51.cc/tag/chaxun/" target="_blank">查询</a>相关的操作都使用了一种特殊的比较形式(这也是为什么不能使用现有集合TreeMap的原因).TreeBins中包含的元素可能
     * 在实现Comp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>ble上的原则不一样,所以对于它们之<a href="https://www.jb51.cc/tag/jiande/" target="_blank">间的</a>比较,则无法<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank">调用</a>Compar<a href="https://www.jb51.cc/tag/eto/" target="_blank">eto</a>()<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>.为了<a href="https://www.jb51.cc/tag/jiejue/" target="_blank">解决</a>这一问题,tree通过hash值对其排序.如果
     * Comp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>ble.compar<a href="https://www.jb51.cc/tag/eto/" target="_blank">eto</a> 可用的话,再用这个<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>对元素排序.在查找节点时,如果元素不具有可比性或比较为0,则可能需要对此节点对左右孩子
     * 都进行<a href="https://www.jb51.cc/tag/chaxun/" target="_blank">查询</a>.如果所有元素都不是可比较的并且具有相同的哈希值,则需要对全table进行扫描.
     * 插入节点调整平衡时,为了保证总体有序,我们将类和identityHashCodes作为等同处理.
     * 红黑树调整平衡的算法是对CLR算法的改进.
     *
     * TreeBins也需要额外的锁定机制。list更新过程中依旧可以进行遍历,但是红黑树在更新时却不能进行遍历,因为红黑树的调整可能会改变树的根节点,* 也可能改变各个节点之<a href="https://www.jb51.cc/tag/jiande/" target="_blank">间的</a>连接情况.TreeBins包含<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>简单的读写锁定机制,依赖于主要的同步策略:插入,<a href="https://www.jb51.cc/tag/shanchu/" target="_blank">删除</a>的结构调整会<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank">调用</a>lock机制;如果
     * 在结构调整前有读操作,则必须读操作完成后,再进行结构的调整操作.由于只可能有<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>waiter,所以可以简单的使用<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>waiter域来阻止所有的写
     * 操作.然后,读操作永远不需要被阻塞.如果保持根锁定,它们沿next指针遍历,直到锁定变为可用或列表遍历完为止.这类情况下并遍历不快,
     * 但是可以最大限度地提高总预期吞吐量.
     *
     * 为了保持与以前的API和序列化兼容,这个类的版本引入了几个特别的<a href="https://www.jb51.cc/tag/neirong/" target="_blank">内容</a>:主要是:保留了构造器参数concurrencyLevel,但并未使用.
     * 我们接受<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>loadFactor构造<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>参数,但只将它应用于初始表容量(这个参数的使用仅此一次).我们还声明了<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>未使用的“Segment”类,
     * 它只在序列化时以最小的形式实例化。
     *
     * 另外,它扩展了AbstractMap,但这只是仅仅为了与这个类的以前版本兼容.
     *
     * ConcurrentHashMap<a href="https://www.jb51.cc/tag/daima/" target="_blank">代码</a>的组织顺序:
     * 1.主要的静态声明+工具类
     * 2.主要的public<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>
     * 3.扩容<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>,树,遍历器,批量操作.
     */

    /* ---------------- 常量 -------------- */

    /**
     * table的最大容量.
     * 为什么不是1<<32? 因为32位散列字段的前两位用于控制目的.
     * 1<<30=1073741824
     */
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    //<a href="https://www.jb51.cc/tag/mo/" target="_blank">默</a>认容量:16,和HashMap一样.
    private static final int DEFAULT_CAPACITY = 16;

    //数组最大长度,在toArray等相关<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>中用到
    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    //<a href="https://www.jb51.cc/tag/mo/" target="_blank">默</a>认并发级别,已经不再使用的字段,之所以还存在只是为了和之前的版本兼容.
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

    //此表的加载因子。在构造<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>中重写此值只会影响初始表的容量,而不会使用实际的浮点值.
    private static final float LOAD_FACTOR = 0.75f;

    //<a href="https://www.jb51.cc/tag/tianjia/" target="_blank">添加</a>当前元素,bin中元素个数=8,则链表转为树
    static final int TREEIFY_THRESHOLD = 8;

    //bin中元素个数到达6个,则树转链表
    static final int UNTREEIFY_THRESHOLD = 6;

    //table转为树的阈值:64,此值最小为4*TREEIFY_THRESHOLD,显然,这里设定了64为初始值.
    static final int MIN_TREEIFY_CAPACITY = 64;

    //table扩容时,bin转移个数,最小为<a href="https://www.jb51.cc/tag/mo/" target="_blank">默</a>认的DEFAULT_CAPACITY=16.
    //因为扩容时,可以多个线程同时操作,所以16个bin会被分配给多个的线程进行转移
    private static final int MIN_TRANSFER_STRIDE = 16;

    /**
     * The number of bits used for generation stamp in sizeCtl.
     * Must be at least 6 for 32bit arrays.
     * 用来控制扩容,单线程进入的变量
     * 32位数组时,最小值为6
     */
    private static int RESIZE_STAMP_BITS = 16;

    //resize时的线程最大个数
    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;

    /**
     * The bit shift for recording size stamp in sizeCtl.
     * 用来控制扩容,单线程进入的变量
     */
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

    //节点hash域的编码
    static final int MOVED     = -1; // forwarding nodes的hash值
    static final int TREEBIN   = -2; // roots of trees的hash值
    static final int RESERVED  = -3; // transient reservations的hash值
    static final int HASH_BITS = 0x7fffffff; // 正常散列节点的可用二进制位

    //当前可用<a href="https://www.jb51.cc/tag/cpu/" target="_blank">cpu</a><a href="https://www.jb51.cc/tag/shuliang/" target="_blank">数量</a>
    static final int N<a href="https://www.jb51.cc/tag/cpu/" target="_blank">cpu</a> = Runtime.getRuntime().availableProcessors();

    //用于序列化兼容性
    private static final ObjectStreamField[] serialPersistentFields = {
            new ObjectStreamField("segments",Segment[].class),new ObjectStreamField("segmentMask",Integer.TYPE),new ObjectStreamField("segmentShift",Integer.TYPE)
    };

    /* ---------------- 节点 -------------- */

    /**
     * static内部类:最核心的内部类,包装了key-value条目.
     * 特别注意:
     * 1.<a href="https://www.jb51.cc/tag/buzhichi/" target="_blank">不支持</a>setValue<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>.
     * 2.包含负数哈希值的node子类是特殊的,允许key和value为null.
     * 3.ConcurrentHashMap不允许key和value为null
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;//比hashmap多了关键字volatile
        volatile Node<K,V> next;//比hashmap多了关键字volatile

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

        public final K getKey()       { return key; }
        public final V getValue()     { return val; }
        //entry的hash值=key和value的hash值求异或,和hashmap相同
        public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
        public final String toString(){ return key + "=" + val; }
        //本<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>不被<a href="https://www.jb51.cc/tag/zhichi/" target="_blank">支持</a>
        public final V setValue(V value) {
            throw new UnsupportedOperationException();
        }

        /**
         * 检查步骤:
         * 1.是Map.Entry类型
         * 2.key和value都等价
         */
        public final boolean equals(Object o) {
            Object k,v,u; Map.Entry<?,?> e;
            return ((o instanceof Map.Entry) &amp;&amp;
                    (k = (e = (Map.Entry<?,?>)o).getKey()) != null &amp;&amp;
                    (v = e.getValue()) != null &amp;&amp;
                    (k == key || k.equals(key)) &amp;&amp;
                    (v == (u = val) || v.equals(u)));
        }

        //虚拟化<a href="https://www.jb51.cc/tag/zhichi/" target="_blank">支持</a>map.get();在子类中被覆盖。
        Node<K,V> find(int h,Object k) {
            Node<K,V> e = this;
            if (k != null) {
                do {
                    K ek;
                    if (e.hash == h &amp;&amp;
                            ((ek = e.key) == k || (ek != null &amp;&amp; k.equals(ek))))
                        return e;
                } while ((e = e.next) != null);
            }
            return null;
        }
    }

    /* ---------------- 静态工具 -------------- */

    /**
     * hash值无符号右移16位原因:
     * 因为table使用的是2的整数次幂的掩码,仅在当前掩码之上的位上变化的散列集将会总是碰撞。(比如,Float键的集合在小table中保持连续的整数)
     * 所以我们应用<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>转换,将高位的影响向下扩展。这是在速度,<a href="https://www.jb51.cc/tag/xingneng/" target="_blank">性能</a>,分布上做的<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>平衡.
     * 因为许多常见的哈希集合已经合理分布(它们就不会在spread机制中受益)
     * 因为我们已经使用了红黑树对bin中的大量碰撞做了处理,因此我们只是以最简单的方式做一些移位,然后进行异或运算,
     * 以减少系统损失,并合并由于表边界而不会用于索引计算的最高位的影响(也就是&amp;运算)。
     *
     */
    static final int spread(int h) {
        return (h ^ (h >>> 16)) &amp; HASH_BITS;//消除异或结果的最高位影响
    }

    /**
     * 如果c为2的整数次幂,则返回c;
     * 如果c不是2的整数次幂,则返回第<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>比c大的2的整数次幂;
     * eg:c=16,则返回结果为16;
     *    c=30,则返回结果为32;
     */
    private static final int tableSi<a href="https://www.jb51.cc/tag/zef/" target="_blank">zef</a>or(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;
    }

    //如果传入参数x实现了Comp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>ble接口,则返回类x,否则返回null.同HashMap
    static Class<?> comp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>bleClassFor(Object x) {
        if (x instanceof <a href="https://www.jb51.cc/tag/javalang/" target="_blank">java.lang</a>.Comp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>ble) {
            Class<?> c; Type[] ts,as; Type t; P<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>meterizedType p;
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;
            if ((ts = c.getGenericInterfaces()) != null) {
                for (int i = 0; i < ts.length; ++i) {
                    if (((t = ts[i]) instanceof P<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>meterizedType) &amp;&amp;
                            ((p = (P<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>meterizedType)t).getRawType() ==
                                    <a href="https://www.jb51.cc/tag/javalang/" target="_blank">java.lang</a>.Comp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>ble.class) &amp;&amp;
                            (as = p.getActualTypeArguments()) != null &amp;&amp;
                            as.length == 1 &amp;&amp; as[0] == c) // type arg is c
                        return c;
                }
            }
        }
        return null;
    }

    //如果x和kc类型相同,则返回k.compar<a href="https://www.jb51.cc/tag/eto/" target="_blank">eto</a>(x)结果;否则返回0.同HashMap
    @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>ble
    static int compareComp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>bles(Class<?> kc,Object k,Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((<a href="https://www.jb51.cc/tag/javalang/" target="_blank">java.lang</a>.Comp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>ble)k).compar<a href="https://www.jb51.cc/tag/eto/" target="_blank">eto</a>(x));
    }

    /* ---------------- 访问table元素<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a> -------------- */

    /*
     * 下面3个<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>,都是属于volatile类型的<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>,所以即使在resize的过程中,访问对table中的元素<a href="https://www.jb51.cc/tag/huoqu/" target="_blank">获取</a>的结果也是正确的.
     * 针对tab参数,必须有非null判定.然后判定tab的长度是否>0,最后判定索引i是否合法.
     * 注意:为了纠正<a href="https://www.jb51.cc/tag/yonghu/" target="_blank">用户</a>发生的任意并发<a href="https://www.jb51.cc/tag/cuowu/" target="_blank">错误</a>,这些检查必须对局部变量进行操作,这些检查必须对本地变量进行操作,这些变量占了下面一些特别的内联分配。
     * 注意:对setTabAt()<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>的<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank">调用</a>总是发生在lock区域内,所以原则上不需要完整的volatile语义,但是目前的<a href="https://www.jb51.cc/tag/daima/" target="_blank">代码</a>还是保守地选择了volatile方式.
     */

    @SuppressWarnings("unchecked")
    static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab,int i) {
        return (Node<K,V>)U.g<a href="https://www.jb51.cc/tag/eto/" target="_blank">eto</a>bjectVolatile(tab,((long)i << ASHIFT) + ABASE);
    }

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

    static final <K,V> void setTabAt(Node<K,V> v) {
        U.putObjectVolatile(tab,v);
    }

    /* ---------------- 域 -------------- */

    /**
     * bin数组
     * 延迟初始化到第一次插入元素.
     * 数组长度总是2的整数次幂.
     * 可以通过迭代器进行访问.
     */
    transient volatile Node<K,V>[] table;

    //resize时用到的临时table,只有在resize时,才不为null
    private transient volatile Node<K,V>[] nextTable;

    //基本计数器值,主要用于没有争用时,也可作为表初始化期<a href="https://www.jb51.cc/tag/jiande/" target="_blank">间的</a>后备。通过CAS更新。
    private transient volatile long baseCount;

    /**
     * 用于控制table初始化和resize的<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>变量.
     * 值为负数:table正在初始化or正在resize
     * sizeCtl=-1:正在初始化;
     * sizeCtl=-(1+n):当前有n个线程<a href="https://www.jb51.cc/tag/zhengzaijinxing/" target="_blank">正在进行</a>resize;
     * 当table未初始化时,保存创建时使用的初始表大小,或<a href="https://www.jb51.cc/tag/mo/" target="_blank">默</a>认为0。初始化后,保存下<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>要调整table大小的元素计数值。
     */
    private transient volatile int sizeCtl;

    //resize时,next table的索引+1,用于分割.
    //nexttable索引[0,2*n-1],故transferIndex=n
    private transient volatile int transferIndex;

    //在调整大小和/或创建CounterCells时使用的自旋锁(通过CAS锁定)。
    private transient volatile int cellsBusy;

    //这是<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>计数器数组,用于保存每个bin中节点个数.
    private transient volatile CounterCell[] counterCells;

    //视图views
    private transient KeySetView<K,V> keySet;
    private transient ValuesView<K,V> values;
    private transient EntrySetView<K,V> entrySet;


    /* ---------------- Public操作 -------------- */

    /*-------------4个构造<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>-----------*/

    //table<a href="https://www.jb51.cc/tag/mo/" target="_blank">默</a>认大小16
    public ConcurrentHashMap() {
    }

    //初始化容量为:>=1.5*initialCapacity+1的最小2的整数次幂
    public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                MAXIMUM_CAPACITY :
                tableSi<a href="https://www.jb51.cc/tag/zef/" target="_blank">zef</a>or(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }

    //创建<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>和输入参数map映射一样的map
    public ConcurrentHashMap(Map<? extends K,? extends V> m) {
        this.sizeCtl = DEFAULT_CAPACITY;
        putAll(m);
    }

    public ConcurrentHashMap(int initialCapacity,float loadFactor) {
        this(initialCapacity,loadFactor,1);
    }

    public ConcurrentHashMap(int initialCapacity,float loadFactor,int concurrencyLevel) {
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new Ille<a href="https://www.jb51.cc/tag/gal/" target="_blank">gal</a>ArgumentException();
        if (initialCapacity < concurrencyLevel)   // Use at least as many bins
            initialCapacity = concurrencyLevel;   // as estimated threads
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        //如果initialCapacity=16,则cap=32;
        int cap = (size >= (long)MAXIMUM_CAPACITY) ?
                MAXIMUM_CAPACITY : tableSi<a href="https://www.jb51.cc/tag/zef/" target="_blank">zef</a>or((int)size);
        this.sizeCtl = cap;
}

    // Original (since JDK1.2) Map methods

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

    public boolean isEmpty() {
        return sumCount() <= 0L; // ig<a href="https://www.jb51.cc/tag/nor/" target="_blank">nor</a>e transient negative values
    }

    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());
        if ((tab = table) != null &amp;&amp; (n = tab.length) > 0 &amp;&amp;
                (e = tabAt(tab,(n - 1) &amp; h)) != null) {
            //如果tab[(n-1)&amp;h]处的节点就是要查找的节点
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null &amp;&amp; key.equals(ek)))
                    return e.val;
            }
            //如果是树节点
            else if (eh < 0)
                return (p = e.find(h,key)) != null ? p.val : null;
            //如果是链表节点
            while ((e = e.next) != null) {
                if (e.hash == h &amp;&amp;
                        ((ek = e.key) == key || (ek != null &amp;&amp; key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }

    //<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank">调用</a>上面的<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>
    public boolean containsKey(Object key) {
        return get(key) != null;
    }


    public boolean containsValue(Object value) {
        if (value == null)
            throw new NullPointerException();
        Node<K,V>[] t;
        if ((t = table) != null) {
            Traverser<K,V> it = new Traverser<K,V>(t,t.length,t.length);
            for (Node<K,V> p; (p = it.advance()) != null; ) {
                V v;
                if ((v = p.val) == value || (v != null &amp;&amp; value.equals(v)))
                    return true;
            }
        }
        return false;
    }

    //key,value不能为null
    public V put(K key,V value) {
        return putVal(key,value,false);
    }

    /** Implementation for put and putIfAbsent
     * 总体步骤:
     * 1.判定key,value合法性
     * 2.插入位置为空bin
     * 3.插入位置<a href="https://www.jb51.cc/tag/zhengzaijinxing/" target="_blank">正在进行</a>resize
     * 4.插入位置在table中,且该位置未进行resize
     * 5.插入完成后,判定bin中节点个数是否>=8,从而决定是否进行链表转红黑树.
     *
     */
    final V putVal(K key,V value,boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        //<a href="https://www.jb51.cc/tag/huoqu/" target="_blank">获取</a>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();
            //如果插入位置为空的bin
            else if ((f = tabAt(tab,i = (n - 1) &amp; hash)) == null) {
                if (casTabAt(tab,null,new Node<K,V>(hash,key,null)))
                    break;                   // no lock when adding to empty bin
            }
            //如果查找位置为forwarding node
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab,f);
            //在当前table中查找插入位置
            else {
                V oldVal = null;
                //同步<a href="https://www.jb51.cc/tag/daima/" target="_blank">代码</a>块,保证插入安全
                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 &amp;&amp;
                                        ((ek = e.key) == key ||
                                                (ek != null &amp;&amp; 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,null);
                                    break;
                                }
                            }
                        }
                        //如果为红黑树
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash,value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                //插入节点后,检查bin中节点个数是否>=8,如果大于,则由链表转为红黑树
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab,i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L,binCount);
        return null;
    }


    public void putAll(Map<? extends K,? extends V> m) {
        //对table的size进行设置,使得其可以容纳新加入的元素.
        tryPresize(m.size());
        for (Map.Entry<? extends K,? extends V> e : m.entrySet())
            putVal(e.getKey(),e.getValue(),false);
    }

    public V remove(Object key) {
        return replaceNode(key,null);
    }

    //此<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>是对4个公有<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>remove/replace的辅助<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>.
    final V replaceNode(Object key,Object cv) {
        int hash = spread(key.hashCode());
        for (Node<K,fh;
            //空表or查找位置bin为null
            if (tab == null || (n = tab.length) == 0 ||
                    (f = tabAt(tab,i = (n - 1) &amp; hash)) == null)
                break;
            //如果查找节点为转移节点forwarding node
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab,f);
            else {
                V oldVal = null;
                boolean validated = false;
                //同步代码块,保证删除安全性
                synchronized (f) {
                    if (tabAt(tab,i) == f) {
                        //bin为链表结构
                        if (fh >= 0) {
                            validated = true;
                            for (Node<K,V> e = f,pred = null;;) {
                                K ek;
                                if (e.hash == hash &amp;&amp;
                                        ((ek = e.key) == key ||
                                                (ek != null &amp;&amp; key.equals(ek)))) {
                                    V ev = e.val;
                                    if (cv == null || cv == ev ||
                                            (ev != null &amp;&amp; cv.equals(ev))) {
                                        oldVal = ev;
                                        if (value != null)
                                            e.val = value;
                                        else if (pred != null)
                                            pred.next = e.next;
                                        else
                                            setTabAt(tab,e.next);
                                    }
                                    break;
                                }
                                //记录上<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>访问节点
                                pred = e;
                                //更新e为下<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>节点
                                if ((e = e.next) == null)
                                    break;
                            }
                        }
                        //bin为红黑树结构
                        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 &amp;&amp;
                                    (p = r.findTreeNode(hash,null)) != null) {
                                V pv = p.val;
                                if (cv == null || cv == pv ||
                                        (pv != null &amp;&amp; cv.equals(pv))) {
                                    oldVal = pv;
                                    if (value != null)
                                        p.val = value;
                                    else if (t.removeTreeNode(p))
                                        setTabAt(tab,untreeify(t.f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t));
                                }
                            }
                        }
                    }
                }
                if (validated) {
                    if (oldVal != null) {
                        if (value == null)
                            //更新节点个数
                            addCount(-1L,-1);
                        return oldVal;
                    }
                    break;
                }
            }
        }
        return null;
    }

    public void clear() {
        long delta = 0L; // negative number of deletions
        int i = 0;
        Node<K,V>[] tab = table;
        while (tab != null &amp;&amp; i < tab.length) {
            int fh;
            Node<K,V> f = tabAt(tab,i);
            if (f == null)
                ++i;
            //如果节点为转移节点forwarding node
            else if ((fh = f.hash) == MOVED) {
                tab = helpTransfer(tab,f);
                i = 0; // restart
            }
            else {
                //同步<a href="https://www.jb51.cc/tag/daima/" target="_blank">代码</a>块,<a href="https://www.jb51.cc/tag/shanchu/" target="_blank">删除</a>i位置处的节点
                synchronized (f) {
                    if (tabAt(tab,i) == f) {
                        Node<K,V> p = (fh >= 0 ? f :
                                (f instanceof TreeBin) ?
                                        ((TreeBin<K,V>)f).f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t : null);
                        while (p != null) {
                            --delta;
                            p = p.next;
                        }
                        setTabAt(tab,i++,null);
                    }
                }
            }
        }
        if (delta != 0L)
            addCount(delta,-1);
    }


    public KeySetView<K,V> keySet() {
        KeySetView<K,V> ks;
        return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this,null));
    }

    public Collection<V> values() {
        ValuesView<K,V> vs;
        return (vs = values) != null ? vs : (values = new ValuesView<K,V>(this));
    }

    public Set<Map.Entry<K,V>> entrySet() {
        EntrySetView<K,V> es;
        return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));
    }

    //返回map的hash值.
    //结果=sum(key.hashCode() ^ value.hashCode())
    public int hashCode() {
        int h = 0;
        Node<K,V> p; (p = it.advance()) != null; )
                h += p.key.hashCode() ^ p.val.hashCode();
        }
        return h;
    }

    //格式:{key1=value1,key2=value2,...}
    public String toString() {
        Node<K,V>[] t;
        int f = (t = table) == null ? 0 : t.length;
        Traverser<K,f,f);
        StringBuilder sb = new StringBuilder();
        sb.append('{');
        Node<K,V> p;
        if ((p = it.advance()) != null) {
            for (;;) {
                K k = p.key;
                V v = p.val;
                sb.append(k == this ? "(this Map)" : k);
                sb.append('=');
                sb.append(v == this ? "(this Map)" : v);
                if ((p = it.advance()) == null)
                    break;
                sb.append(',').append(' ');
            }
        }
        return sb.append('}').toString();
    }

    /**
     * Compares the specified object with this map for equality.
     * Returns {@code true} if the given object is a map with the same
     * mappings as this map.  This operation may return misleading
     * results if either map is concurrently modified during execution
     * of this method.
     *
     * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m o object to be compared for equality with this map
     * @return {@code true} if the specified object is equal to this map
     */
    public boolean equals(Object o) {
        //内存地址是否相同
        if (o != this) {
            //是否为map类型
            if (!(o instanceof Map))
                return false;
            //类型转化
            Map<?,?> m = (Map<?,?>) o;
            Node<K,V>[] t;
            //记录table长度
            int f = (t = table) == null ? 0 : t.length;
            Traverser<K,f);
            //遍历table,检查和o的value一致性
            for (Node<K,V> p; (p = it.advance()) != null; ) {
                V val = p.val;
                Object v = m.get(p.key);
                if (v == null || (v != val &amp;&amp; !v.equals(val)))
                    return false;
            }
            //遍历o,检查自身key和value的合法性
            for (Map.Entry<?,?> e : m.entrySet()) {
                Object mk,mv,v;
                if ((mk = e.getKey()) == null ||
                        (mv = e.getValue()) == null ||
                        (v = get(mk)) == null ||
                        (mv != v &amp;&amp; !mv.equals(v)))
                    return false;
            }
        }
        return true;
    }


    //旧版本中使用的类,存在的意义:序列化兼容性
    static class Segment<K,V> extends <a href="https://www.jb51.cc/tag/reentrantlock/" target="_blank">reentrantlock</a> implements Serializable {
        private static final long serialVersionUID = 2249069246763182397L;
        final float loadFactor;
        Segment(float lf) { this.loadFactor = lf; }
    }

    //用于序列化:将concurrenthashmap写入stream中.
    private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
        // 用于序列化版本兼容
        // Emulate segment cal<a href="https://www.jb51.cc/tag/cula/" target="_blank">cula</a>tion from prev<a href="https://www.jb51.cc/tag/IoU/" target="_blank">IoU</a>s version of this class
        int sshift = 0;
        int ssize = 1;
        while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
            ++sshift;
            ssize <<= 1;
        }
        int segmentShift = 32 - sshift;
        int segmentMask = ssize - 1;
        @SuppressWarnings("unchecked")
        Segment<K,V>[] segments = (Segment<K,V>[])
                new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
        for (int i = 0; i < segments.length; ++i)
            segments[i] = new Segment<K,V>(LOAD_FACTOR);
        s.putFields().put("segments",segments);
        s.putFields().put("segmentShift",segmentShift);
        s.putFields().put("segmentMask",segmentMask);
        s.writeFields();

        Node<K,V> p; (p = it.advance()) != null; ) {
                s.writeObject(p.key);
                s.writeObject(p.val);
            }
        }
        s.writeObject(null);
        s.writeObject(null);
        segments = null; // throw away
    }


    private void rea<a href="https://www.jb51.cc/tag/dob/" target="_blank">dob</a>ject(java.io.ObjectInputStream s)
            throws java.io.IOException,ClassNotFoundException {
        /*
         * 为了在典型情况下提高<a href="https://www.jb51.cc/tag/xingneng/" target="_blank">性能</a>,我们在读取时创建节点,然后在知道大小后放置在表中.
         * 但是,我们还必须验证唯一性并处理过多的bin,这需要putVal机制的专用版本
         */
        sizeCtl = -1; // force exclusion for table construction
        s.defaultRea<a href="https://www.jb51.cc/tag/dob/" target="_blank">dob</a>ject();
        long size = 0L;
        Node<K,V> p = null;
        for (;;) {
            @SuppressWarnings("unchecked")
            K k = (K) s.rea<a href="https://www.jb51.cc/tag/dob/" target="_blank">dob</a>ject();
            @SuppressWarnings("unchecked")
            V v = (V) s.rea<a href="https://www.jb51.cc/tag/dob/" target="_blank">dob</a>ject();
            if (k != null &amp;&amp; v != null) {
                p = new Node<K,V>(spread(k.hashCode()),k,p);
                ++size;
            }
            else
                break;
        }
        if (size == 0L)
            sizeCtl = 0;
        else {
            int n;
            if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
                n = MAXIMUM_CAPACITY;
            else {
                int sz = (int)size;
                n = tableSi<a href="https://www.jb51.cc/tag/zef/" target="_blank">zef</a>or(sz + (sz >>> 1) + 1);
            }
            @SuppressWarnings("unchecked")
            Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
            int mask = n - 1;
            long added = 0L;
            while (p != null) {
                boolean insertAtFront;
                Node<K,V> next = p.next,f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t;
                int h = p.hash,j = h &amp; mask;
                if ((f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t = tabAt(tab,j)) == null)
                    insertAtFront = true;
                else {
                    K k = p.key;
                    if (f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t.hash < 0) {
                        TreeBin<K,V>)f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t;
                        if (t.putTreeVal(h,p.val) == null)
                            ++added;
                        insertAtFront = false;
                    }
                    else {
                        int binCount = 0;
                        insertAtFront = true;
                        Node<K,V> q; K qk;
                        for (q = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t; q != null; q = q.next) {
                            if (q.hash == h &amp;&amp;
                                    ((qk = q.key) == k ||
                                            (qk != null &amp;&amp; k.equals(qk)))) {
                                insertAtFront = false;
                                break;
                            }
                            ++binCount;
                        }
                        if (insertAtFront &amp;&amp; binCount >= TREEIFY_THRESHOLD) {
                            insertAtFront = false;
                            ++added;
                            p.next = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t;
                            TreeNode<K,V> hd = null,tl = null;
                            for (q = p; q != null; q = q.next) {
                                TreeNode<K,V> t = new TreeNode<K,V>
                                        (q.hash,q.key,q.val,null);
                                if ((t.prev = tl) == null)
                                    hd = t;
                                else
                                    tl.next = t;
                                tl = t;
                            }
                            setTabAt(tab,j,new TreeBin<K,V>(hd));
                        }
                    }
                }
                if (insertAtFront) {
                    ++added;
                    p.next = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t;
                    setTabAt(tab,p);
                }
                p = next;
            }
            table = tab;
            sizeCtl = n - (n >>> 2);
            baseCount = added;
        }
    }

    /*-------ConcurrentMap<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>---------*/

    //存在,替换,返回旧value;否则不操作,返回null
    public V putIfAbsent(K key,true);
    }


    public boolean remove(Object key,Object value) {
        if (key == null)
            throw new NullPointerException();
        return value != null &amp;&amp; replaceNode(key,value) != null;
    }

    public boolean replace(K key,V oldValue,V newValue) {
        if (key == null || oldValue == null || newValue == null)
            throw new NullPointerException();
        return replaceNode(key,newValue,oldValue) != null;
    }

    public V replace(K key,V value) {
        if (key == null || value == null)
            throw new NullPointerException();
        return replaceNode(key,null);
    }

    /*--------Overrides在JDK8中Map接口扩展的<a href="https://www.jb51.cc/tag/mo/" target="_blank">默</a>认<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>--------*/

    //key有value,则返回value;
    //否则返回参数值
    public V g<a href="https://www.jb51.cc/tag/eto/" target="_blank">eto</a>rDefault(Object key,V defaultValue) {
        V v;
        return (v = get(key)) == null ? defaultValue : v;
    }

    public void forEach(BiConsumer<? super K,? super V> action) {
        if (action == null) throw new NullPointerException();
        Node<K,V> p; (p = it.advance()) != null; ) {
                action.accept(p.key,p.val);
            }
        }
    }

    public void replaceAll(BiFunction<? super K,? super V,? extends V> function) {
        if (function == null) throw new NullPointerException();
        Node<K,V> p; (p = it.advance()) != null; ) {
                V oldValue = p.val;
                for (K key = p.key;;) {
                    V newValue = function.apply(key,oldValue);
                    if (newValue == null)
                        throw new NullPointerException();
                    if (replaceNode(key,oldValue) != null ||
                            (oldValue = get(key)) == null)
                        break;
                }
            }
        }
    }

    /**
     * 如果指定的键尚未与值关联,则尝试使用给定的映射<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>计算其值,并将其输入到该映射中,除非是null.
     * 整个<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a><a href="https://www.jb51.cc/tag/diaoyong/" target="_blank">调用</a>是以原子方式执行的,因此每个键最多应用一次该<a href="https://www.jb51.cc/tag/gongneng/" target="_blank">功能</a>。
     * 在进行计算时,其他线程在此映射上的某些尝试更新操作可能会被阻止,因此计算应该简短并且不要尝试更新此map中的任何其他映射。
     */
    public V co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>teIfAbsent(K key,Function<? super K,? extends V> mappingFunction) {
        if (key == null || mappingFunction == null)
            throw new NullPointerException();
        int h = spread(key.hashCode());
        V val = null;
        int binCount = 0;
        for (Node<K,fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            //不存在
            else if ((f = tabAt(tab,i = (n - 1) &amp; h)) == null) {
                Node<K,V> r = new ReservationNode<K,V>();
                //同步<a href="https://www.jb51.cc/tag/daima/" target="_blank">代码</a>块,计算新值并插入map
                synchronized (r) {
                    if (casTabAt(tab,r)) {
                        binCount = 1;
                        Node<K,V> node = null;
                        try {
                            if ((val = mappingFunction.apply(key)) != null)
                                node = new Node<K,V>(h,val,null);
                        } finally {
                            setTabAt(tab,node);
                        }
                    }
                }
                if (binCount != 0)
                    break;
            }
            //此节点为转移节点forwarding node
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab,f);
            //存在,且不是转移节点
            else {
                boolean added = false;
                //同步<a href="https://www.jb51.cc/tag/daima/" target="_blank">代码</a>块:分链表和红黑树两种情况进行插入
                synchronized (f) {
                    if (tabAt(tab,i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek; V ev;
                                if (e.hash == h &amp;&amp;
                                        ((ek = e.key) == key ||
                                                (ek != null &amp;&amp; key.equals(ek)))) {
                                    val = e.val;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    if ((val = mappingFunction.apply(key)) != null) {
                                        added = true;
                                        pred.next = new Node<K,null);
                                    }
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            binCount = 2;
                            TreeBin<K,p;
                            if ((r = t.root) != null &amp;&amp;
                                    (p = r.findTreeNode(h,null)) != null)
                                val = p.val;
                            else if ((val = mappingFunction.apply(key)) != null) {
                                added = true;
                                t.putTreeVal(h,val);
                            }
                        }
                    }
                }
                //插入后,判定是否需要将链表转为红黑树
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab,i);
                    if (!added)
                        return val;
                    break;
                }
            }
        }
        //<a href="https://www.jb51.cc/tag/zengjia/" target="_blank">增加</a>节点个数
        if (val != null)
            addCount(1L,binCount);
        return val;
    }

    /**
     * 如果指定的键尚已经与值关联,则尝试使用给定的映射<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>计算其值,并更改该映射.
     * 整个<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a><a href="https://www.jb51.cc/tag/diaoyong/" target="_blank">调用</a>是以原子方式执行的,因此每个键最多应用一次该<a href="https://www.jb51.cc/tag/gongneng/" target="_blank">功能</a>。
     * 在进行计算时,其他线程在此映射上的某些尝试更新操作可能会被阻止,因此计算应该简短并且不要尝试更新此map中的任何其他映射。
     */
    public V co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>teIfPresent(K key,BiFunction<? super K,? extends V> remappingFunction) {
        if (key == null || remappingFunction == null)
            throw new NullPointerException();
        int h = spread(key.hashCode());
        V val = null;
        int delta = 0;
        int binCount = 0;
        for (Node<K,fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            //如果为null,返回
            else if ((f = tabAt(tab,i = (n - 1) &amp; h)) == null)
                break;
            //如果为转移节点,帮助转移
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab,f);
            //计算值并替换
            else {
                //同步<a href="https://www.jb51.cc/tag/daima/" target="_blank">代码</a>块,分链表和红黑树节点讨论插入.
                synchronized (f) {
                    if (tabAt(tab,pred = null;; ++binCount) {
                                K ek;
                                if (e.hash == h &amp;&amp;
                                        ((ek = e.key) == key ||
                                                (ek != null &amp;&amp; key.equals(ek)))) {
                                    val = remappingFunction.apply(key,e.val);
                                    if (val != null)
                                        e.val = val;
                                    else {
                                        delta = -1;
                                        Node<K,V> en = e.next;
                                        if (pred != null)
                                            pred.next = en;
                                        else
                                            setTabAt(tab,en);
                                    }
                                    break;
                                }
                                pred = e;
                                if ((e = e.next) == null)
                                    break;
                            }
                        }
                        else if (f instanceof TreeBin) {
                            binCount = 2;
                            TreeBin<K,null)) != null) {
                                val = remappingFunction.apply(key,p.val);
                                if (val != null)
                                    p.val = val;
                                else {
                                    delta = -1;
                                    if (t.removeTreeNode(p))
                                        setTabAt(tab,untreeify(t.first));
                                }
                            }
                        }
                    }
                }
                if (binCount != 0)
                    break;
            }
        }
        if (delta != 0)
            addCount((long)delta,binCount);
        return val;
    }

    //指定key如果没有value,则为其计算一个value
    public V compute(K key,fh;
            //如果表为null,则初始化表
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            //如果指定位置为null
            else if ((f = tabAt(tab,V>();
                //同步<a href="https://www.jb51.cc/tag/daima/" target="_blank">代码</a>块:为其计算值,并插入map
                synchronized (r) {
                    if (casTabAt(tab,V> node = null;
                        try {
                            if ((val = remappingFunction.apply(key,null)) != null) {
                                delta = 1;
                                node = new Node<K,null);
                            }
                        } finally {
                            //插入map
                            setTabAt(tab,node);
                        }
                    }
                }
                if (binCount != 0)
                    break;
            }
            //如果指定位置为转移节点,当前线程转去帮忙转移节点
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab,f);
            //同步代码块
            else {
                synchronized (f) {
                    if (tabAt(tab,i) == f) {
                        //链表节点
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,e.val);
                                    //计算的value不为null,更改原value
                                    if (val != null)
                                        e.val = val;
                                    //计算的value为null
                                    else {
                                        delta = -1;
                                        Node<K,V> en = e.next;
                                        //上<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>节点为为null,<a href="https://www.jb51.cc/tag/shanchu/" target="_blank">删除</a>当前节点
                                        if (pred != null)
                                            pred.next = en;
                                        //上<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>节点为null
                                        else
                                            setTabAt(tab,en);
                                    }
                                    break;
                                }
                                pred = e;
                                if ((e = e.next) == null) {
                                    val = remappingFunction.apply(key,null);
                                    if (val != null) {
                                        delta = 1;
                                        pred.next =
                                                new Node<K,null);
                                    }
                                    break;
                                }
                            }
                        }
                        //红黑树树节点
                        else if (f instanceof TreeBin) {
                            binCount = 1;
                            TreeBin<K,p;
                            if ((r = t.root) != null)
                                p = r.findTreeNode(h,null);
                            else
                                p = null;
                            V pv = (p == null) ? null : p.val;
                            val = remappingFunction.apply(key,pv);
                            if (val != null) {
                                if (p != null)
                                    p.val = val;
                                else {
                                    delta = 1;
                                    t.putTreeVal(h,val);
                                }
                            }
                            else if (p != null) {
                                delta = -1;
                                if (t.removeTreeNode(p))
                                    setTabAt(tab,untreeify(t.first));
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab,i);
                    break;
                }
            }
        }
        if (delta != 0)
            addCount((long)delta,binCount);
        return val;
    }

    /**
     * 如果指定的键尚未与(非空)值相关联,则将其与给定值value相关联。
     * 否则,将该值替换为给定的重映射<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>的结果,或者如果为null则被移除.
     * 整个<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a><a href="https://www.jb51.cc/tag/diaoyong/" target="_blank">调用</a>是以原子方式执行的。其他线程在此映射上的某些尝试更新操作可能会被阻止当计算<a href="https://www.jb51.cc/tag/zhengzaijinxing/" target="_blank">正在进行</a>时,所以计算应该简短,
     * 并且不能尝试更新此Map的任何其他映射。
     */
    public V merge(K key,BiFunction<? super V,? extends V> remappingFunction) {
        if (key == null || value == null || remappingFunction == null)
            throw new NullPointerException();
        int h = spread(key.hashCode());
        V val = null;
        int delta = 0;
        int binCount = 0;
        for (Node<K,fh;
            //如果tab为null,初始化table
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            //如果该散列位置没有元素,为null
            else if ((f = tabAt(tab,i = (n - 1) &amp; h)) == null) {
                //利用CAS为索引i处节点赋值
                if (casTabAt(tab,null))) {
                    delta = 1;
                    val = value;
                    break;
                }
            }
            //如果table在进行resize,则当前线程帮忙去resize
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab,f);
            //如果散列位置有数值
            else {
                //同步代码块:
                synchronized (f) {
                    //查找i处的节点
                    if (tabAt(tab,i) == f) {
                        //如果为链表节点
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,pred = null;; ++binCount) {
                                K ek;
                                if (e.hash == h &amp;&amp;
                                        ((ek = e.key) == key ||
                                                (ek != null &amp;&amp; key.equals(ek)))) {
                                    val = remappingFunction.apply(e.val,value);
                                    if (val != null)
                                        e.val = val;
                                    else {
                                        delta = -1;
                                        Node<K,V> en = e.next;
                                        if (pred != null)
                                            pred.next = en;
                                        //原value=新value=null,则<a href="https://www.jb51.cc/tag/shanchu/" target="_blank">删除</a>当前节点
                                        else
                                            setTabAt(tab,en);
                                    }
                                    break;
                                }
                                pred = e;
                                if ((e = e.next) == null) {
                                    delta = 1;
                                    val = value;
                                    pred.next =
                                            new Node<K,null);
                                    break;
                                }
                            }
                        }
                        //如果节点为红黑树节点
                        else if (f instanceof TreeBin) {
                            binCount = 2;
                            TreeBin<K,V> r = t.root;
                            TreeNode<K,V> p = (r == null) ? null :
                                    r.findTreeNode(h,null);
                            val = (p == null) ? value :
                                    remappingFunction.apply(p.val,value);
                            if (val != null) {
                                if (p != null)
                                    p.val = val;
                                else {
                                    delta = 1;
                                    t.putTreeVal(h,binCount);
        return val;
    }

    /*-----------Hashtable的传统<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>------------*/

    //此<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>在<a href="https://www.jb51.cc/tag/gongneng/" target="_blank">功能</a>上与containsValue(Object)完全相同
    public boolean contains(Object value) {
        return containsValue(value);
    }

    //返回key的枚举
    public Enumeration<K> keys() {
        Node<K,V>[] t;
        int f = (t = table) == null ? 0 : t.length;
        return new KeyI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,this);
    }

    //返回value的枚举
    public Enumeration<V> elements() {
        Node<K,V>[] t;
        int f = (t = table) == null ? 0 : t.length;
        return new ValueI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,this);
    }

    /*-----------ConcurrentHashMap-only methods------独有<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>------------*/

    /**
     * 返回映射的<a href="https://www.jb51.cc/tag/shuliang/" target="_blank">数量</a>。
     * 求映射个数时,应该使用此<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>而不是size()<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>,因为ConcurrentHashMap包含映射个数可以比Integer.MAX_VALUE更多。
     * 注意:本<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>返回的值是<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>估计值;如果并发插入或<a href="https://www.jb51.cc/tag/shanchu/" target="_blank">删除</a>,实际计数可能会有所不同。
     * @return the number of mappings
     * @since 1.8
     */
    public long mappingCount() {
        long n = sumCount();
        return (n < 0L) ? 0L : n; // ig<a href="https://www.jb51.cc/tag/nor/" target="_blank">nor</a>e transient negative values
    }

    /**
     * 根据给定类型Boolean.TRUE,新建<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>Set,当然这个set也是由ConcurrentHashMap作为后备支撑的
     * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m <K> the element type of the returned set
     * @return the new set
     * @since 1.8
     */
    public static <K> KeySetView<K,Boolean> newKeySet() {
        return new KeySetView<K,Boolean>
                (new ConcurrentHashMap<K,Boolean>(),Boolean.TRUE);
    }

    /**
     * @since 1.8
     */
    public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
        return new KeySetView<K,Boolean>(initialCapacity),Boolean.TRUE);
    }

    //根据给定的通用value,在add,addAll<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>中可以随意<a href="https://www.jb51.cc/tag/tianjia/" target="_blank">添加</a>值.这当然只适用于从该视图中为所有<a href="https://www.jb51.cc/tag/tianjia/" target="_blank">添加</a>使用相同值的情况。
    public KeySetView<K,V> keySet(V mappedValue) {
        if (mappedValue == null)
            throw new NullPointerException();
        return new KeySetView<K,mappedValue);
    }

    /* ---------------- Special Nodes 特殊节点 -------------- */


    /**
     * <a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>用于连接两个table的节点类。它包含<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>nextTable指针,用于指向下一张表。而且这个节点的key,next指针全部为null,
     * 它的hash值为-1. 这里面定义的find的<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>是从nextTable里进行<a href="https://www.jb51.cc/tag/chaxun/" target="_blank">查询</a>节点,而不是以自身为头节点进行查找
     */
    static final class ForwardingNode<K,V> extends Node<K,V> {
        final Node<K,V>[] nextTable;
        ForwardingNode(Node<K,V>[] tab) {
            //hash值=MOVED=-1
            super(MOVED,null);
            this.nextTable = tab;
        }

        Node<K,Object k) {
            // loop to avoid arbitrarily deep recursion on forwarding nodes
            //循环以避免转发节点上的任意深度递归
            outer: for (Node<K,V>[] tab = nextTable;;) {
                Node<K,V> e; int n;
                //如果table为null,or长度为0,or指定bin无元素
                if (k == null || tab == null || (n = tab.length) == 0 ||
                        (e = tabAt(tab,(n - 1) &amp; h)) == null)
                    return null;
                //循环
                for (;;) {
                    int eh; K ek;
                    if ((eh = e.hash) == h &amp;&amp;
                            ((ek = e.key) == k || (ek != null &amp;&amp; k.equals(ek))))
                        return e;
                    //哈希值<0
                    if (eh < 0) {
                        //如果是转发节点
                        if (e instanceof ForwardingNode) {
                            //更新查找到新table
                            tab = ((ForwardingNode<K,V>)e).nextTable;
                            continue outer;
                        }
                        //非转发节点,则直接查找
                        else
                            return e.find(h,k);
                    }
                    if ((e = e.next) == null)
                        return null;
                }
            }
        }
    }

    //在co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>teIfAbsent和co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>中的节点占位符
    static final class ReservationNode<K,V> {
        ReservationNode() {
            super(RESERVED,null);
        }

        Node<K,Object k) {
            return null;
        }
    }

    /* ---------------- Table 初始化 and Resizing -------------- */

    //返回用于调整大小为n的table的<a href="https://www.jb51.cc/tag/biaoji/" target="_blank">标记</a>位。左移RESIZE_STAMP_SHIFT二进制位时,数值必为负.
    static final int resizeStamp(int n) {
        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
    }

    //使用sizeCtl中记录的size值初始化table
    //对于ConcurrentHashMap来说,<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank">调用</a>它的构造<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>仅仅是设置了一些参数而已。
    //而整个table的初始化是在向ConcurrentHashMap中插入元素的时候发生的。
    private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            //如果当前有线程在对table进行初始化,则当前线程被阻塞,这也可以看出ConcurrentHashMap的初始化只能由<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>线程完成.
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // 初始化失败,进行自旋
            //利用CAS方法把sizectl的值置为-1,防止其他线程进入,表示本线程正在进行初始化
            else if (U.compareAndSwapInt(this,SIZECTL,sc,-1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        //初始化大小为n的node数组
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,?>[n];
                        table = tab = nt;
                        sc = n - (n >>> 2);////相当于0.75*n 设置<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>扩容的阈值
                    }
                } finally {
                    sizeCtl = sc;//sizeCtl的值改为0.75*n
                }
                break;
            }
        }
        return tab;
    }

    /**
     * <a href="https://www.jb51.cc/tag/zengjia/" target="_blank">增加</a>节点个数,如果table太小而没有resize,则检查是否需要resize。如果已经调整大小,则可以帮助复制转移节点。转移后重新检查占用情况,
     * 以确定是否还需要调整大小,因为resize总是比put操作滞后。
     */
    private final void addCount(long x,int check) {
        CounterCell[] as; long b,s;
        if ((as = counterCells) != null ||
                !U.compareAndSwapLong(this,BASECOUNT,b = baseCount,s = b + x)) {
            CounterCell a; long v; int m;
            boolean uncontended = true;
            if (as == null || (m = as.length - 1) < 0 ||
                    (a = as[ThreadLocalRandom.getProbe() &amp; m]) == null ||
                    !(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,nt; int n,sc;
            while (s >= (long)(sc = sizeCtl) &amp;&amp; (tab = table) != null &amp;&amp;
                    (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;
                    if (U.compareAndSwapInt(this,sc + 1))
                        transfer(tab,nt);
                }
                else if (U.compareAndSwapInt(this,(rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab,null);
                s = sumCount();
            }
        }
    }

    //如果resize<a href="https://www.jb51.cc/tag/zhengzaijinxing/" target="_blank">正在进行</a>,则多个线程帮助节点的复制操作.
    final Node<K,V>[] helpTransfer(Node<K,V> f) {
        Node<K,V>[] nextTab; int sc;
        //如果tab不为null,且f为转移节点,且新table不为null
        if (tab != null &amp;&amp; (f instanceof ForwardingNode) &amp;&amp;
                (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
            //返回resize后的table的<a href="https://www.jb51.cc/tag/biaoji/" target="_blank">标记</a>位
            int rs = resizeStamp(tab.length);
            while (nextTab == nextTable &amp;&amp; table == tab &amp;&amp;
                    (sc = sizeCtl) < 0) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || transferIndex <= 0)
                    break;
                if (U.compareAndSwapInt(this,sc + 1)) {
                    transfer(tab,nextTab);
                    break;
                }
            }
            return nextTab;
        }
        return table;
    }

    //尝试将table大小设定为:1.5*size+1,以容纳元素
    private final void tryPresize(int size) {
        int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
                tableSi<a href="https://www.jb51.cc/tag/zef/" target="_blank">zef</a>or(size + (size >>> 1) + 1);
        int sc;
        while ((sc = sizeCtl) >= 0) {
            Node<K,V>[] tab = table; int n;
            if (tab == null || (n = tab.length) == 0) {
                n = (sc > c) ? sc : c;
                if (U.compareAndSwapInt(this,-1)) {
                    try {
                        if (table == tab) {
                            @SuppressWarnings("unchecked")
                            Node<K,?>[n];
                            table = nt;
                            sc = n - (n >>> 2);
                        }
                    } finally {
                        sizeCtl = sc;
                    }
                }
            }
            else if (c <= sc || n >= MAXIMUM_CAPACITY)
                break;
            else if (tab == table) {
                int rs = resizeStamp(n);
                if (sc < 0) {
                    Node<K,V>[] nt;
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                            sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                            transferIndex <= 0)
                        break;
                    if (U.compareAndSwapInt(this,null);
            }
        }
    }



    /**
     * 这是ConcurrentHashMa的扩容<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>
     * 将每<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>bin拷贝到新的table中
     */
    private final void transfer(Node<K,V>[] nextTab) {
        int n = tab.length,stride;
        //如果可用<a href="https://www.jb51.cc/tag/cpu/" target="_blank">cpu</a>数目>1,则stride=tab长度/<a href="https://www.jb51.cc/tag/cpu/" target="_blank">cpu</a><a href="https://www.jb51.cc/tag/shuliang/" target="_blank">数量</a>
        if ((stride = (N<a href="https://www.jb51.cc/tag/cpu/" target="_blank">cpu</a> > 1) ? (n >>> 3) / N<a href="https://www.jb51.cc/tag/cpu/" target="_blank">cpu</a> : n) < MIN_TRANSFER_STRIDE)
            //如果此时stride<最小分割并行段数,则更新stride为最小分割并行段数
            stride = MIN_TRANSFER_STRIDE; // subdivide range
        //如果新table为null,则对新table初始化,长度为旧table的2倍
        if (nextTab == null) {            // initiating
            try {
                @SuppressWarnings("unchecked")
                Node<K,?>[n << 1];//2倍扩容
                nextTab = nt;
            } catch (Throwable ex) {      // try to <a href="https://www.jb51.cc/tag/cop/" target="_blank">cop</a>e with OOME
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            //nextTable指向新建table
            nextTable = nextTab;
            //转移索引改为n
            transferIndex = n;
        }
        //新table长度
        int nextn = nextTab.length;
        //转移节点:设定为新table,hash值=-1,其他<a href="https://www.jb51.cc/tag/shuxing/" target="_blank">属性</a>为null
        ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
        boolean advance = true;///并发扩容的关键<a href="https://www.jb51.cc/tag/shuxing/" target="_blank">属性</a> 如果等于true 说明这个节点已经处理过
        //确保在提交nextTab之前进行扫描
        boolean finishing = false; // to ensure sweep before committing nextTab
        for (int i = 0,bound = 0;;) {
            Node<K,V> f; int fh;
            ////这个while循环体的作用就是在控制i--  通过i--可以依次遍历原hash表中的节点
            while (advance) {
                int nextIndex,nextBound;
                if (--i >= bound || finishing)
                    advance = false;
                else if ((nextIndex = transferIndex) <= 0) {
                    i = -1;
                    advance = false;
                }
                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 清空临时对象nextTabl
                if (finishing) {
                    nextTable = null;
                    table = nextTab;
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }
                if (U.compareAndSwapInt(this,sc = sizeCtl,sc - 1)) {
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        return;
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            //i位置节点为null,原table中的i位置放入forwardNode节点,这个也是触发并发扩容的关键点;
            else if ((f = tabAt(tab,i)) == null)
                advance = casTabAt(tab,fwd);
            //当前节点已经被复制过,直接跳过.是控制并发扩容的关键
            else if ((fh = f.hash) == MOVED)
                advance = true; // already processed
            //同步代码块,复制节点,保证线程安全的复制,不重复不冲突
            else {
                synchronized (f) {
                    if (tabAt(tab,V> ln,hn;
                        //如果节点为链表节点
                        if (fh >= 0) {
                            int runBit = fh &amp; n;
                            Node<K,V> lastRun = f;
                            //查找lastRun的位置
                            for (Node<K,V> p = f.next; p != null; p = p.next) {
                                int b = p.hash &amp; n;
                                if (b != runBit) {
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                            if (runBit == 0) {
                                ln = lastRun;
                                hn = null;
                            }
                            else {
                                hn = lastRun;
                                ln = null;
                            }
                            //lastRun节点前的节点都会构造<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>反序链表,lastRun节点开始到后面的节点则顺序不变
                            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 &amp; n) == 0)
                                    ln = new Node<K,V>(ph,pk,pv,ln);
                                else
                                    hn = new Node<K,hn);
                            }
                            //在nextTable的i位置上插入<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>链表
                            setTabAt(nextTab,ln);
                            //在nextTable的i+n的位置上插入另<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>链表
                            setTabAt(nextTab,i + n,hn);
                            //在table的i位置上插入forwardNode节点  表示已经处理过该节点
                            setTabAt(tab,fwd);
                            //设置advance为true 返回到上面的while循环中 就可以执行i--操作
                            advance = true;
                        }
                        //如果被复制节点为红黑树节点包装类TreeBin,也做<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>反序处理,并且判断是否需要untreeify,
                        //把处理的结果分别放在nextTable的i和i+n的位置上
                        else if (f instanceof TreeBin) {
                            TreeBin<K,V> lo = null,loTail = null;
                            TreeNode<K,V> hi = null,hiTail = null;
                            int lc = 0,hc = 0;
                            for (Node<K,V> e = t.f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t; e != null; e = e.next) {
                                int h = e.hash;
                                TreeNode<K,V> p = new TreeNode<K,V>
                                        (h,e.key,e.val,null);
                                if ((h &amp; 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;
                                }
                            }
                            ////如果扩容后已经不再需要tree的结构 反向转换为链表结构
                            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;
                            //下面<a href="https://www.jb51.cc/tag/gongneng/" target="_blank">功能</a>和链表处理一致
                            setTabAt(nextTab,ln);
                            setTabAt(nextTab,hn);
                            setTabAt(tab,fwd);
                            advance = true;
                        }
                    }
                }
            }
        }
    }

    /* ---------------- Counter support 计数器<a href="https://www.jb51.cc/tag/zhichi/" target="_blank">支持</a><a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>-------------- */

    /**
     * A padded cell for <a href="https://www.jb51.cc/tag/dis/" target="_blank">dis</a>tributing counts.  Adapted from LongAdder
     * and Striped64.  See their internal docs for explanation.
     * 用于分发计数的填充单元格。改编自LongAdder和Striped64。请参阅他们的内部文档以获得解释。
     * 用于辅助sumCount()<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>
     */
    @sun.misc.Contended static final class CounterCell {
        //内存可见value
        volatile long value;
        CounterCell(long x) { value = x; }
    }

    //ConcurrentHashMap中节点总数
    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;
    }

    /**
     * LongAdder是java8新增的.
     * LongAdders与ConcurrentHashMap一起使用,以维护可伸缩的频率映射(一种直方图或多重集)。
     * 例如,要为ConcurrentHashMap<String,LongAdder> freqs <a href="https://www.jb51.cc/tag/tianjia/" target="_blank">添加</a><a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>计数,
     * 初始化(如果尚未存在),可以使用freqs.co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>teIfAbsent(k  - > new LongAdder())
     */
    private final void fullAddCount(long x,boolean wasUncontended) {
        int h;
        if ((h = ThreadLocalRandom.getProbe()) == 0) {
            ThreadLocalRandom.localInit();      // force initialization
            h = ThreadLocalRandom.getProbe();
            wasUncontended = true;
        }
        boolean collide = false;                // True if last slot nonempty
        for (;;) {
            CounterCell[] as; CounterCell a; int n; long v;
            if ((as = counterCells) != null &amp;&amp; (n = as.length) > 0) {
                if ((a = as[(n - 1) &amp; h]) == null) {
                    if (cellsBusy == 0) {            // Try to attach new Cell
                        CounterCell r = new CounterCell(x); // Optimistic create
                        if (cellsBusy == 0 &amp;&amp;
                                U.compareAndSwapInt(this,CELLSBUSY,1)) {
                            boolean created = false;
                            try {               // Recheck under lock
                                CounterCell[] rs; int m,j;
                                if ((rs = counterCells) != null &amp;&amp;
                                        (m = rs.length) > 0 &amp;&amp;
                                        rs[j = (m - 1) &amp; h] == null) {
                                    rs[j] = r;
                                    created = true;
                                }
                            } finally {
                                cellsBusy = 0;
                            }
                            if (created)
                                break;
                            continue;           // Slot is <a href="https://www.jb51.cc/tag/Now/" target="_blank">Now</a> non-empty
                        }
                    }
                    collide = false;
                }
                else if (!wasUncontended)       // CAS already k<a href="https://www.jb51.cc/tag/Now/" target="_blank">Now</a>n to fail
                    wasUncontended = true;      // Continue after rehash
                else if (U.compareAndSwapLong(a,v + x))
                    break;
                else if (counterCells != as || n >= N<a href="https://www.jb51.cc/tag/cpu/" target="_blank">cpu</a>)
                    collide = false;            // At max size or stale
                else if (!collide)
                    collide = true;
                else if (cellsBusy == 0 &amp;&amp;
                        U.compareAndSwapInt(this,1)) {
                    try {
                        if (counterCells == as) {// Expand table unless stale
                            CounterCell[] rs = new CounterCell[n << 1];
                            for (int i = 0; i < n; ++i)
                                rs[i] = as[i];
                            counterCells = rs;
                        }
                    } finally {
                        cellsBusy = 0;
                    }
                    collide = false;
                    continue;                   // Retry with expanded table
                }
                h = ThreadLocalRandom.advanceProbe(h);
            }
            else if (cellsBusy == 0 &amp;&amp; counterCells == as &amp;&amp;
                    U.compareAndSwapInt(this,1)) {
                boolean init = false;
                try {                           // Initialize table
                    if (counterCells == as) {
                        CounterCell[] rs = new CounterCell[2];
                        rs[h &amp; 1] = new CounterCell(x);
                        counterCells = rs;
                        init = true;
                    }
                } finally {
                    cellsBusy = 0;
                }
                if (init)
                    break;
            }
            else if (U.compareAndSwapLong(this,v = baseCount,v + x))
                break;                          // Fall back on using base
        }
    }

    /* ---------------- TreeBins 转换相关-------------- */

    //在指定索引处替换掉所有的链表节点为红黑树节点;当然如果此时table特别小,则不执行转换操作,而应执行resize操作.
    private final void treeifyBin(Node<K,int index) {
        Node<K,V> b; int n,sc;
        if (tab != null) {
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                tryPresize(n << 1);
            else if ((b = tabAt(tab,index)) != null &amp;&amp; b.hash >= 0) {
                synchronized (b) {
                    if (tabAt(tab,index) == b) {
                        TreeNode<K,tl = null;
                        for (Node<K,V> e = b; e != null; e = e.next) {
                            TreeNode<K,V> p =
                                    new TreeNode<K,V>(e.hash,null);
                            if ((p.prev = tl) == null)
                                hd = p;
                            else
                                tl.next = p;
                            tl = p;
                        }
                        //TreeBin封装了TreeNode节点,将索引index处节点设置为新的TreeBin节点
                        setTabAt(tab,index,V>(hd));
                    }
                }
            }
        }
    }

    //将给定list中红黑树节点全部替换为链表节点,并返回链表
    static <K,V> untreeify(Node<K,V> b) {
        Node<K,tl = null;
        for (Node<K,V> q = b; q != null; q = q.next) {
            Node<K,V> p = new Node<K,V>(q.hash,null);
            if (tl == null)
                hd = p;
            else
                tl.next = p;
            tl = p;
        }
        return hd;
    }

    /* ---------------- TreeNodes -------------- */

    /**
     * Nodes for use in TreeBins
     * 也是<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>核心的数据结构.
     * 当链表长度过长的时候,会转换为TreeNode。但是与HashMap不相同的是,它并不是直接转换为红黑树,
     * 而是把这些结点包装成TreeNode放在TreeBin对象中,由TreeBin完成对红黑树的包装。
     * 而且TreeNode在ConcurrentHashMap集成自Node类,而并非HashMap中的集成自LinkedHashMap.Entry<K,V>类,
     * 也就是说TreeNode带有next指针,这样做的目的是方便基于TreeBin的访问。
     */
    static final class TreeNode<K,V> {
        //用于红黑树节点连接,因为本身是<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>链表,所以需要<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>指针指向双亲节点
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        //前驱节点指针,用于<a href="https://www.jb51.cc/tag/shanchu/" target="_blank">删除</a>节点
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;

        TreeNode(int hash,V> next,TreeNode<K,V> parent) {
            super(hash,next);
            this.parent = parent;
        }

        Node<K,Object k) {
            return findTreeNode(h,null);
        }

        /**
         * 从给定根节点出发,查找指定key的树节点.
         * 红黑树节点排序规则:按照节点的hash值排序
         * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m h 查找节点hash值
         * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m k 查找节点key
         * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m kc
         *
         */
        final TreeNode<K,V> findTreeNode(int h,Class<?> kc) {
            //指定key不为null
            if (k != null) {
                TreeNode<K,V> p = this;
                do  {
                    int ph,dir; K pk; TreeNode<K,V> q;
                    TreeNode<K,V> pl = p.left,pr = p.right;
                    //查找节点hash值比当前节点p的hash值小,则转向p的左孩子进行遍历,可见 红黑树按照节点的hash值排序
                    if ((ph = p.hash) > h)
                        p = pl;
                    //转右孩子
                    else if (ph < h)
                        p = pr;
                    //查找节点和当前p节点hash值和key都一样,则查找成功,返回查找节点
                    else if ((pk = p.key) == k || (pk != null &amp;&amp; k.equals(pk)))
                        return p;
                    else if (pl == null)
                        p = pr;
                    else if (pr == null)
                        p = pl;
                    else if ((kc != null ||
                            (kc = comp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>bleClassFor(k)) != null) &amp;&amp;
                            (dir = compareComp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>bles(kc,pk)) != 0)
                        p = (dir < 0) ? pl : pr;
                    //递归查找
                    else if ((q = pr.findTreeNode(h,kc)) != null)
                        return q;
                    else
                        p = pl;
                } while (p != null);
            }
            return null;
        }
    }

    /* ---------------- TreeBins -------------- */

    /**
     * TreeNodes用作bin的头节点.在实际的ConcurrentHashMap“数组”中,存放的是TreeBin对象,而不是TreeNode对象,这是与HashMap的区别。
     * TreeBins不保存key和value,而是指向TreeNodes链表及其根节点.
     * TreeBin还维持<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>读写锁,从而保证在红黑树重构前,优先完成读操作,然后再执行写操作.
     */
    static final class TreeBin<K,V> {
        //<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>TreeBin既要有指向根节点的指针,也要有指向第<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>节点指针
        TreeNode<K,V> root;//根节点
        volatile TreeNode<K,V> f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t;//第<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>节点
        volatile Thread waiter;//等待线程
        volatile int lockState;//锁状态

        //lockState的一些值
        static final int WRITER = 1; // 持有写锁的锁状态值
        static final int WAITER = 2; // 等待写锁的锁状态值
        static final int READER = 4; // 设置读锁时的锁状态增量值

        /**
         * 插入节点时,如果hash值相同而又没有其它可比较的元素时,此<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>可用于打破此种插入僵局.
         * 我们不需要<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>全局有序,只需要<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>插入规则,保证在调整平衡时可以维持等价关系.
         * 僵局关系的进一步打破也使得测试变得简单了一些.
         * 和hashmap<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>一样
         */
        static int tieBreakOrder(Object a,Object b) {
            int d;
            //如果a为null,或者b为null,或者a和b是同<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>类的实
            if (a == null || b == null ||
                    (d = a.getClass().getName().
                            compar<a href="https://www.jb51.cc/tag/eto/" target="_blank">eto</a>(b.getClass().getName())) == 0)//反射<a href="https://www.jb51.cc/tag/huoqu/" target="_blank">获取</a>类名
            //identityHashCode():无论给定对象的类是否覆盖hashCode(),都会返回给定对象的哈希码,与<a href="https://www.jb51.cc/tag/mo/" target="_blank">默</a>认<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>hashCode()返回的哈希码相同。
            //如果传入参数a为null,则返回值为0;
                d = (Sy<a href="https://www.jb51.cc/tag/stem/" target="_blank">stem</a>.identityHashCode(a) <= Sy<a href="https://www.jb51.cc/tag/stem/" target="_blank">stem</a>.identityHashCode(b) ?
                        -1 : 1);
            return d;
        }

        //利用头节点为b的初始set节点集合,创建<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>bin,里面放了一棵红黑树
        TreeBin(TreeNode<K,V> b) {
            //这就它的构造<a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>,TREEBIN=-1,树根节点的hash值
            super(TREEBIN,null);

            this.f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t = b;
            TreeNode<K,V> r = null;
            for (TreeNode<K,V> x = b,next; x != null; x = next) {
                next = (TreeNode<K,V>)x.next;
                x.left = x.right = null;
                if (r == null) {
                    x.parent = null;
                    x.red = false;
                    r = x;
                }
                else {
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    for (TreeNode<K,V> p = r;;) {
                        int dir,ph;
                        K pk = p.key;
                        if ((ph = p.hash) > h)
                            dir = -1;
                        else if (ph < h)
                            dir = 1;
                        else if ((kc == null &amp;&amp;
                                (kc = comp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>bleClassFor(k)) == null) ||
                                (dir = compareComp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>bles(kc,pk)) == 0)
                            dir = tieBreakOrder(k,pk);
                        TreeNode<K,V> xp = p;
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            x.parent = xp;
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;
                            r = balanceInsertion(r,x);
                            break;
                        }
                    }
                }
            }
            this.root = r;
            assert checkInvariants(root);
        }

        //红黑树重构开始前,<a href="https://www.jb51.cc/tag/huoqu/" target="_blank">获取</a>写锁
        private final void lockRoot() {
            if (!U.compareAndSwapInt(this,LOCKSTATE,WRITER))
                contendedLock(); // offload to sep<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>te method
        }

        //红黑树重构完成后,释放写锁
        private final void unlockRoot() {
            lockState = 0;
        }

        //root被锁定时,阻塞其他请求.
        private final void contendedLock() {
            boolean waiting = false;
            for (int s;;) {
                if (((s = lockState) &amp; ~WAITER) == 0) {
                    if (U.compareAndSwapInt(this,s,WRITER)) {
                        if (waiting)
                            waiter = null;
                        return;
                    }
                }
                else if ((s &amp; WAITER) == 0) {
                    if (U.compareAndSwapInt(this,s | WAITER)) {
                        waiting = true;
                        waiter = Thread.currentThread();
                    }
                }
                else if (waiting)
                    LockSupport.park(this);
            }
        }

        //根据给定hash值和key查找树节点.
        //首先尝试从树根节点开始查找
        //如果<a href="https://www.jb51.cc/tag/huoqu/" target="_blank">获取</a>不到bin的锁,则<a href="https://www.jb51.cc/tag/chaxun/" target="_blank">查询</a>需要线性时间:o(n),也就是从头到位底链表进行了遍历
        //所以TreeBin的查找节点过程:时间复杂度为o(logN)或为o(N)
        final Node<K,Object k) {
            if (k != null) {
                for (Node<K,V> e = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t; e != null; ) {
                    int s; K ek;
                    if (((s = lockState) &amp; (WAITER|WRITER)) != 0) {
                        if (e.hash == h &amp;&amp;
                                ((ek = e.key) == k || (ek != null &amp;&amp; k.equals(ek))))
                            return e;
                        e = e.next;
                    }
                    else if (U.compareAndSwapInt(this,s + READER)) {
                        TreeNode<K,p;
                        try {
                            p = ((r = root) == null ? null :
                                    r.findTreeNode(h,null));
                        } finally {
                            Thread w;
                            if (U.getAndAddInt(this,-READER) ==
                                    (READER|WAITER) &amp;&amp; (w = waiter) != null)
                                LockSupport.unpark(w);
                        }
                        return p;
                    }
                }
            }
            return null;
        }


        //<a href="https://www.jb51.cc/tag/tianjia/" target="_blank">添加</a><a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>树节点
        final TreeNode<K,V> putTreeVal(int h,K k,V v) {
            Class<?> kc = null;
            boolean searched = false;
            for (TreeNode<K,V> p = root;;) {
                int dir,ph; K pk;
                if (p == null) {
                    f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t = root = new TreeNode<K,null);
                    break;
                }
                else if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((pk = p.key) == k || (pk != null &amp;&amp; k.equals(pk)))
                    return p;
                else if ((kc == null &amp;&amp;
                        (kc = comp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>bleClassFor(k)) == null) ||
                        (dir = compareComp<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>bles(kc,pk)) == 0) {
                    if (!searched) {
                        TreeNode<K,V> q,ch;
                        searched = true;
                        if (((ch = p.left) != null &amp;&amp;
                                (q = ch.findTreeNode(h,kc)) != null) ||
                                ((ch = p.right) != null &amp;&amp;
                                        (q = ch.findTreeNode(h,kc)) != null))
                            return q;
                    }
                    dir = tieBreakOrder(k,pk);
                }

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    TreeNode<K,V> x,f = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t;
                    f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t = x = new TreeNode<K,xp);
                    if (f != null)
                        f.prev = x;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    if (!xp.red)
                        x.red = true;
                    else {
                        lockRoot();
                        try {
                            root = balanceInsertion(root,x);
                        } finally {
                            unlockRoot();
                        }
                    }
                    break;
                }
            }
            assert checkInvariants(root);
            return null;
        }

        /**
         * 移除<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>树节点.在此<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>被<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank">调用</a>前此节点必须存在.
         * 这比典型的红黑<a href="https://www.jb51.cc/tag/shanchu/" target="_blank">删除</a><a href="https://www.jb51.cc/tag/daima/" target="_blank">代码</a>更混乱,因为我们不能交换内部节点和其后继叶子节点的<a href="https://www.jb51.cc/tag/neirong/" target="_blank">内容</a>。
         * 所以,取而代之的是交换树<a href="https://www.jb51.cc/tag/lianjie/" target="_blank">链接</a>。
         * @return 返回值为true,代表<a href="https://www.jb51.cc/tag/shanchu/" target="_blank">删除</a>节点后,bin内节点太少,需要将红黑树转为链表.
         */
        final boolean removeTreeNode(TreeNode<K,V> p) {
            TreeNode<K,V> next = (TreeNode<K,V>)p.next;
            TreeNode<K,V> pred = p.prev;  // unlink traversal pointers
            TreeNode<K,rl;
            if (pred == null)
                f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t = next;
            else
                pred.next = next;
            if (next != null)
                next.prev = pred;
            if (f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t == null) {
                root = null;
                return true;
            }
            if ((r = root) == null || r.right == null || // too small
                    (rl = r.left) == null || rl.left == null)
                return true;
            lockRoot();
            try {
                TreeNode<K,V> replacement;
                TreeNode<K,V> pl = p.left;
                TreeNode<K,V> pr = p.right;
                if (pl != null &amp;&amp; pr != null) {
                    TreeNode<K,V> s = pr,sl;
                    while ((sl = s.left) != null) // find successor
                        s = sl;
                    boolean c = s.red; s.red = p.red; p.red = c; // swap colors
                    TreeNode<K,V> sr = s.right;
                    TreeNode<K,V> pp = p.parent;
                    if (s == pr) { // p was s's direct parent
                        p.parent = s;
                        s.right = p;
                    }
                    else {
                        TreeNode<K,V> sp = s.parent;
                        if ((p.parent = sp) != null) {
                            if (s == sp.left)
                                sp.left = p;
                            else
                                sp.right = p;
                        }
                        if ((s.right = pr) != null)
                            pr.parent = s;
                    }
                    p.left = null;
                    if ((p.right = sr) != null)
                        sr.parent = p;
                    if ((s.left = pl) != null)
                        pl.parent = s;
                    if ((s.parent = pp) == null)
                        r = s;
                    else if (p == pp.left)
                        pp.left = s;
                    else
                        pp.right = s;
                    if (sr != null)
                        replacement = sr;
                    else
                        replacement = p;
                }
                else if (pl != null)
                    replacement = pl;
                else if (pr != null)
                    replacement = pr;
                else
                    replacement = p;
                if (replacement != p) {
                    TreeNode<K,V> pp = replacement.parent = p.parent;
                    if (pp == null)
                        r = replacement;
                    else if (p == pp.left)
                        pp.left = replacement;
                    else
                        pp.right = replacement;
                    p.left = p.right = p.parent = null;
                }

                root = (p.red) ? r : balanceDeletion(r,replacement);

                if (p == replacement) {  // detach pointers
                    TreeNode<K,V> pp;
                    if ((pp = p.parent) != null) {
                        if (p == pp.left)
                            pp.left = null;
                        else if (p == pp.right)
                            pp.right = null;
                        p.parent = null;
                    }
                }
            } finally {
                unlockRoot();
            }
            assert checkInvariants(root);
            return false;
        }

        /* --------------------红黑树<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>,全部改自CLR算法---------------------------------------- */

        //左旋
        static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,pp,rl;
            if (p != null &amp;&amp; (r = p.right) != null) {
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                r.left = p;
                p.parent = r;
            }
            return root;
        }

        //右旋
        static <K,V> rotateRight(TreeNode<K,V> l,lr;
            if (p != null &amp;&amp; (l = p.left) != null) {
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                l.right = p;
                p.parent = l;
            }
            return root;
        }

        //插入后,调整平衡和颜色
        static <K,V> balanceInsertion(TreeNode<K,V> x) {
            x.red = true;
            for (TreeNode<K,V> xp,xpp,xppl,xppr;;) {
                if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                else if (!xp.red || (xpp = xp.parent) == null)
                    return root;
                if (xp == (xppl = xpp.left)) {
                    if ((xppr = xpp.right) != null &amp;&amp; xppr.red) {
                        xppr.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.right) {
                            root = rotateLeft(root,x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateRight(root,xpp);
                            }
                        }
                    }
                }
                else {
                    if (xppl != null &amp;&amp; xppl.red) {
                        xppl.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.left) {
                            root = rotateRight(root,x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateLeft(root,xpp);
                            }
                        }
                    }
                }
            }
        }

        //<a href="https://www.jb51.cc/tag/shanchu/" target="_blank">删除</a>后调整平衡和颜色
        static <K,V> balanceDeletion(TreeNode<K,V> x) {
            for (TreeNode<K,xpl,xpr;;)  {
                if (x == null || x == root)
                    return root;
                else if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                else if (x.red) {
                    x.red = false;
                    return root;
                }
                else if ((xpl = xp.left) == x) {
                    if ((xpr = xp.right) != null &amp;&amp; xpr.red) {
                        xpr.red = false;
                        xp.red = true;
                        root = rotateLeft(root,xp);
                        xpr = (xp = x.parent) == null ? null : xp.right;
                    }
                    if (xpr == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpr.left,sr = xpr.right;
                        if ((sr == null || !sr.red) &amp;&amp;
                                (sl == null || !sl.red)) {
                            xpr.red = true;
                            x = xp;
                        }
                        else {
                            if (sr == null || !sr.red) {
                                if (sl != null)
                                    sl.red = false;
                                xpr.red = true;
                                root = rotateRight(root,xpr);
                                xpr = (xp = x.parent) == null ?
                                        null : xp.right;
                            }
                            if (xpr != null) {
                                xpr.red = (xp == null) ? false : xp.red;
                                if ((sr = xpr.right) != null)
                                    sr.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateLeft(root,xp);
                            }
                            x = root;
                        }
                    }
                }
                else { // symmetric
                    if (xpl != null &amp;&amp; xpl.red) {
                        xpl.red = false;
                        xp.red = true;
                        root = rotateRight(root,xp);
                        xpl = (xp = x.parent) == null ? null : xp.left;
                    }
                    if (xpl == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpl.left,sr = xpl.right;
                        if ((sl == null || !sl.red) &amp;&amp;
                                (sr == null || !sr.red)) {
                            xpl.red = true;
                            x = xp;
                        }
                        else {
                            if (sl == null || !sl.red) {
                                if (sr != null)
                                    sr.red = false;
                                xpl.red = true;
                                root = rotateLeft(root,xpl);
                                xpl = (xp = x.parent) == null ?
                                        null : xp.left;
                            }
                            if (xpl != null) {
                                xpl.red = (xp == null) ? false : xp.red;
                                if ((sl = xpl.left) != null)
                                    sl.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateRight(root,xp);
                            }
                            x = root;
                        }
                    }
                }
            }
        }

        //递归不变检查,用于检查整个红黑树连接上是否有<a href="https://www.jb51.cc/tag/cuowu/" target="_blank">错误</a>
        static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
            //tp双亲,tl左孩子,tr右孩子,tb前驱,tn后继
            TreeNode<K,V> tp = t.parent,tl = t.left,tr = t.right,tb = t.prev,tn = (TreeNode<K,V>)t.next;
            //双亲不为null,前驱的后继不是当前节点t,故连接<a href="https://www.jb51.cc/tag/cuowu/" target="_blank">错误</a>,返回false
            if (tb != null &amp;&amp; tb.next != t)
                return false;
            //后继不为null,后继的前驱不为当前节点t,故<a href="https://www.jb51.cc/tag/lianjie/" target="_blank">链接</a><a href="https://www.jb51.cc/tag/cuowu/" target="_blank">错误</a>,返回false
            if (tn != null &amp;&amp; tn.prev != t)
                return false;
            if (tp != null &amp;&amp; t != tp.left &amp;&amp; t != tp.right)
                return false;
            if (tl != null &amp;&amp; (tl.parent != t || tl.hash > t.hash))
                return false;
            if (tr != null &amp;&amp; (tr.parent != t || tr.hash < t.hash))
                return false;
            if (t.red &amp;&amp; tl != null &amp;&amp; tl.red &amp;&amp; tr != null &amp;&amp; tr.red)
                return false;
            if (tl != null &amp;&amp; !checkInvariants(tl))
                return false;
            if (tr != null &amp;&amp; !checkInvariants(tr))
                return false;
            return true;
        }

        private static final sun.misc.Unsafe U;
        private static final long LOCKSTATE;
        static {
            try {
                U = sun.misc.Unsafe.getUnsafe();
                Class<?> k = TreeBin.class;
                LOCKSTATE = U.objectFieldOffset
                        (k.getDeclaredField("lockState"));//反射<a href="https://www.jb51.cc/tag/huoquziduan/" target="_blank">获取字段</a>值
            } catch (Exception e) {
                throw new Error(e);
            }
        }
    }

    /* ----------------Table 遍历 -------------- */

    //在继续使用当前table前,必须记录转发表的区域的表,其长度和当前遍历索引。
    static final class TableStack<K,V> {
        int length;
        int index;
        Node<K,V>[] tab;
        TableStack<K,V> next;
    }

    /**
     * 对诸如containsValue之类的<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>要进行封装遍历.alsoserves是其他迭代器和分割器的基类.
     * 遍历过程中,可能出现resize,为了面对可能的持续调整,需要记录大量的状态,因此很难通过volatile进行优化,* 即便如此,遍历仍然保持合理的吞吐量。通常情况下,迭代逐个进行遍历列表。但是,如果表已经调整大小,那么所有未来的步骤
     * 必须遍历当前索引处的bin以及(index + baseSize).
     * 为了处理<a href="https://www.jb51.cc/tag/yonghu/" target="_blank">用户</a>间跨线程共享迭代器之<a href="https://www.jb51.cc/tag/jiande/" target="_blank">间的</a>冲突,如果迭代器索引边界失效,则迭代停止.
     */

    static class Traverser<K,V> {
        Node<K,V>[] tab;        // current table; updated if resized
        Node<K,V> next;         // the next entry to use
        TableStack<K,V> stack,spare; // to save/restore on ForwardingNodes
        int index;              // index of bin to use next
        int baseIndex;          // current index of initial table
        int baseLimit;          // index bound for initial table
        final int baseSize;     // initial table size

        Traverser(Node<K,int size,int index,int limit) {
            this.tab = tab;
            this.baseSize = size;
            this.baseIndex = this.index = index;
            this.baseLimit = limit;
            this.next = null;
        }

        //继续遍历,返回下<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>有效节点,如果没有则返回null
        final Node<K,V> advance() {
            Node<K,V> e;
            if ((e = next) != null)
                e = e.next;
            for (;;) {
                Node<K,V>[] t; int i,n;  // must use locals in checks
                if (e != null)
                    return next = e;
                if (baseIndex >= baseLimit || (t = tab) == null ||
                        (n = t.length) <= (i = index) || i < 0)
                    return next = null;
                if ((e = tabAt(t,i)) != null &amp;&amp; e.hash < 0) {
                    if (e instanceof ForwardingNode) {
                        tab = ((ForwardingNode<K,V>)e).nextTable;
                        e = null;
                        pushState(t,n);
                        continue;
                    }
                    else if (e instanceof TreeBin)
                        e = ((TreeBin<K,V>)e).f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t;
                    else
                        e = null;
                }
                if (stack != null)
                    recoverState(n);
                else if ((index = i + baseSize) >= n)
                    index = ++baseIndex; // visit upper slots if present
            }
        }

        //遇到转发节点时,保存遍历状态
        private void pushState(Node<K,V>[] t,int n) {
            TableStack<K,V> s = spare;  // reuse if possible
            if (s != null)
                spare = s.next;
            else
                s = new TableStack<K,V>();
            s.tab = t;
            s.length = n;
            s.index = i;
            s.next = stack;
            stack = s;
        }

        //取出遍历状态栈的栈定元素.
        private void recoverState(int n) {
            TableStack<K,V> s; int len;
            while ((s = stack) != null &amp;&amp; (index += (len = s.length)) >= n) {
                n = len;
                index = s.index;
                tab = s.tab;
                s.tab = null;
                TableStack<K,V> next = s.next;
                s.next = spare; // save for reuse
                stack = next;
                spare = s;
            }
            if (s == null &amp;&amp; (index += baseSize) >= n)
                index = ++baseIndex;
        }
    }

    //基于key,entry的迭代器.在Traverser基础上<a href="https://www.jb51.cc/tag/tianjia/" target="_blank">添加</a>了一些变量以<a href="https://www.jb51.cc/tag/zhichi/" target="_blank">支持</a>i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor.remove<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>
    static class BaseI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,V> extends Traverser<K,V> {
        final ConcurrentHashMap<K,V> map;
        Node<K,V> lastReturned;
        BaseI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor(Node<K,int limit,ConcurrentHashMap<K,V> map) {
            super(tab,size,limit);
            this.map = map;
            advance();
        }

        public final boolean hasNext() { return next != null; }
        public final boolean hasMoreElements() { return next != null; }

        public final void remove() {
            Node<K,V> p;
            if ((p = lastReturned) == null)
                throw new Ille<a href="https://www.jb51.cc/tag/gal/" target="_blank">gal</a>StateException();
            lastReturned = null;
            map.replaceNode(p.key,null);
        }
    }

    //key迭代器
    static final class KeyI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,V> extends BaseI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,V>
            implements I<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K>,Enumeration<K> {
        KeyI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor(Node<K,limit,map);
        }

        public final K next() {
            Node<K,V> p;
            if ((p = next) == null)
                throw new NoSuchElementException();
            K k = p.key;
            lastReturned = p;
            advance();
            return k;
        }

        public final K nextElement() { return next(); }
    }

    //value迭代器
    static final class ValueI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,V>
            implements I<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<V>,Enumeration<V> {
        ValueI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor(Node<K,map);
        }

        public final V next() {
            Node<K,V> p;
            if ((p = next) == null)
                throw new NoSuchElementException();
            V v = p.val;
            lastReturned = p;
            advance();
            return v;
        }

        public final V nextElement() { return next(); }
    }

    //Entry迭代器
    static final class EntryI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,V>
            implements I<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<Map.Entry<K,V>> {
        EntryI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor(Node<K,map);
        }

        public final Map.Entry<K,V> next() {
            Node<K,V> p;
            if ((p = next) == null)
                throw new NoSuchElementException();
            K k = p.key;
            V v = p.val;
            lastReturned = p;
            advance();
            return new MapEntry<K,V>(k,map);
        }
    }

    //从EntryI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor导出<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>Entry
    static final class MapEntry<K,V> {
        final K key; // non-null
        V val;       // non-null
        final ConcurrentHashMap<K,V> map;
        MapEntry(K key,V> map) {
            this.key = key;
            this.val = val;
            this.map = map;
        }
        public K getKey()        { return key; }
        public V getValue()      { return val; }
        public int hashCode()    { return key.hashCode() ^ val.hashCode(); }
        public String toString() { return key + "=" + val; }

        public boolean equals(Object o) {
            Object k,v; Map.Entry<?,?>)o).getKey()) != null &amp;&amp;
                    (v = e.getValue()) != null &amp;&amp;
                    (k == key || k.equals(key)) &amp;&amp;
                    (v == val || v.equals(val)));
        }

        /**
         * 设置我们的entry的value并写入map。
         * 注意:返回的值<a href="https://www.jb51.cc/tag/zaizheli/" target="_blank">在这里</a>有点随便。因为可能返回的值已经被其它线程做过更改了,而返回值并未<a href="https://www.jb51.cc/tag/huoqu/" target="_blank">获取</a>到最新的值.
         */
        public V setValue(V value) {
            if (value == null) throw new NullPointerException();
            V v = val;
            val = value;
            map.put(key,value);
            return v;
        }
    }

    //key分割器
    static final class KeySpli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,V>
            implements Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K> {
        long est;               // size estimate
        KeySpli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor(Node<K,long est) {
            super(tab,limit);
            this.est = est;
        }

        public Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K> trySplit() {
            int i,h;
            return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
                    new KeySpli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,V>(tab,baseSize,baseLimit = h,est >>>= 1);
        }

        public void forEachRemaining(Consumer<? super K> action) {
            if (action == null) throw new NullPointerException();
            for (Node<K,V> p; (p = advance()) != null;)
                action.accept(p.key);
        }

        public boolean tryAdvance(Consumer<? super K> action) {
            if (action == null) throw new NullPointerException();
            Node<K,V> p;
            if ((p = advance()) == null)
                return false;
            action.accept(p.key);
            return true;
        }

        public long estimateSize() { return est; }

        public int <a href="https://www.jb51.cc/tag/characteristics/" target="_blank">characteristics</a>() {
            return Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor.<a href="https://www.jb51.cc/tag/dis/" target="_blank">dis</a>TINCT | Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor.CONCURRENT |
                    Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor.NONNULL;
        }
    }

    //value分割器
    static final class ValueSpli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,V>
            implements Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<V> {
        long est;               // size estimate
        ValueSpli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor(Node<K,limit);
            this.est = est;
        }

        public Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<V> trySplit() {
            int i,h;
            return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
                    new ValueSpli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,est >>>= 1);
        }

        public void forEachRemaining(Consumer<? super V> action) {
            if (action == null) throw new NullPointerException();
            for (Node<K,V> p; (p = advance()) != null;)
                action.accept(p.val);
        }

        public boolean tryAdvance(Consumer<? super V> action) {
            if (action == null) throw new NullPointerException();
            Node<K,V> p;
            if ((p = advance()) == null)
                return false;
            action.accept(p.val);
            return true;
        }

        public long estimateSize() { return est; }

        public int <a href="https://www.jb51.cc/tag/characteristics/" target="_blank">characteristics</a>() {
            return Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor.CONCURRENT | Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor.NONNULL;
        }
    }

    //entry分割器
    static final class EntrySpli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,V>
            implements Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<Map.Entry<K,V>> {
        final ConcurrentHashMap<K,V> map; // To export MapEntry
        long est;               // size estimate
        EntrySpli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor(Node<K,long est,limit);
            this.map = map;
            this.est = est;
        }

        public Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<Map.Entry<K,V>> trySplit() {
            int i,h;
            return (h = ((i = baseIndex) + (f = baseLimit)) >>> 1) <= i ? null :
                    new EntrySpli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,est >>>= 1,map);
        }

        public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
            if (action == null) throw new NullPointerException();
            for (Node<K,V> p; (p = advance()) != null; )
                action.accept(new MapEntry<K,V>(p.key,p.val,map));
        }

        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
            if (action == null) throw new NullPointerException();
            Node<K,V> p;
            if ((p = advance()) == null)
                return false;
            action.accept(new MapEntry<K,map));
            return true;
        }

        public long estimateSize() { return est; }

        public int <a href="https://www.jb51.cc/tag/characteristics/" target="_blank">characteristics</a>() {
            return Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor.<a href="https://www.jb51.cc/tag/dis/" target="_blank">dis</a>TINCT | Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor.CONCURRENT |
                    Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor.NONNULL;
        }
    }

    /*---------并行批量操作 P<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llel bulk operations---------*/

    /**
     * 计算批量任务的初始批次值。
     * 在执行最终的操作之前,返回值将是将任务一分为二的<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>指数值exp2.我的理解是,如果返回为3,则是将任务分为8部分,并行处理.
     * 此值计算速度很快,适合用作二划分
     */

    final int batchFor(long b) {
        long n;
        if (b == Long.MAX_VALUE || (n = sumCount()) <= 1L || n < b)
            return 0;
        int sp = ForkJoinPool.getCommonPoolP<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelism() << 2; // slack of 4
        return (b <= 0L || (n /= b) >= sp) ? sp : (int)n;
    }


    //@since 1.8
    public void forEach(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,BiConsumer<? super K,? super V> action) {
        if (action == null) throw new NullPointerException();
        new ForEachMappingTask<K,V>
                (null,batchFor(p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold),table,action).invoke();
    }

    //@since 1.8
    public <U> void forEach(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,? extends U> transformer,Consumer<? super U> action) {
        if (transformer == null || action == null)
            throw new NullPointerException();
        new ForEachTransformedMappingTask<K,V,U>
                (null,transformer,action).invoke();
    }

    /**
     * 对每个(key,value)应用给定的<a href="https://www.jb51.cc/tag/sousuo/" target="_blank">搜索</a><a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>并返回<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>非空结果,如果没有,则返回null。
     * 成功后,进一步的元素处理将被抑制,<a href="https://www.jb51.cc/tag/sousuo/" target="_blank">搜索</a><a href="https://www.jb51.cc/tag/gongneng/" target="_blank">功能</a>的任何其他并行<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank">调用</a>的结果都将被忽略。
     * @since 1.8
     */
    public <U> U search(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,? extends U> searchFunction) {
        if (searchFunction == null) throw new NullPointerException();
        return new SearchMappingsTask<K,searchFunction,new <a href="https://www.jb51.cc/tag/atomicreference/" target="_blank">atomicreference</a><U>()).invoke();
    }

    //since 1.8,合并结果值
    public <U> U reduce(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,BiFunction<? super U,? super U,? extends U> reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceMappingsTask<K,reducer).invoke();
    }

    /**
     * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m basis reduction操作的<a href="https://www.jb51.cc/tag/mo/" target="_blank">默</a>认初始化值
     * @since 1.8
     */
    public double reduc<a href="https://www.jb51.cc/tag/eto/" target="_blank">eto</a>Double(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,T<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleBiFunction<? super K,? super V> transformer,double basis,DoubleBinaryOperator reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceMappingsT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,basis,reducer).invoke();
    }


    //@since 1.8
    public long reduc<a href="https://www.jb51.cc/tag/eto/" target="_blank">eto</a>Long(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,ToLongBiFunction<? super K,long basis,LongBinaryOperator reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceMappingsToLongTask<K,reducer).invoke();
    }

    // @since 1.8
    public int reduc<a href="https://www.jb51.cc/tag/eto/" target="_blank">eto</a>Int(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,ToIntBiFunction<? super K,int basis,IntBinaryOperator reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceMappingsToIntTask<K,reducer).invoke();
    }

    /**
     * Performs the given action for each key.
     * @since 1.8
     */
    public void forEachKey(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,Consumer<? super K> action) {
        if (action == null) throw new NullPointerException();
        new ForEachKeyTask<K,action).invoke();
    }

    /**
     * @since 1.8
     */
    public <U> void forEachKey(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,Consumer<? super U> action) {
        if (transformer == null || action == null)
            throw new NullPointerException();
        new ForEachTransformedKeyTask<K,action).invoke();
    }

    /**
     * 根据给定<a href="https://www.jb51.cc/tag/chaxun/" target="_blank">查询</a><a href="https://www.jb51.cc/tag/hanshu/" target="_blank">函数</a>,返回<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>非null结果.如果没有则返回null
     * 成功后,进一步的元素处理将被抑制,<a href="https://www.jb51.cc/tag/sousuo/" target="_blank">搜索</a><a href="https://www.jb51.cc/tag/gongneng/" target="_blank">功能</a>的任何其他并行<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank">调用</a>的结果都将被忽略。
     * @since 1.8
     */
    public <U> U searchKeys(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,? extends U> searchFunction) {
        if (searchFunction == null) throw new NullPointerException();
        return new SearchKeysTask<K,new <a href="https://www.jb51.cc/tag/atomicreference/" target="_blank">atomicreference</a><U>()).invoke();
    }

    /**
     * 所有key的<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>合并操作
     * @since 1.8
     */
    public K reduceKeys(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,? super K,? extends K> reducer) {
        if (reducer == null) throw new NullPointerException();
        return new ReduceKeysTask<K,reducer).invoke();
    }

    /**
     * 对key的reduce操作
     * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold 并行被处理的元素的个数阈值
     * @since 1.8
     */
    public <U> U reduceKeys(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,? extends U> reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceKeysTask<K,reducer).invoke();
    }

    /**
     * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m basis reduction操作的初始化值
     * @since 1.8
     */
    public double reduceKeysT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>uble(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,T<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleFunction<? super K> transformer,DoubleBinaryOperator reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceKeysT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,reducer).invoke();
    }

    /**
     * @since 1.8
     */
    public long reduceKeysToLong(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,ToLongFunction<? super K> transformer,LongBinaryOperator reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceKeysToLongTask<K,reducer).invoke();
    }

    /**
     * @since 1.8
     */
    public int reduceKeysToInt(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,ToIntFunction<? super K> transformer,IntBinaryOperator reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceKeysToIntTask<K,reducer).invoke();
    }

    /**
     * @since 1.8
     */
    public void forEachValue(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,Consumer<? super V> action) {
        if (action == null)
            throw new NullPointerException();
        new ForEachValueTask<K,action).invoke();
    }

    /**
     * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold 并行被处理的元素的个数阈值
     * @since 1.8
     */
    public <U> void forEachValue(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,Function<? super V,Consumer<? super U> action) {
        if (transformer == null || action == null)
            throw new NullPointerException();
        new ForEachTransformedValueTask<K,action).invoke();
    }

    /**
     * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold 并行被处理的元素的个数阈值
     * @since 1.8
     */
    public <U> U searchValues(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,? extends U> searchFunction) {
        if (searchFunction == null) throw new NullPointerException();
        return new SearchValuesTask<K,new <a href="https://www.jb51.cc/tag/atomicreference/" target="_blank">atomicreference</a><U>()).invoke();
    }

    /**
     *
     * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold t并行被处理的元素的个数阈值
     * @since 1.8
     */
    public V reduceValues(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,? extends V> reducer) {
        if (reducer == null) throw new NullPointerException();
        return new ReduceValuesTask<K,reducer).invoke();
    }

    /**
     * @since 1.8
     */
    public <U> U reduceValues(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,? extends U> reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceValuesTask<K,reducer).invoke();
    }

    /**
     * @since 1.8
     */
    public double reduceValuesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>uble(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,T<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleFunction<? super V> transformer,DoubleBinaryOperator reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceValuesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,reducer).invoke();
    }

    /**
     * @since 1.8
     */
    public long reduceValuesToLong(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,ToLongFunction<? super V> transformer,LongBinaryOperator reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceValuesToLongTask<K,reducer).invoke();
    }

    /**
     * @since 1.8
     */
    public int reduceValuesToInt(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,ToIntFunction<? super V> transformer,IntBinaryOperator reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceValuesToIntTask<K,reducer).invoke();
    }

    /**
     * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold 并行被处理的元素的个数阈值
     * @since 1.8
     */
    public void forEachEntry(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,Consumer<? super Map.Entry<K,V>> action) {
        if (action == null) throw new NullPointerException();
        new ForEachEntryTask<K,V>(null,action).invoke();
    }

    /**
     * @since 1.8
     */
    public <U> void forEachEntry(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,Function<Map.Entry<K,Consumer<? super U> action) {
        if (transformer == null || action == null)
            throw new NullPointerException();
        new ForEachTransformedEntryTask<K,action).invoke();
    }

    /**
     * @since 1.8
     */
    public <U> U searchEntries(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,? extends U> searchFunction) {
        if (searchFunction == null) throw new NullPointerException();
        return new SearchEntriesTask<K,new <a href="https://www.jb51.cc/tag/atomicreference/" target="_blank">atomicreference</a><U>()).invoke();
    }

    /**
     * @since 1.8
     */
    public Map.Entry<K,V> reduceEntries(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,BiFunction<Map.Entry<K,Map.Entry<K,? extends Map.Entry<K,V>> reducer) {
        if (reducer == null) throw new NullPointerException();
        return new ReduceEntriesTask<K,reducer).invoke();
    }

    /**
     * @since 1.8
     */
    public <U> U reduceEntries(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,? extends U> reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceEntriesTask<K,reducer).invoke();
    }

    /**
     * @since 1.8
     */
    public double reduceEntriesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>uble(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,T<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleFunction<Map.Entry<K,V>> transformer,DoubleBinaryOperator reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceEntriesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,reducer).invoke();
    }

    /**
     * @since 1.8
     */
    public long reduceEntriesToLong(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,ToLongFunction<Map.Entry<K,LongBinaryOperator reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceEntriesToLongTask<K,reducer).invoke();
    }

    /**
     * @since 1.8
     */
    public int reduceEntriesToInt(long p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>llelismThreshold,ToIntFunction<Map.Entry<K,IntBinaryOperator reducer) {
        if (transformer == null || reducer == null)
            throw new NullPointerException();
        return new MapReduceEntriesToIntTask<K,reducer).invoke();
    }


    /* ----------------视图操作 Views -------------- */

    /**
     * Base class for views.
     */
    abstract static class CollectionView<K,E>
            implements Collection<E>,java.io.Serializable {
        private static final long serialVersionUID = 7249069246763182397L;
        final ConcurrentHashMap<K,V> map;
        CollectionView(ConcurrentHashMap<K,V> map)  { this.map = map; }

        /**
         * Returns the map <a href="https://www.jb51.cc/tag/backing/" target="_blank">backing</a> this view.
         *
         * @return the map <a href="https://www.jb51.cc/tag/backing/" target="_blank">backing</a> this view
         */
        public ConcurrentHashMap<K,V> getMap() { return map; }

        /**
         * Removes all of the elements from this view,by removing all
         * the mappings from the map <a href="https://www.jb51.cc/tag/backing/" target="_blank">backing</a> this view.
         */
        public final void clear()      { map.clear(); }
        public final int size()        { return map.size(); }
        public final boolean isEmpty() { return map.isEmpty(); }

        // implementations below rely on concrete classes supplying these
        // abstract methods
        /**
         * Returns an i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor over the elements in this collection.
         *
         * <p>The returned i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor is
         * <a href="package-summary.html#Weakly"&gt;<i>weakly consistent</i></a>.
         *
         * @return an i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor over the elements in this collection
         */
        public abstract I<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<E> i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor();
        public abstract boolean contains(Object o);
        public abstract boolean remove(Object o);

        private static final String oomeMsg = "<a href="https://www.jb51.cc/tag/required/" target="_blank">required</a> array size too large";

        public final Object[] toArray() {
            long sz = map.mappingCount();
            if (sz > MAX_ARRAY_SIZE)
                throw new OutOfMemoryError(oomeMsg);
            int n = (int)sz;
            Object[] r = new Object[n];
            int i = 0;
            for (E e : this) {
                if (i == n) {
                    if (n >= MAX_ARRAY_SIZE)
                        throw new OutOfMemoryError(oomeMsg);
                    if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
                        n = MAX_ARRAY_SIZE;
                    else
                        n += (n >>> 1) + 1;
                    r = Arrays.<a href="https://www.jb51.cc/tag/cop/" target="_blank">cop</a>yOf(r,n);
                }
                r[i++] = e;
            }
            return (i == n) ? r : Arrays.<a href="https://www.jb51.cc/tag/cop/" target="_blank">cop</a>yOf(r,i);
        }

        @SuppressWarnings("unchecked")
        public final <T> T[] toArray(T[] a) {
            long sz = map.mappingCount();
            if (sz > MAX_ARRAY_SIZE)
                throw new OutOfMemoryError(oomeMsg);
            int m = (int)sz;
            T[] r = (a.length >= m) ? a :
                    (T[])<a href="https://www.jb51.cc/tag/javalang/" target="_blank">java.lang</a>.reflect.Array
                            .newInstance(a.getClass().getComponentType(),m);
            int n = r.length;
            int i = 0;
            for (E e : this) {
                if (i == n) {
                    if (n >= MAX_ARRAY_SIZE)
                        throw new OutOfMemoryError(oomeMsg);
                    if (n >= MAX_ARRAY_SIZE - (MAX_ARRAY_SIZE >>> 1) - 1)
                        n = MAX_ARRAY_SIZE;
                    else
                        n += (n >>> 1) + 1;
                    r = Arrays.<a href="https://www.jb51.cc/tag/cop/" target="_blank">cop</a>yOf(r,n);
                }
                r[i++] = (T)e;
            }
            if (a == r &amp;&amp; i < n) {
                r[i] = null; // null-terminate
                return r;
            }
            return (i == n) ? r : Arrays.<a href="https://www.jb51.cc/tag/cop/" target="_blank">cop</a>yOf(r,i);
        }


        public final String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append('[');
            I<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<E> it = i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor();
            if (it.hasNext()) {
                for (;;) {
                    Object e = it.next();
                    sb.append(e == this ? "(this Collection)" : e);
                    if (!it.hasNext())
                        break;
                    sb.append(',').append(' ');
                }
            }
            return sb.append(']').toString();
        }

        public final boolean containsAll(Collection<?> c) {
            if (c != this) {
                for (Object e : c) {
                    if (e == null || !contains(e))
                        return false;
                }
            }
            return true;
        }

        public final boolean removeAll(Collection<?> c) {
            if (c == null) throw new NullPointerException();
            boolean modified = false;
            for (I<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<E> it = i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor(); it.hasNext();) {
                if (c.contains(it.next())) {
                    it.remove();
                    modified = true;
                }
            }
            return modified;
        }

        public final boolean retainAll(Collection<?> c) {
            if (c == null) throw new NullPointerException();
            boolean modified = false;
            for (I<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<E> it = i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor(); it.hasNext();) {
                if (!c.contains(it.next())) {
                    it.remove();
                    modified = true;
                }
            }
            return modified;
        }

    }

    /**
     * ConcurrentHashMap键的集合视图,通过映射到<a href="https://www.jb51.cc/tag/yige/" target="_blank">一个</a>公共值,<a href="https://www.jb51.cc/tag/tianjia/" target="_blank">添加</a>操作可以具有选择性。
     * 这个类不能直接实例化。
     * @since 1.8
     */
    public static class KeySetView<K,V> extends CollectionView<K,K>
            implements Set<K>,java.io.Serializable {
        private static final long serialVersionUID = 7249069246763182397L;
        private final V value;
        KeySetView(ConcurrentHashMap<K,V> map,V value) {  // non-public
            super(map);
            this.value = value;
        }

        /**
         * Returns the default mapped value for additions,* or {@code null} if additions are not supported.
         *
         * @return the default mapped value for additions,or {@code null}
         * if not supported
         */
        public V getMappedValue() { return value; }

        /**
         * {@inheritDoc}
         * @throws NullPointerException if the specified key is null
         */
        public boolean contains(Object o) { return map.containsKey(o); }

        /**
         * Removes the key from this map view,by removing the key (and its
         * corresponding value) from the <a href="https://www.jb51.cc/tag/backing/" target="_blank">backing</a> map.  This method does
         * <a href="https://www.jb51.cc/tag/nothing/" target="_blank">nothing</a> if the key is not in the map.
         *
         * @p<a href="https://www.jb51.cc/tag/ara/" target="_blank">ara</a>m  o the key to be removed from the <a href="https://www.jb51.cc/tag/backing/" target="_blank">backing</a> map
         * @return {@code true} if the <a href="https://www.jb51.cc/tag/backing/" target="_blank">backing</a> map contained the specified key
         * @throws NullPointerException if the specified key is null
         */
        public boolean remove(Object o) { return map.remove(o) != null; }

        /**
         * @return an i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor over the keys of the <a href="https://www.jb51.cc/tag/backing/" target="_blank">backing</a> map
         */
        public I<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K> i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor() {
            Node<K,V>[] t;
            ConcurrentHashMap<K,V> m = map;
            int f = (t = m.table) == null ? 0 : t.length;
            return new KeyI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,m);
        }

        //<a href="https://www.jb51.cc/tag/tianjia/" target="_blank">添加</a>指定key,此时value为定义的<a href="https://www.jb51.cc/tag/mo/" target="_blank">默</a>认映射值
        public boolean add(K e) {
            V v;
            if ((v = value) == null)
                throw new UnsupportedOperationException();
            return map.putVal(e,true) == null;
        }

        public boolean addAll(Collection<? extends K> c) {
            boolean added = false;
            V v;
            if ((v = value) == null)
                throw new UnsupportedOperationException();
            for (K e : c) {
                if (map.putVal(e,true) == null)
                    added = true;
            }
            return added;
        }

        public int hashCode() {
            int h = 0;
            for (K e : this)
                h += e.hashCode();
            return h;
        }

        public boolean equals(Object o) {
            Set<?> c;
            return ((o instanceof Set) &amp;&amp;
                    ((c = (Set<?>)o) == this ||
                            (containsAll(c) &amp;&amp; c.containsAll(this))));
        }

        public Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K> spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor() {
            Node<K,V> m = map;
            long n = m.sumCount();
            int f = (t = m.table) == null ? 0 : t.length;
            return new KeySpli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,n < 0L ? 0L : n);
        }

        public void forEach(Consumer<? super K> action) {
            if (action == null) throw new NullPointerException();
            Node<K,V>[] t;
            if ((t = map.table) != null) {
                Traverser<K,t.length);
                for (Node<K,V> p; (p = it.advance()) != null; )
                    action.accept(p.key);
            }
        }
    }

    /**
     * A view of a ConcurrentHashMap as a {@link Collection} of
     * values,in which additions are <a href="https://www.jb51.cc/tag/dis/" target="_blank">dis</a>abled. This class cannot be
     * directly instantiated. See {@link #values()}.
     */
    static final class ValuesView<K,V>
            implements Collection<V>,java.io.Serializable {
        private static final long serialVersionUID = 2249069246763182397L;
        ValuesView(ConcurrentHashMap<K,V> map) { super(map); }
        public final boolean contains(Object o) {
            return map.containsValue(o);
        }

        public final boolean remove(Object o) {
            if (o != null) {
                for (I<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<V> it = i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor(); it.hasNext();) {
                    if (o.equals(it.next())) {
                        it.remove();
                        return true;
                    }
                }
            }
            return false;
        }

        public final I<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<V> i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor() {
            ConcurrentHashMap<K,V> m = map;
            Node<K,V>[] t;
            int f = (t = m.table) == null ? 0 : t.length;
            return new ValueI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,m);
        }

        public final boolean add(V e) {
            throw new UnsupportedOperationException();
        }
        public final boolean addAll(Collection<? extends V> c) {
            throw new UnsupportedOperationException();
        }

        public Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<V> spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor() {
            Node<K,V> m = map;
            long n = m.sumCount();
            int f = (t = m.table) == null ? 0 : t.length;
            return new ValueSpli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,n < 0L ? 0L : n);
        }

        public void forEach(Consumer<? super V> action) {
            if (action == null) throw new NullPointerException();
            Node<K,V> p; (p = it.advance()) != null; )
                    action.accept(p.val);
            }
        }
    }

    /**
     * A view of a ConcurrentHashMap as a {@link Set} of (key,value)
     * entries.  This class cannot be directly instantiated. See
     * {@link #entrySet()}.
     */
    static final class EntrySetView<K,V>>
            implements Set<Map.Entry<K,V>>,java.io.Serializable {
        private static final long serialVersionUID = 2249069246763182397L;
        EntrySetView(ConcurrentHashMap<K,V> map) { super(map); }

        public boolean contains(Object o) {
            Object k,r; Map.Entry<?,?>)o).getKey()) != null &amp;&amp;
                    (r = map.get(k)) != null &amp;&amp;
                    (v = e.getValue()) != null &amp;&amp;
                    (v == r || v.equals(r)));
        }

        public boolean remove(Object o) {
            Object k,?>)o).getKey()) != null &amp;&amp;
                    (v = e.getValue()) != null &amp;&amp;
                    map.remove(k,v));
        }

        /**
         * @return an i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor over the entries of the <a href="https://www.jb51.cc/tag/backing/" target="_blank">backing</a> map
         */
        public I<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<Map.Entry<K,V>> i<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor() {
            ConcurrentHashMap<K,V>[] t;
            int f = (t = m.table) == null ? 0 : t.length;
            return new EntryI<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,m);
        }

        public boolean add(Entry<K,V> e) {
            return map.putVal(e.getKey(),false) == null;
        }

        public boolean addAll(Collection<? extends Entry<K,V>> c) {
            boolean added = false;
            for (Entry<K,V> e : c) {
                if (add(e))
                    added = true;
            }
            return added;
        }

        public final int hashCode() {
            int h = 0;
            Node<K,V> p; (p = it.advance()) != null; ) {
                    h += p.hashCode();
                }
            }
            return h;
        }

        public final boolean equals(Object o) {
            Set<?> c;
            return ((o instanceof Set) &amp;&amp;
                    ((c = (Set<?>)o) == this ||
                            (containsAll(c) &amp;&amp; c.containsAll(this))));
        }

        public Spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<Map.Entry<K,V>> spli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor() {
            Node<K,V> m = map;
            long n = m.sumCount();
            int f = (t = m.table) == null ? 0 : t.length;
            return new EntrySpli<a href="https://www.jb51.cc/tag/tera/" target="_blank">tera</a>tor<K,n < 0L ? 0L : n,m);
        }

        public void forEach(Consumer<? super Map.Entry<K,V> p; (p = it.advance()) != null; )
                    action.accept(new MapEntry<K,map));
            }
        }

    }

    // -------------------------------------------------------

    //批量任务的基类。从类Traverser重复一些字段和<a href="https://www.jb51.cc/tag/daima/" target="_blank">代码</a>,因为我们需要子类CountedCompleter。
    @SuppressWarnings("serial")
    abstract static class BulkTask<K,R> extends CountedCompleter<R> {
        Node<K,V>[] tab;        // same as Traverser
        Node<K,V> next;
        TableStack<K,spare;
        int index;
        int baseIndex;
        int baseLimit;
        final int baseSize;
        int batch;              // split control

        BulkTask(BulkTask<K,?> par,int b,int f,V>[] t) {
            super(par);
            this.batch = b;
            this.index = this.baseIndex = i;
            if ((this.tab = t) == null)
                this.baseSize = this.baseLimit = 0;
            else if (par == null)
                this.baseSize = this.baseLimit = t.length;
            else {
                this.baseLimit = f;
                this.baseSize = par.baseSize;
            }
        }

        /**
         * Same as Traverser version
         */
        final Node<K,n;
                if (e != null)
                    return next = e;
                if (baseIndex >= baseLimit || (t = tab) == null ||
                        (n = t.length) <= (i = index) || i < 0)
                    return next = null;
                if ((e = tabAt(t,V>)e).f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>t;
                    else
                        e = null;
                }
                if (stack != null)
                    recoverState(n);
                else if ((index = i + baseSize) >= n)
                    index = ++baseIndex;
            }
        }

        private void pushState(Node<K,V> s = spare;
            if (s != null)
                spare = s.next;
            else
                s = new TableStack<K,V>();
            s.tab = t;
            s.length = n;
            s.index = i;
            s.next = stack;
            stack = s;
        }

        private void recoverState(int n) {
            TableStack<K,V> next = s.next;
                s.next = spare; // save for reuse
                stack = next;
                spare = s;
            }
            if (s == null &amp;&amp; (index += baseSize) >= n)
                index = ++baseIndex;
        }
    }

    /*
     * 任务类。使用常规
     * 由于编译器无法知道我们已经对任务参数进行了空值检查,因此我们强制使用最简单的提升旁路来帮助避免复杂检查。
     */
    @SuppressWarnings("serial")
    static final class ForEachKeyTask<K,V>
            extends BulkTask<K,Void> {
        final Consumer<? super K> action;
        ForEachKeyTask
                (BulkTask<K,?> p,Consumer<? super K> action) {
            super(p,b,t);
            this.action = action;
        }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final Consumer<? super K> action;
            if ((action = this.action) != null) {
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    new ForEachKeyTask<K,V>
                            (this,batch >>>= 1,tab,action).<a href="https://www.jb51.cc/tag/fork/" target="_blank">fork()</a>;
                }
                for (Node<K,V> p; (p = advance()) != null;)
                    action.accept(p.key);
                propagateCompletion();
            }
        }
    }

    @SuppressWarnings("serial")
    static final class ForEachValueTask<K,Void> {
        final Consumer<? super V> action;
        ForEachValueTask
                (BulkTask<K,Consumer<? super V> action) {
            super(p,t);
            this.action = action;
        }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final Consumer<? super V> action;
            if ((action = this.action) != null) {
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    new ForEachValueTask<K,V> p; (p = advance()) != null;)
                    action.accept(p.val);
                propagateCompletion();
            }
        }
    }

    @SuppressWarnings("serial")
    static final class ForEachEntryTask<K,Void> {
        final Consumer<? super Entry<K,V>> action;
        ForEachEntryTask
                (BulkTask<K,Consumer<? super Entry<K,V>> action) {
            super(p,t);
            this.action = action;
        }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final Consumer<? super Entry<K,V>> action;
            if ((action = this.action) != null) {
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    new ForEachEntryTask<K,V> p; (p = advance()) != null; )
                    action.accept(p);
                propagateCompletion();
            }
        }
    }

    @SuppressWarnings("serial")
    static final class ForEachMappingTask<K,Void> {
        final BiConsumer<? super K,? super V> action;
        ForEachMappingTask
                (BulkTask<K,? super V> action) {
            super(p,t);
            this.action = action;
        }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final BiConsumer<? super K,? super V> action;
            if ((action = this.action) != null) {
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    new ForEachMappingTask<K,V> p; (p = advance()) != null; )
                    action.accept(p.key,p.val);
                propagateCompletion();
            }
        }
    }

    @SuppressWarnings("serial")
    static final class ForEachTransformedKeyTask<K,U>
            extends BulkTask<K,Void> {
        final Function<? super K,? extends U> transformer;
        final Consumer<? super U> action;
        ForEachTransformedKeyTask
                (BulkTask<K,Consumer<? super U> action) {
            super(p,t);
            this.transformer = transformer; this.action = action;
        }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final Function<? super K,? extends U> transformer;
            final Consumer<? super U> action;
            if ((transformer = this.transformer) != null &amp;&amp;
                    (action = this.action) != null) {
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    new ForEachTransformedKeyTask<K,U>
                            (this,V> p; (p = advance()) != null; ) {
                    U u;
                    if ((u = transformer.apply(p.key)) != null)
                        action.accept(u);
                }
                propagateCompletion();
            }
        }
    }

    @SuppressWarnings("serial")
    static final class ForEachTransformedValueTask<K,Void> {
        final Function<? super V,? extends U> transformer;
        final Consumer<? super U> action;
        ForEachTransformedValueTask
                (BulkTask<K,t);
            this.transformer = transformer; this.action = action;
        }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final Function<? super V,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    new ForEachTransformedValueTask<K,V> p; (p = advance()) != null; ) {
                    U u;
                    if ((u = transformer.apply(p.val)) != null)
                        action.accept(u);
                }
                propagateCompletion();
            }
        }
    }

    @SuppressWarnings("serial")
    static final class ForEachTransformedEntryTask<K,Void> {
        final Function<Map.Entry<K,? extends U> transformer;
        final Consumer<? super U> action;
        ForEachTransformedEntryTask
                (BulkTask<K,t);
            this.transformer = transformer; this.action = action;
        }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final Function<Map.Entry<K,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    new ForEachTransformedEntryTask<K,V> p; (p = advance()) != null; ) {
                    U u;
                    if ((u = transformer.apply(p)) != null)
                        action.accept(u);
                }
                propagateCompletion();
            }
        }
    }

    @SuppressWarnings("serial")
    static final class ForEachTransformedMappingTask<K,Void> {
        final BiFunction<? super K,? extends U> transformer;
        final Consumer<? super U> action;
        ForEachTransformedMappingTask
                (BulkTask<K,t);
            this.transformer = transformer; this.action = action;
        }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final BiFunction<? super K,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    new ForEachTransformedMappingTask<K,V> p; (p = advance()) != null; ) {
                    U u;
                    if ((u = transformer.apply(p.key,p.val)) != null)
                        action.accept(u);
                }
                propagateCompletion();
            }
        }
    }

    @SuppressWarnings("serial")
    static final class SearchKeysTask<K,U> {
        final Function<? super K,? extends U> searchFunction;
        final <a href="https://www.jb51.cc/tag/atomicreference/" target="_blank">atomicreference</a><U> result;
        SearchKeysTask
                (BulkTask<K,? extends U> searchFunction,<a href="https://www.jb51.cc/tag/atomicreference/" target="_blank">atomicreference</a><U> result) {
            super(p,t);
            this.searchFunction = searchFunction; this.result = result;
        }
        public final U getRawResult() { return result.get(); }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final Function<? super K,? extends U> searchFunction;
            final <a href="https://www.jb51.cc/tag/atomicreference/" target="_blank">atomicreference</a><U> result;
            if ((searchFunction = this.searchFunction) != null &amp;&amp;
                    (result = this.result) != null) {
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    if (result.get() != null)
                        return;
                    addToPendingCount(1);
                    new SearchKeysTask<K,result).<a href="https://www.jb51.cc/tag/fork/" target="_blank">fork()</a>;
                }
                while (result.get() == null) {
                    U u;
                    Node<K,V> p;
                    if ((p = advance()) == null) {
                        propagateCompletion();
                        break;
                    }
                    if ((u = searchFunction.apply(p.key)) != null) {
                        if (result.compareAndSet(null,u))
                            quietlyCompleteRoot();
                        break;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class SearchValuesTask<K,U> {
        final Function<? super V,? extends U> searchFunction;
        final <a href="https://www.jb51.cc/tag/atomicreference/" target="_blank">atomicreference</a><U> result;
        SearchValuesTask
                (BulkTask<K,t);
            this.searchFunction = searchFunction; this.result = result;
        }
        public final U getRawResult() { return result.get(); }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final Function<? super V,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    if (result.get() != null)
                        return;
                    addToPendingCount(1);
                    new SearchValuesTask<K,V> p;
                    if ((p = advance()) == null) {
                        propagateCompletion();
                        break;
                    }
                    if ((u = searchFunction.apply(p.val)) != null) {
                        if (result.compareAndSet(null,u))
                            quietlyCompleteRoot();
                        break;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class SearchEntriesTask<K,U> {
        final Function<Entry<K,? extends U> searchFunction;
        final <a href="https://www.jb51.cc/tag/atomicreference/" target="_blank">atomicreference</a><U> result;
        SearchEntriesTask
                (BulkTask<K,Function<Entry<K,t);
            this.searchFunction = searchFunction; this.result = result;
        }
        public final U getRawResult() { return result.get(); }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final Function<Entry<K,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    if (result.get() != null)
                        return;
                    addToPendingCount(1);
                    new SearchEntriesTask<K,V> p;
                    if ((p = advance()) == null) {
                        propagateCompletion();
                        break;
                    }
                    if ((u = searchFunction.apply(p)) != null) {
                        if (result.compareAndSet(null,u))
                            quietlyCompleteRoot();
                        return;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class SearchMappingsTask<K,U> {
        final BiFunction<? super K,? extends U> searchFunction;
        final <a href="https://www.jb51.cc/tag/atomicreference/" target="_blank">atomicreference</a><U> result;
        SearchMappingsTask
                (BulkTask<K,t);
            this.searchFunction = searchFunction; this.result = result;
        }
        public final U getRawResult() { return result.get(); }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final BiFunction<? super K,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    if (result.get() != null)
                        return;
                    addToPendingCount(1);
                    new SearchMappingsTask<K,V> p;
                    if ((p = advance()) == null) {
                        propagateCompletion();
                        break;
                    }
                    if ((u = searchFunction.apply(p.key,p.val)) != null) {
                        if (result.compareAndSet(null,u))
                            quietlyCompleteRoot();
                        break;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class ReduceKeysTask<K,K> {
        final BiFunction<? super K,? extends K> reducer;
        K result;
        ReduceKeysTask<K,V> rights,nextRight;
        ReduceKeysTask
                (BulkTask<K,ReduceKeysTask<K,V> nextRight,? extends K> reducer) {
            super(p,t); this.nextRight = nextRight;
            this.reducer = reducer;
        }
        public final K getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final BiFunction<? super K,? extends K> reducer;
            if ((reducer = this.reducer) != null) {
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new ReduceKeysTask<K,rights,reducer)).<a href="https://www.jb51.cc/tag/fork/" target="_blank">fork()</a>;
                }
                K r = null;
                for (Node<K,V> p; (p = advance()) != null; ) {
                    K u = p.key;
                    r = (r == null) ? u : u == null ? r : reducer.apply(r,u);
                }
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    ReduceKeysTask<K,V>
                            t = (ReduceKeysTask<K,V>)c,s = t.rights;
                    while (s != null) {
                        K tr,sr;
                        if ((sr = s.result) != null)
                            t.result = (((tr = t.result) == null) ? sr :
                                    reducer.apply(tr,sr));
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class ReduceValuesTask<K,V> {
        final BiFunction<? super V,? extends V> reducer;
        V result;
        ReduceValuesTask<K,nextRight;
        ReduceValuesTask
                (BulkTask<K,ReduceValuesTask<K,? extends V> reducer) {
            super(p,t); this.nextRight = nextRight;
            this.reducer = reducer;
        }
        public final V getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final BiFunction<? super V,? extends V> reducer;
            if ((reducer = this.reducer) != null) {
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new ReduceValuesTask<K,reducer)).<a href="https://www.jb51.cc/tag/fork/" target="_blank">fork()</a>;
                }
                V r = null;
                for (Node<K,V> p; (p = advance()) != null; ) {
                    V v = p.val;
                    r = (r == null) ? v : reducer.apply(r,v);
                }
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    ReduceValuesTask<K,V>
                            t = (ReduceValuesTask<K,s = t.rights;
                    while (s != null) {
                        V tr,sr));
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class ReduceEntriesTask<K,V>> {
        final BiFunction<Map.Entry<K,V>> reducer;
        Map.Entry<K,V> result;
        ReduceEntriesTask<K,nextRight;
        ReduceEntriesTask
                (BulkTask<K,ReduceEntriesTask<K,BiFunction<Entry<K,V>> reducer) {
            super(p,t); this.nextRight = nextRight;
            this.reducer = reducer;
        }
        public final Map.Entry<K,V> getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final BiFunction<Map.Entry<K,V>> reducer;
            if ((reducer = this.reducer) != null) {
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new ReduceEntriesTask<K,reducer)).<a href="https://www.jb51.cc/tag/fork/" target="_blank">fork()</a>;
                }
                Map.Entry<K,V> r = null;
                for (Node<K,V> p; (p = advance()) != null; )
                    r = (r == null) ? p : reducer.apply(r,p);
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    ReduceEntriesTask<K,V>
                            t = (ReduceEntriesTask<K,s = t.rights;
                    while (s != null) {
                        Map.Entry<K,V> tr,sr));
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    //MapReduce

    @SuppressWarnings("serial")
    static final class MapReduceKeysTask<K,? extends U> transformer;
        final BiFunction<? super U,? extends U> reducer;
        U result;
        MapReduceKeysTask<K,U> rights,nextRight;
        MapReduceKeysTask
                (BulkTask<K,MapReduceKeysTask<K,U> nextRight,? extends U> reducer) {
            super(p,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.reducer = reducer;
        }
        public final U getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final Function<? super K,? extends U> transformer;
            final BiFunction<? super U,? extends U> reducer;
            if ((transformer = this.transformer) != null &amp;&amp;
                    (reducer = this.reducer) != null) {
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceKeysTask<K,reducer)).<a href="https://www.jb51.cc/tag/fork/" target="_blank">fork()</a>;
                }
                U r = null;
                for (Node<K,V> p; (p = advance()) != null; ) {
                    U u;
                    if ((u = transformer.apply(p.key)) != null)
                        r = (r == null) ? u : reducer.apply(r,u);
                }
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceKeysTask<K,U>
                            t = (MapReduceKeysTask<K,U>)c,s = t.rights;
                    while (s != null) {
                        U tr,sr));
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceValuesTask<K,? extends U> reducer;
        U result;
        MapReduceValuesTask<K,nextRight;
        MapReduceValuesTask
                (BulkTask<K,MapReduceValuesTask<K,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.reducer = reducer;
        }
        public final U getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final Function<? super V,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceValuesTask<K,V> p; (p = advance()) != null; ) {
                    U u;
                    if ((u = transformer.apply(p.val)) != null)
                        r = (r == null) ? u : reducer.apply(r,u);
                }
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceValuesTask<K,U>
                            t = (MapReduceValuesTask<K,sr));
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceEntriesTask<K,U> {
        final Function<Map.Entry<K,? extends U> reducer;
        U result;
        MapReduceEntriesTask<K,nextRight;
        MapReduceEntriesTask
                (BulkTask<K,MapReduceEntriesTask<K,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.reducer = reducer;
        }
        public final U getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final Function<Map.Entry<K,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceEntriesTask<K,V> p; (p = advance()) != null; ) {
                    U u;
                    if ((u = transformer.apply(p)) != null)
                        r = (r == null) ? u : reducer.apply(r,u);
                }
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceEntriesTask<K,U>
                            t = (MapReduceEntriesTask<K,sr));
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceMappingsTask<K,? extends U> reducer;
        U result;
        MapReduceMappingsTask<K,nextRight;
        MapReduceMappingsTask
                (BulkTask<K,MapReduceMappingsTask<K,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.reducer = reducer;
        }
        public final U getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final BiFunction<? super K,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceMappingsTask<K,p.val)) != null)
                        r = (r == null) ? u : reducer.apply(r,u);
                }
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceMappingsTask<K,U>
                            t = (MapReduceMappingsTask<K,sr));
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceKeysT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,Double> {
        final T<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleFunction<? super K> transformer;
        final DoubleBinaryOperator reducer;
        final double basis;
        double result;
        MapReduceKeysT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,nextRight;
        MapReduceKeysT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask
                (BulkTask<K,MapReduceKeysT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,DoubleBinaryOperator reducer) {
            super(p,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.basis = basis; this.reducer = reducer;
        }
        public final Double getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final T<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleFunction<? super K> transformer;
            final DoubleBinaryOperator reducer;
            if ((transformer = this.transformer) != null &amp;&amp;
                    (reducer = this.reducer) != null) {
                double r = this.basis;
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceKeysT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,r,reducer)).<a href="https://www.jb51.cc/tag/fork/" target="_blank">fork()</a>;
                }
                for (Node<K,V> p; (p = advance()) != null; )
                    r = reducer.applyAsDouble(r,transformer.applyAsDouble(p.key));
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceKeysT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,V>
                            t = (MapReduceKeysT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,s = t.rights;
                    while (s != null) {
                        t.result = reducer.applyAsDouble(t.result,s.result);
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceValuesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,Double> {
        final T<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleFunction<? super V> transformer;
        final DoubleBinaryOperator reducer;
        final double basis;
        double result;
        MapReduceValuesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,nextRight;
        MapReduceValuesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask
                (BulkTask<K,MapReduceValuesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.basis = basis; this.reducer = reducer;
        }
        public final Double getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final T<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleFunction<? super V> transformer;
            final DoubleBinaryOperator reducer;
            if ((transformer = this.transformer) != null &amp;&amp;
                    (reducer = this.reducer) != null) {
                double r = this.basis;
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceValuesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,transformer.applyAsDouble(p.val));
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceValuesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,V>
                            t = (MapReduceValuesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,s.result);
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceEntriesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,Double> {
        final T<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleFunction<Map.Entry<K,V>> transformer;
        final DoubleBinaryOperator reducer;
        final double basis;
        double result;
        MapReduceEntriesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,nextRight;
        MapReduceEntriesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask
                (BulkTask<K,MapReduceEntriesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.basis = basis; this.reducer = reducer;
        }
        public final Double getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final T<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleFunction<Map.Entry<K,V>> transformer;
            final DoubleBinaryOperator reducer;
            if ((transformer = this.transformer) != null &amp;&amp;
                    (reducer = this.reducer) != null) {
                double r = this.basis;
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceEntriesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,transformer.applyAsDouble(p));
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceEntriesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,V>
                            t = (MapReduceEntriesT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,s.result);
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceMappingsT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,Double> {
        final T<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleBiFunction<? super K,? super V> transformer;
        final DoubleBinaryOperator reducer;
        final double basis;
        double result;
        MapReduceMappingsT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,nextRight;
        MapReduceMappingsT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask
                (BulkTask<K,MapReduceMappingsT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.basis = basis; this.reducer = reducer;
        }
        public final Double getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final T<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleBiFunction<? super K,? super V> transformer;
            final DoubleBinaryOperator reducer;
            if ((transformer = this.transformer) != null &amp;&amp;
                    (reducer = this.reducer) != null) {
                double r = this.basis;
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceMappingsT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,transformer.applyAsDouble(p.key,p.val));
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceMappingsT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,V>
                            t = (MapReduceMappingsT<a href="https://www.jb51.cc/tag/odo/" target="_blank">odo</a>ubleTask<K,s.result);
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceKeysToLongTask<K,Long> {
        final ToLongFunction<? super K> transformer;
        final LongBinaryOperator reducer;
        final long basis;
        long result;
        MapReduceKeysToLongTask<K,nextRight;
        MapReduceKeysToLongTask
                (BulkTask<K,MapReduceKeysToLongTask<K,LongBinaryOperator reducer) {
            super(p,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.basis = basis; this.reducer = reducer;
        }
        public final Long getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final ToLongFunction<? super K> transformer;
            final LongBinaryOperator reducer;
            if ((transformer = this.transformer) != null &amp;&amp;
                    (reducer = this.reducer) != null) {
                long r = this.basis;
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceKeysToLongTask<K,V> p; (p = advance()) != null; )
                    r = reducer.applyAsLong(r,transformer.applyAsLong(p.key));
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceKeysToLongTask<K,V>
                            t = (MapReduceKeysToLongTask<K,s = t.rights;
                    while (s != null) {
                        t.result = reducer.applyAsLong(t.result,s.result);
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceValuesToLongTask<K,Long> {
        final ToLongFunction<? super V> transformer;
        final LongBinaryOperator reducer;
        final long basis;
        long result;
        MapReduceValuesToLongTask<K,nextRight;
        MapReduceValuesToLongTask
                (BulkTask<K,MapReduceValuesToLongTask<K,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.basis = basis; this.reducer = reducer;
        }
        public final Long getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final ToLongFunction<? super V> transformer;
            final LongBinaryOperator reducer;
            if ((transformer = this.transformer) != null &amp;&amp;
                    (reducer = this.reducer) != null) {
                long r = this.basis;
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceValuesToLongTask<K,transformer.applyAsLong(p.val));
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceValuesToLongTask<K,V>
                            t = (MapReduceValuesToLongTask<K,s.result);
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceEntriesToLongTask<K,Long> {
        final ToLongFunction<Map.Entry<K,V>> transformer;
        final LongBinaryOperator reducer;
        final long basis;
        long result;
        MapReduceEntriesToLongTask<K,nextRight;
        MapReduceEntriesToLongTask
                (BulkTask<K,MapReduceEntriesToLongTask<K,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.basis = basis; this.reducer = reducer;
        }
        public final Long getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final ToLongFunction<Map.Entry<K,V>> transformer;
            final LongBinaryOperator reducer;
            if ((transformer = this.transformer) != null &amp;&amp;
                    (reducer = this.reducer) != null) {
                long r = this.basis;
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceEntriesToLongTask<K,transformer.applyAsLong(p));
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceEntriesToLongTask<K,V>
                            t = (MapReduceEntriesToLongTask<K,s.result);
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceMappingsToLongTask<K,Long> {
        final ToLongBiFunction<? super K,? super V> transformer;
        final LongBinaryOperator reducer;
        final long basis;
        long result;
        MapReduceMappingsToLongTask<K,nextRight;
        MapReduceMappingsToLongTask
                (BulkTask<K,MapReduceMappingsToLongTask<K,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.basis = basis; this.reducer = reducer;
        }
        public final Long getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final ToLongBiFunction<? super K,? super V> transformer;
            final LongBinaryOperator reducer;
            if ((transformer = this.transformer) != null &amp;&amp;
                    (reducer = this.reducer) != null) {
                long r = this.basis;
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceMappingsToLongTask<K,transformer.applyAsLong(p.key,p.val));
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceMappingsToLongTask<K,V>
                            t = (MapReduceMappingsToLongTask<K,s.result);
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceKeysToIntTask<K,Integer> {
        final ToIntFunction<? super K> transformer;
        final IntBinaryOperator reducer;
        final int basis;
        int result;
        MapReduceKeysToIntTask<K,nextRight;
        MapReduceKeysToIntTask
                (BulkTask<K,MapReduceKeysToIntTask<K,IntBinaryOperator reducer) {
            super(p,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.basis = basis; this.reducer = reducer;
        }
        public final Integer getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final ToIntFunction<? super K> transformer;
            final IntBinaryOperator reducer;
            if ((transformer = this.transformer) != null &amp;&amp;
                    (reducer = this.reducer) != null) {
                int r = this.basis;
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceKeysToIntTask<K,V> p; (p = advance()) != null; )
                    r = reducer.applyAsInt(r,transformer.applyAsInt(p.key));
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceKeysToIntTask<K,V>
                            t = (MapReduceKeysToIntTask<K,s = t.rights;
                    while (s != null) {
                        t.result = reducer.applyAsInt(t.result,s.result);
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceValuesToIntTask<K,Integer> {
        final ToIntFunction<? super V> transformer;
        final IntBinaryOperator reducer;
        final int basis;
        int result;
        MapReduceValuesToIntTask<K,nextRight;
        MapReduceValuesToIntTask
                (BulkTask<K,MapReduceValuesToIntTask<K,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.basis = basis; this.reducer = reducer;
        }
        public final Integer getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final ToIntFunction<? super V> transformer;
            final IntBinaryOperator reducer;
            if ((transformer = this.transformer) != null &amp;&amp;
                    (reducer = this.reducer) != null) {
                int r = this.basis;
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceValuesToIntTask<K,transformer.applyAsInt(p.val));
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceValuesToIntTask<K,V>
                            t = (MapReduceValuesToIntTask<K,s.result);
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceEntriesToIntTask<K,Integer> {
        final ToIntFunction<Map.Entry<K,V>> transformer;
        final IntBinaryOperator reducer;
        final int basis;
        int result;
        MapReduceEntriesToIntTask<K,nextRight;
        MapReduceEntriesToIntTask
                (BulkTask<K,MapReduceEntriesToIntTask<K,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.basis = basis; this.reducer = reducer;
        }
        public final Integer getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final ToIntFunction<Map.Entry<K,V>> transformer;
            final IntBinaryOperator reducer;
            if ((transformer = this.transformer) != null &amp;&amp;
                    (reducer = this.reducer) != null) {
                int r = this.basis;
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceEntriesToIntTask<K,transformer.applyAsInt(p));
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceEntriesToIntTask<K,V>
                            t = (MapReduceEntriesToIntTask<K,s.result);
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    @SuppressWarnings("serial")
    static final class MapReduceMappingsToIntTask<K,Integer> {
        final ToIntBiFunction<? super K,? super V> transformer;
        final IntBinaryOperator reducer;
        final int basis;
        int result;
        MapReduceMappingsToIntTask<K,nextRight;
        MapReduceMappingsToIntTask
                (BulkTask<K,MapReduceMappingsToIntTask<K,t); this.nextRight = nextRight;
            this.transformer = transformer;
            this.basis = basis; this.reducer = reducer;
        }
        public final Integer getRawResult() { return result; }
        public final void co<a href="https://www.jb51.cc/tag/mpu/" target="_blank">mpu</a>te() {
            final ToIntBiFunction<? super K,? super V> transformer;
            final IntBinaryOperator reducer;
            if ((transformer = this.transformer) != null &amp;&amp;
                    (reducer = this.reducer) != null) {
                int r = this.basis;
                for (int i = baseIndex,h; batch > 0 &amp;&amp;
                        (h = ((f = baseLimit) + i) >>> 1) > i;) {
                    addToPendingCount(1);
                    (rights = new MapReduceMappingsToIntTask<K,transformer.applyAsInt(p.key,p.val));
                result = r;
                CountedCompleter<?> c;
                for (c = f<a href="https://www.jb51.cc/tag/irs/" target="_blank">irs</a>tComplete(); c != null; c = c.nextComplete()) {
                    @SuppressWarnings("unchecked")
                    MapReduceMappingsToIntTask<K,V>
                            t = (MapReduceMappingsToIntTask<K,s.result);
                        s = t.rights = s.nextRight;
                    }
                }
            }
        }
    }

    /*-------Unsafe mechanics------*/
    /**
     * unsafe<a href="https://www.jb51.cc/tag/daima/" target="_blank">代码</a>块控制了一些<a href="https://www.jb51.cc/tag/shuxing/" target="_blank">属性</a>的<a href="https://www.jb51.cc/tag/xiugai/" target="_blank">修改</a>工作,比如最常用的SIZECTL 。
     * <a href="https://www.jb51.cc/tag/zaizhe/" target="_blank">在这</a>一版本的concurrentHashMap中,大量应用来的CAS<a href="https://www.jb51.cc/tag/fangfa/" target="_blank">方法</a>进行变量、<a href="https://www.jb51.cc/tag/shuxing/" target="_blank">属性</a>的<a href="https://www.jb51.cc/tag/xiugai/" target="_blank">修改</a>工作。利用CAS进行无锁操作,可以大大提高<a href="https://www.jb51.cc/tag/xingneng/" target="_blank">性能</a>。
     * static<a href="https://www.jb51.cc/tag/daima/" target="_blank">代码</a>块中:大量使用了反射
     */
    private static final sun.misc.Unsafe U;
    private static final long SIZECTL;
    private static final long TRANSFERINDEX;
    private static final long BASECOUNT;
    private static final long CELLSBUSY;
    private static final long CELLVALUE;
    private static final long ABASE;
    private static final int ASHIFT;

    static {
        try {
            U = sun.misc.Unsafe.getUnsafe();
            Class<?> k = ConcurrentHashMap.class;
            SIZECTL = U.objectFieldOffset
                    (k.getDeclaredField("sizeCtl"));
            TRANSFERINDEX = U.objectFieldOffset
                    (k.getDeclaredField("transferIndex"));
            BASECOUNT = U.objectFieldOffset
                    (k.getDeclaredField("baseCount"));
            CELLSBUSY = U.objectFieldOffset
                    (k.getDeclaredField("cellsBusy"));
            Class<?> ck = CounterCell.class;
            CELLVALUE = U.objectFieldOffset
                    (ck.getDeclaredField("value"));
            Class<?> ak = Node[].class;
            ABASE = U.arrayBa<a href="https://www.jb51.cc/tag/SEO/" title="SEO">SEO</a>ffset(ak);
            int scale = U.arrayIndexScale(ak);
            if ((scale &amp; (scale - 1)) != 0)
                throw new Error("data type scale not a power of two");
            ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
        } catch (Exception e) {
            throw new Error(e);
        }
    }
}

参考:nofollow">https://blog.csdn.net/u010723709/article/details/48007881

ConcurrentHashMa源码

ConcurrentHashMa源码

概括:

        这个哈希表的主要设计目标是维护并发可读性(通常方法get(),但也迭代器和相关方法),同时最小化更新争用。

        次要的目标是保持空间消耗与java.util相同或更好。

        HashMap,并支持high多个线程对空表的初始插入率。

 

        这个映射通常充当一个binned (bucked)哈希表。每一个键值映射保存在节点中。大多数节点都是实例包含散列、键、值和next的基本节点类字段。

然而,存在各种子类:treenode排列成平衡的树,而不是列表。树冠支撑着树根一组树状阳极。转发节点位于头部调整大小期间的桶。reservationnode用作

占位符,同时在computeIfAbsent和相关的方法。类型为TreeBin、forwarding节点和ReservationNode不保存正常的用户密钥、值或散列,以及在搜索过程中容易区分等。因为它们有负哈希字段和空键和值字段。(这些特殊的节点不是不常见就是短暂的,因此,携带一些未使用的字段的影响是微不足道。)

 

        时,将该表惰性地初始化为2的幂级大小第一次插入。表中的每个bin通常包含一个节点列表(通常,列表只有0个或一个节点)。表访问需要volatile/原子读、写和案件。因为没有其他方法来安排这个添加进一步的间接,我们使用了intrinsics (sun.misc.Unsafe)操作。

 

        我们使用节点哈希字段的顶部(符号)位进行控制目的——由于寻址,无论如何它都是可用的约束。具有负哈希字段的节点是特殊的在map方法中处理或忽略。

 

        方法中第一个节点的插入(通过put或其变体)空桶是通过将其装箱到桶中来执行的。这是到目前为止,put操作在most下最常见的情况键/散列分布。其他更新操作(插入、删除和替换)需要锁。我们不想浪费将一个不同的锁对象与之关联所需的空间每个bin,因此使用bin列表本身的第一个节点作为一个锁。对这些锁的锁定支持依赖于内置监控“同步”。

        将列表的第一个节点用作锁本身并不会这样做足够了:当一个节点被锁定时,任何更新都必须首先进行确认它仍然是锁定后的第一个节点,并且如果没有,请重试。因为新节点总是附加到列表中,一旦一个节点在一个bin中第一个被删除,它就会保持在第一个直到被删除或bin(调整大小后)失效。

 

每个bin锁的主要缺点是其他更新在受相同保护的bin列表中的其他节点上执行操作lock可能会停止,例如当user =()或映射时功能需要很长时间。然而,据统计,

随机哈希码,这不是一个常见的问题。理想情况下,箱中节点的频率服从泊松分布(http://en.wikipedia.org/wiki/Poisson_distribution)给定调整阈值,参数平均约为0.5为0.75,但由于调整大小,方差较大粒度。忽略方差,期望发生的列表大小k是(exp(-0.5) * pow(0.5, k) / factorial(k))。的

第一个值是:

0:    0.60653066
1:    0.30326533

2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006

多于:少于千分之一

两个访问不同的线程的锁争用概率元素大约是随机哈希下的1 /(8 * #元素)。

        实际中遇到的哈希代码分布有时明显偏离统一的随机性。这个包括n>时的情况(1<<30),因此某些键必须碰撞。同样地,对于多个键都是设计为具有相同的哈希代码或仅不同的哈希代码隐藏的高位。所以我们使用了一个二级策略当bin中的节点数超过阈值。这些树键使用平衡树来保存节点(a特殊形式的红黑树),边界搜索时间O(log n)。treebin中的每个搜索步骤至少是和普通的列表一样慢,但考虑到n不能超过(1<<64)(在地址用完之前)此边界搜索步进、锁定保持时间等,达到合理的常数(大致每个操作检查100个节点(最坏情况),只要键具有可比性(非常常见——字符串、长字符串等)。treebin节点(treenodes)也保持相同的“next”遍历指针作为常规节点,因此可以遍历以同样的方式使用迭代器。

当占用率超过某个百分比时,将调整表的大小。阈值(名义上为0.75,但见下文)。任何线程注意到垃圾箱过满可能有助于在启动线程分配并设置替换数组。但是,这些其他线程可能会继续运行,而不是停止运行。插入等。使用treebins保护我们不受调整大小时过度填充的最坏情况影响进步。通过一个接一个地传送垃圾箱来调整收益大小,从桌子到下一张桌子。然而,线程声称很小之前要传输的索引块(通过字段transferIndex)这样做可以减少争用。田间的世代印记sizectl确保大小调整不会重叠。因为我们是使用两次扩展的力量,每个箱子的元件必须要么保持同一索引,要么以2的幂移动偏移量。我们通过捕获旧节点可以重用的情况,因为它们的下一个字段不会改变的。平均来说,只有大约六分之一的人需要当表翻倍时进行克隆。它们替换的节点将是一旦不再被引用,便可收集的垃圾任何可能同时处于遍历表。在传输时,旧的表bin包含只有一个特殊的转发节点(哈希字段为“moved”)。包含下一个表作为其键。遇到一个转发节点,访问和更新操作重新启动,使用新桌子。

HashMap、Hashtable、ConcurrentHashMap、ConcurrentSkipListMap对比及java并发包(java.util.concurrent)

HashMap、Hashtable、ConcurrentHashMap、ConcurrentSkipListMap对比及java并发包(java.util.concurrent)

一、基础普及

 

 

接口(interface)

类(class)

继承类

实现的接口

Array

 

 

 

 

Collection

 

 

 

Set

 

Collection

 

List

 

Collection

 

Map

 

Collection

 

Vector

 

 

List

ArrayList

 

 

List

HashMap

 

 

Map

Hashtable

 

Dictionary

Map

ConcurrentMap

 

Map

 

 

ConcurrentHashMap

 

 

 

ConcurrentMap

 

二、对比 

1、HashMap与Hashtable区别

 

 

是否线程安全

允不允许null值

Hashtable

线程安全。

因为里面的方法使用了synchronized进行同步

不允许。

key和value都不允许出现null值,否则会抛出NullPointerException异常。

HashMap

非线程安全。

可以通过以下方式进行同步:

Map m = Collections.synchronizeMap(hashMap);

允许。

null可以作为键,这样的键只有一个;可以有一个或多个键所对应的值为null。

 

Tip:

1、Hashtable是线程安全的,多个线程可以共享一个Hashtable;而如果没有正确的同步的话,多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。

2、由于Hashtable是线程安全的也是synchronized,所以在单线程环境下它比HashMap要慢。如果你不需要同步,只需要单一线程,那么使用HashMap性能要好过Hashtable。

 

 

2、Hashtable和ConcurrentHashMap在lock表区别图

 

 

 

三、java并发包(java.util.concurrent)

 

1、线程池:

 

1.1、为什么要用到线程池

 

使用线程池的好处是减少在创建和销毁线程上所花的时间以及系统资源的开销,解决资源不足的问题
如果不使用线程池,有可能造成系统创建大量同类线程而导致消耗完内存或者“过度切换”的问题。

 

1.2、线程池创建方式(常用)

 

1)固定数量的线程池newFixedThreadPool

 

int cpu = Runtime.getRuntime().availableProcessors();
final ExecutorService es = Executors.newFixedThreadPool(cpu);

 

2)可调度的线程池Scheduled Thread Pool 

 

ScheduledExecutorService scheduledThreadPool = Executors.newScheduledThreadPool(4);

 

2、Java容器:

2.1、同步类容器

第一类:

  同步类:Vector、Stack、Hashtable

  非同步类:ArrayList、LinkedList、HashMap

第二类:Collections提供的一些工厂类(静态)

 

 

2.2、并发类容器

java.util.concurrent提供了多种并发容器,总体上来说有4类:

  • 队列Queue类型的BlockingQueue和ConcurrentLinkedQueue
  • Map类型的ConcurrentMap
  • Set类型的ConcurrentSkipListSet和CopyOnWriteArraySet
  • List类型的CopyOnWriteArrayList

 

在并发比较大的情况下,用ConcurrentMap来替代HashTable

使用CopyOnWriteArrayList替代Vector

2.3、concurrentHashMap

2.3.1、为什么采用concurrentHashMap:

Hashtable写操作会锁住整张表,效率低,写操作无法并行

concurrentHashMap分成16个桶(把整张表分成16份),适合高并发

2.3.2、ConcurrentHashMap介绍:

  ConcurrentHashMap采用了分段锁的设计,只有在同一个分段内才存在竞态关系,不同的分段锁之间没有锁竞争。

  相比于对整个Map加锁的设计,分段锁大大的提高了高并发环境下的处理能力。

 

2.3.3、Hashtable和ConcurrentHashMap在lock表区别图

 

 

2.3.4、ConcurrentSkipListMap

 

 

跳表查询,比ConcurrentHashMap效率快。

四、Java并发包消息队列

1、BlockingQueue 阻塞队列

主要的方法是:put、take一对阻塞存取;add、poll一对非阻塞存取。

put(anObject):把anObject加到BlockingQueue里,如果BlockQueue没有空间,则调用此方法的线程被阻塞直到BlockingQueue里面有空间再继续

take():取走BlockingQueue里排在首位的对象,若BlockingQueue为空,阻断进入等待状态直到Blocking有新的对象被加入为止

2、BlockingQueue成员介绍

2.1、ArrayBlockingQueue:

基于数组实现的有界阻塞队列,查找快,增删慢。生产者和消费者用的是同一把锁,并发效率低

消费的方式:FIFO

2.2、LinkedBlockingQueue:

基于链表实现的阻塞队列,链表是增删快,定位慢,生产者和消费者用的锁相互独立,并发性能略高于ArrayBlockingQueue

2.3、DelayQueue(延时队列):

DelayQueue中的元素,只有指定的延迟时间到了,才能够从队列中获取到该元素。

DelayQueue是一个没有大小限制的队列,因此往队列中插入数据的操作(生产者)永远不会被阻塞,而只有获取数据的操作(消费者)才会被阻塞

应用场景

1、客户端长时间占用连接的问题,超过这个空闲时间了,可以移除的

2、处理长时间不用的缓存;如果队列里面的对象长时间不用,超过了空闲时间,就移除

3、任务超时处理

2.4、PriorityBlockingQueue(优先级队列):

PriorityBlockingQueue并不会阻塞数据生产者,而只会在没有可消费的数据时,阻塞数据的消费者不阻塞生产者

compareTo()方法决定优先级。

2.5、SynchronousQueue(同步无缓冲队列):

一种无缓冲的等待队列,来一个任务就执行这个任务,这期间不能太添加任何的任务。也就是不用阻塞了,其实对于少量任务而言,这种做法更高效

声明一个SynchronousQueue有两种不同的方式,它们之间有着不太一样的行为。

公平模式和非公平模式的区别:

如果采用公平模式:SynchronousQueue会采用公平锁,并配合一个FIFO队列来阻塞多余的生产者和消费者,从而体系整体的公平策略;

但如果是非公平模式(SynchronousQueue默认):SynchronousQueue采用非公平锁,同时配合一个LIFO队列来管理多余的生产者和消费者,而后一种模式,如果生产者和消费者的处理速度有差距,则很容易出现饥渴的情况,即可能有某些生产者或者是消费者的数据永远都得不到处理。

2.5、concurrentLinkedQueue(高并发无锁队列)

 

 

 

 

 

关于java源码学习---ConcurrentHashMapjava concurrenthashmap原理的问题我们已经讲解完毕,感谢您的阅读,如果还想了解更多关于ConcurrentHashMap 与同步 HashMap - ConcurrentHashMap vs Synchronized HashMap、ConcurrentHashMap源码分析-Java8、ConcurrentHashMa源码、HashMap、Hashtable、ConcurrentHashMap、ConcurrentSkipListMap对比及java并发包(java.util.concurrent)等相关内容,可以在本站寻找。

本文标签: