GVKun编程网logo

Java并发(四):并发集合ConcurrentHashMap的源码分析(java 并发集合)

19

在本文中,您将会了解到关于Java并发(四):并发集合ConcurrentHashMap的源码分析的新资讯,同时我们还将为您解释java并发集合的相关在本文中,我们将带你探索Java并发(四):并发集

在本文中,您将会了解到关于Java并发(四):并发集合ConcurrentHashMap的源码分析的新资讯,同时我们还将为您解释java 并发集合的相关在本文中,我们将带你探索Java并发(四):并发集合ConcurrentHashMap的源码分析的奥秘,分析java 并发集合的特点,并给出一些关于ConcurrentHashMap比其他并发集合的安全效率要高一些?、ConcurrentHashMap源码分析-Java8、HashMap、Hashtable、ConcurrentHashMap、ConcurrentSkipListMap对比及java并发包(java.util.concurrent)、Java 并发分析 —ConcurrentHashMap的实用技巧。

本文目录一览:

Java并发(四):并发集合ConcurrentHashMap的源码分析(java 并发集合)

Java并发(四):并发集合ConcurrentHashMap的源码分析(java 并发集合)

  之前介绍了Java并发的基础知识和使用案例分析,接下来我们正式地进入Java并发的源码分析阶段,本文作为源码分析地开篇,源码参考JDK1.8

OverView:

  JDK1.8源码中的注释提到:ConcurrentHashMap是一种提供完整的并发检索和对于并发更新有高预测性的散列表,遵循了与HashMap相同的功能性规格,并包含与HashTable每个方法都对应的方法.虽然所有操作都是线程安全的,但检索操作并不牵涉任何锁,不支持任何锁住整个散列表来保护所有的访问.

  ConcurrentHashMap不会和HashTable一样,滥用synchronized关键字,从而令许多操作会锁住整个容器,而是采用分段锁技术,它的加锁粒度更细,并发访问环境下能获得更好高的吞吐量;

ConcurrentHashMap的数据结构如下图所示

JDK1.8虽然已经摒弃Segment来存儲,但他仍然兼容Segment,只是它被用在序列化实现上了,直接用Node数组+链表(或红黑树)的数据结构来实现,并发控制使用Synchronized和CAS来实现;

 

部分核心源码分析:

 

构造器:

public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
        //三个参数分别是:集合容量,负载因子,并发级别
        //集合容量即预计的集合容量
        //负载因子是指集合的密度,或者说是有效存儲占比
        //并发级别即预估的并发修改集合的线程个数
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (initialCapacity < concurrencyLevel)   
            initialCapacity = concurrencyLevel;   //构造集合时,容量默认大于等于并发级别
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        //计算长度时要带上避免哈希冲突的链地址法产生的额外的存储空间再加1
        
        int cap = (size >= (long)MAXIMUM_CAPACITY) ?
            MAXIMUM_CAPACITY : tableSizeFor((int)size);
        //限制集合的最大长度

        this.sizeCtl = cap;
        //sizeControl:扩容用的控制变量
    }

 

putVal()方法:put()底层调用了putVal()用于插入键值对

final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
     //返回(h ^ (h >>> 16)) & HASH_BITS int binCount = 0; for (Node<K,V>[] tab = table;;) {
       //遍历整个table数组,tab[i]即链表或红黑树的首节点 Node
<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable();
       //如果整个table为空,就初始化这个table;
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
        //table不为空并且长度大于0,并且桶为空
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                  //CompareAndSwap(CAS),如果tab[i]为空就将新的元素替换进去
break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED)
          //如果tab[i]的hash为MOVED,代表需要转移节点 tab
= helpTransfer(tab, f); else { V oldVal = null; synchronized (f) {
            //在每个tab上加私有锁,粒度更细
if (tabAt(tab, i) == f) { if (fh >= 0) {
                 //找到hash大于0的tab[i]节点 binCount
= 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val;
                      //判断hash和key是否相等,相等就保存该点的值
if (!onlyIfAbsent) e.val = value;
                      //将指定值value保存到节点上
break; } Node<K,V> pred = e; if ((e = e.next) == null) {
                      //判断是否为bin的尾节点 pred.next
= new Node<K,V>(hash, key, value, null); break;
                      //若是,就生成一个节点放在尾部,并跳出循环 } } }
else if (f instanceof TreeBin) {
               //如果tab[i]是TreeBin类型,说明这个Bin是红黑树结构,执行红黑树的插入操作 Node
<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i);
            //当tab[i]下的元素大于等于预设阈值8时,就将整个bin转变为红黑树存儲
if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; }

 

replaceNode方法:被remove()底层调用,用于删除节点

final V replaceNode(Object key, V value, Object cv) {
        // 计算key的hash值
        int hash = spread(key.hashCode());
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0 ||
                (f = tabAt(tab, i = (n - 1) & hash)) == null)
          
// table为空或表长度为0或key对应的bin为空或长度为0,直接跳出循环 break; else if ((fh = f.hash) == MOVED) // bin中第一个结点的hash值为MOVED就转移节点 tab = helpTransfer(tab, f); else { V oldVal = null; boolean validated = false; synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { // bin中首节点没有变化,结点hash值大于0 validated = true; for (Node<K,V> e = f, pred = null;;) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { // 结点的hash值与指定的hash值相等,并且key也相等 V ev = e.val; if (cv == null || cv == ev || (ev != null && cv.equals(ev))) { // cv为空或者与结点value相等或者不为空并且相等 // 保存该结点的val值 oldVal = ev; if (value != null) // value为null // 设置结点value值 e.val = value; else if (pred != null) // 前驱不为空 // 前驱的后继为e的后继,即删除了e结点 pred.next = e.next; else // 设置table表中下标为index的值为e.next setTabAt(tab, i, e.next); } break; } pred = e; if ((e = e.next) == null) break; } } else if (f instanceof TreeBin) { // 节点为红黑树结点类型 validated = true; // 类型转化 TreeBin<K,V> t = (TreeBin<K,V>)f; TreeNode<K,V> r, p; if ((r = t.root) != null && (p = r.findTreeNode(hash, key, null)) != null) { // 根节点不为空并且存在与指定hash和key相等的结点 // 保存p结点的value V pv = p.val; if (cv == null || cv == pv || (pv != null && cv.equals(pv))) { // cv为空或者与结点value相等或者不为空并且相等 oldVal = pv; if (value != null) p.val = value; else if (t.removeTreeNode(p)) // 移除p结点 setTabAt(tab, i, untreeify(t.first)); } } } } } if (validated) { if (oldVal != null) { if (value == null) addCount(-1L, -1); return oldVal; } break; } } } return null; }

 

get()方法:获取对应键的值

public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        int h = spread(key.hashCode());
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
       //如果table不是空,且table的长度>0,且bin不为空
if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek)))
          //若表中元素的hash和入参的hash相等,且两者的键一致,就返回该节点的值
return e.val; } else if (eh < 0)
          //若表中节点的hash小于0,就在tab[i]的bin里找相同键的节点,若找到了就返回该节点的值,若没找到,就返回空
return (p = e.find(h, key)) != null ? p.val : null; while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek))))
          //若表中节点的hash大于等于0,就遍历其所有后继节点并判断是否与存在相同的hash和键,有就返回节点的值
return e.val; } } return null; }

 

treeifyBin()方法:用于将链表转化成红黑树的数据结构,考虑到若一个散列桶(bin)中的节点太多,链表存儲的话查找节点的效率就会变成线性,所以在节点数大于一个阈值之后,会将之转化为红黑树,提升查找效率为O(logn)

private final void treeifyBin(Node<K,V>[] tab, int index) {
        Node<K,V> b; int n, sc;
        if (tab != null) {
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
          //表不为空的条件下,表长小于阈值8,就对表进行扩容 tryPresize(n
<< 1); else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
          //表不为空的条件下,bin中存在节点,并且节点的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) {
                 //遍历bin中的所有节点 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;
                   //更新临时节点变量tl } setTabAt(tab, index,
new TreeBin<K,V>(hd));
              //设置table表中的下标为hd } } } } }

 

size()方法:可以看到size()方法内并没有任何的同步机制,故size()所获得的值可能已经是过时的,因此只能仅仅作为一个估计值,尽管在并发环境下用处不大,但仍然可以作为我们权衡利弊的因素

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

 

小结:

  JDK1.8的ConcurrentHashMap相比之前版本的ConcurrentHashMap有很了大的改进与不同,从源码中可以发现,每个同步代码块都是作为每个散列桶(bin)的私有锁来实现线程同步的,故每个bin之间的操作都是可以异步完成的,至于多线程的执行效率方面,就取决于散列桶的数量和散列函数的合理性(节点分配的均匀程度)了.

ConcurrentHashMap带来的结果是,在并发访问的环境下实现更高的系统吞吐量,在单线程环境下损失非常小的性能.并且,它的迭代器并不会抛出ConcurrentModifi-cationException,因此不需要再迭代的时候对容器加锁.

                        ----Java并发编程实战   

 

 

参考资料:

Java并发编程实战

https://www.cnblogs.com/lujiango/p/7580558.html

https://www.cnblogs.com/everSeeker/p/5601861.html

https://www.cnblogs.com/leesf456/p/5453341.html

ConcurrentHashMap比其他并发集合的安全效率要高一些?

ConcurrentHashMap比其他并发集合的安全效率要高一些?

前言
我们知道,ConcurrentHashmap(1.8)这个并发集合框架是线程安全的,当你看到源码的get操作时,会发现get操作全程是没有加任何锁的,这也是这篇博文讨论的问题——为什么它不需要加锁呢?
ConcurrentHashMap的简介
我想有基础的朋友知道在jdk1.7中是采用Segment + HashEntry + ReentrantLock的方式进行实现的,而1.8中放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现。
  • JDK1.8的实现降低锁的粒度,JDK1.7版本锁的粒度是基于Segment的,包含多个HashEntry,而JDK1.8锁的粒度就是HashEntry(首节点)
  • JDK1.8版本的数据结构变得更加简单,使得操作也更加清晰流畅,因为已经使用synchronized来进行同步,所以不需要分段锁的概念,也就不需要Segment这种数据结构了,由于粒度的降低,实现的复杂度也增加了
  • JDK1.8使用红黑树来优化链表,基于长度很长的链表的遍历是一个很漫长的过程,而红黑树的遍历效率是很快的,代替一定阈值的链表,这样形成一个最佳拍档
 
get操作源码
  • 首先计算hash值,定位到该table索引位置,如果是首节点符合就返回
  • 如果遇到扩容的时候,会调用标志正在扩容节点ForwardingNode的find方法,查找该节点,匹配就返回
  • 以上都不符合的话,就往下遍历节点,匹配就返回,否则最后就返回null
//会发现源码中没有一处加了锁 public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; int h = spread(key.hashCode()); //计算hash if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) {//读取首节点的Node元素 if ((eh = e.hash) == h) { //如果该节点就是首节点就返回 if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } //hash值为负值表示正在扩容,这个时候查的是ForwardingNode的find方法来定位到nextTable来 //eh=-1,说明该节点是一个ForwardingNode,正在迁移,此时调用ForwardingNode的find方法去nextTable里找。 //eh=-2,说明该节点是一个TreeBin,此时调用TreeBin的find方法遍历红黑树,由于红黑树有可能正在旋转变色,所以find里会有读写锁。 //eh>=0,说明该节点下挂的是一个链表,直接遍历该链表即可。 else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null; while ((e = e.next) != null) {//既不是首节点也不是ForwardingNode,那就往下遍历 if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; }
get没有加锁的话,ConcurrentHashMap是如何保证读到的数据不是脏数据的呢?
volatile登场
对于可见性,Java提供了volatile关键字来保证可见性、有序性。但不保证原子性。
普通的共享变量不能保证可见性,因为普通共享变量被修改之后,什么时候被写入主存是不确定的,当其他线程去读取时,此时内存中可能还是原来的旧值,因此无法保证可见性。
  • volatile关键字对于基本类型的修改可以在随后对多个线程的读保持一致,但是对于引用类型如数组,实体bean,仅仅保证引用的可见性,但并不保证引用内容的可见性。。
  • 禁止进行指令重排序。
背景:为了提高处理速度,处理器不直接和内存进行通信,而是先将系统内存的数据读到内部缓存(L1,L2或其他)后再进行操作,但操作完不知道何时会写到内存。
  • 如果对声明了volatile的变量进行写操作,JVM就会向处理器发送一条指令,将这个变量所在缓存行的数据写回到系统内存。但是,就算写回到内存,如果其他处理器缓存的值还是旧的,再执行计算操作就会有问题。
  • 在多处理器下,为了保证各个处理器的缓存是一致的,就会实现缓存一致性协议,当某个CPU在写数据时,如果发现操作的变量是共享变量,则会通知其他CPU告知该变量的缓存行是无效的,因此其他CPU在读取该变量时,发现其无效会重新从主存中加载数据。
总结下来:
第一:使用volatile关键字会强制将修改的值立即写入主存;
第二:使用volatile关键字的话,当线程2进行修改时,会导致线程1的工作内存中缓存变量的缓存行无效(反映到硬件层的话,就是CPU的L1或者L2缓存中对应的缓存行无效);
第三:由于线程1的工作内存中缓存变量的缓存行无效,所以线程1再次读取变量的值时会去主存读取。
是加在数组上的volatile吗?
/** * The array of bins. Lazily initialized upon first insertion. * Size is always a power of two. Accessed directly by iterators. */ transient volatile Node<K,V>[] table;
我们知道volatile可以修饰数组的,只是意思和它表面上看起来的样子不同。举个栗子,volatile int array[10]是指array的地址是volatile的而不是数组元素的值是volatile的.
用volatile修饰的Node
get操作可以无锁是由于Node的元素val和指针next是用volatile修饰的,在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; //可以看到这些都用了volatile修饰 volatile V val; volatile Node<K,V> next; Node(int hash, K key, V val, Node<K,V> next) { this.hash = hash; this.key = key; this.val = val; this.next = next; } public final K getKey() { return key; } public final V getValue() { return val; } public final int hashCode() { return key.hashCode() ^ val.hashCode(); } public final String toString(){ return key + "=" + val; } public final V setValue(V value) { throw new UnsupportedOperationException(); } public final boolean equals(Object o) { Object k, v, u; Map.Entry<?,?> e; return ((o instanceof Map.Entry) && (k = (e = (Map.Entry<?,?>)o).getKey()) != null && (v = e.getValue()) != null && (k == key || k.equals(key)) && (v == (u = val) || v.equals(u))); } /** * Virtualized support for map.get(); overridden in subclasses. */ Node<K,V> find(int h, Object k) { Node<K,V> e = this; if (k != null) { do { K ek; if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; } while ((e = e.next) != null); } return null; } }
既然volatile修饰数组对get操作没有效果那加在数组上的volatile的目的是什么呢?
其实就是为了使得Node数组在扩容的时候对其他线程具有可见性而加的volatile
 
总结
  • 在1.8中ConcurrentHashMap的get操作全程不需要加锁,这也是它比其他并发集合比如hashtable、用Collections.synchronizedMap()包装的hashmap;安全效率高的原因之一。
  • get操作全程不需要加锁是因为Node的成员val是用volatile修饰的和数组用volatile修饰没有关系。
  • 数组用volatile修饰主要是保证在数组扩容的时候保证可见性。
最后 欢迎大家一起交流,喜欢文章记得关注我点个赞哟,感谢支持!

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

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 并发分析 —ConcurrentHashMap

Java 并发分析 —ConcurrentHashMap

  LZ 在 https://www.cnblogs.com/xyzyj/p/6696545.html 中简单介绍了 List 和 Map 中的常用集合,唯独没有 CurrentHashMap。原因是 CurrentHashMap 太复杂了,于是新开一篇,将在这里将隆重介绍。

  在 java 中,hashMap 和 hashTable 与 currentHashMap 的关系比较密切,所以 LZ 在这多啰嗦一下,从 hashMap,hashTable 说起,再逐渐过渡到 CurrentHashMap,以便于读者更能清晰地理解它的来龙去脉。

1.hashMap(JDK 1.7)

1.1 hashMap 的数据结构图

  大家都知道 hashmap 的数据结构是由数组 + 链表实现的,如图:

  HashMap 默认的初始化容量是 16,默认加载因子是 0.75。扩容就是把一原 map 结构中的数据一一取出来放在一个更大的 map 结构中,在操作链表时使用的是头插法。在单线程时,扩容是没有问题的,但是在多线程下,会发生线程安全问题。

1.2 HashMap 扩容分析

  扩容源码如下:

void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

 

  其中最主要的是红色部分,把这几句代码摘出来,标上序号,方便后文引用,看下执行过程中会发生什么?

Entry<K,V> next = e.next;  ①
e.next = newTable[i];      ②
newTable[i] = e;           ③
e = next;                  ④

  具体过程举一个例子:

  单线程情况下的扩容情况:

  

  这是一个大小为 2 的 map 结构,其中在下标为 1 的数组上挂了一个长度为 3 的链表,链表中的 3 个 key 分别为 3,5,9 。而这三个 key 都是 mod (2) 以后放在链表中的。造成一个链过程。此时 e 节点指向了 3,next 节点指向了 e 的下一个节点 5 ,现在要将此 map 扩容,则将 mod (2) 变成 mode (4)。单线程执行步骤如下:

(1)执行代码①②后结果:e 指向了新 map 的 3 ,e 的 next 为空。

 

  

(2)循环执行代码④①后的结果:e 指向 5,next 执行 9

  

(3)继续循环执行,链表使用头插法,最终的结果如下:e 指向了 5,next 指向了 null,5 和 9 的顺序发生了反转,和扩容完毕。

  

  在多线程下的扩容情况:

   

 

  同样是上面的 map 结构。有两个线程 A 和线程 B 进行扩容,

(1)线程 A 执行代码①后挂起。此时线程 A 的指针情况如上图,e 指向 3,next 指向 5

(2)此时线程 B 执行扩容,直至线程 B 扩容完毕,新的 map 结构如单线程中的执行结果:

 

  

  在这个时候,线程 A 开始执行,但线程 A 的指针还是挂起之前的状态,为了方便标识,下面用红色标识 A 线程,用绿色标识 B 线程。

 

  如上图,线程 A 在挂起之前 e 指向 3,next,指向 5,并且这两个节点在原 map 上,当 A 挂起后,就像睡了一觉,这是线程 B 将原 map 结构上的节点复制到了新的 mao 结构上,当 A 醒来之后,它的 e 和 next 执行节点没变,但是节点的位置发生了变化,已经在新的 map 上了,因此会出现上图现象,此时 A 开始扩容:

(3)A 执行②③代码,情况和上图一样,没有变化,依然是将 3 节点放在 newtable [3] 上。

(4)A 循环执行④①代码,情况如下;

  e = next;        ④        (3)执行完后的情况如上图,A 的 next 执行 5,所以执行完这行代码后,e 指向 5。

  next = e.next;①         执行完代码④后,e 指向了 5,而在 e 挂起之前,5 的 next 指向了 9,此时 e 的 next 为 9,next = e.next = 9。

(5)A 在执行②③代码后的情况如下:

e.next = newTable[i];      ②  此时e指向5,i等于1,e.next指向9 (线程B扩完容,9的next指向了5)
newTable[i] = e;           ③  此时,新table[1]指向e,即5

  此时出现了环形循环,即死循环。。。

1.3 HashMap 扩容时机

  从上面知道了 HashMap 扩容原理,那么 hashMap 到底是什么时候扩容的呢?

  上面提到过,HashMap 默认的初始化容量是 16,默认加载因子是 0.75,什么意思呢?就是 16*0.75 = 12,即当向 hashMap 中通过 put () 方法存入的数据大于 12 个的时候就会扩容,扩容后的容量为 16*2 = 32 ,举个简单的例子。

public static void main(String[] args) {
        Map map = new HashMap<Integer, Integer>();
        for(int i = 0;i < 12;i++){
            map.put(i, i+1);
        }
}

  这是一个很简单的 put ()操作,然后在扩容源码上打上断点,debug 执行完成,没有任何拦截,过程不再演示,下面将 for 循环中的条件改成 i < 13,debug 当 put 第 13 个键值对的时候,如下图:

    

  从上图可知,当 put 的键值对大于 12 的时候就会进行扩容。

2.hashMap(JDK 1.8)

  在 1.8 中,对 hashmap 做了优化,在 1.7 中,有个很容易发生的问题,就是当发生 hash 冲突的概率比较高时,数组上的某个链表上的数据就会比较多,而其他链表上数据比较少,某个链表将变的非常长,导致查询效率降低。于是,在 1.8 中,当某个链表上的键值对个数达到 8 个时,就会将此链表转化为红黑树,我们知道,红黑树的查询效率非常高,主要是用它来存储有序的数据,它的时间复杂度是 O (lgn),java 集合中的 TreeSet 和 TreeMap 以及 linux 虚拟内存管理就是用红黑树实现的。关于红黑树,这里不再介绍,可以参阅 http://www.360doc.com/content/18/0904/19/25944647_783893127.shtml 。下面看看 hashmap 的源码。

put () 方法源码:

 1  /**
 2      * Implements Map.put and related methods
 3      *
 4      * @param hash hash for key
 5      * @param key the key
 6      * @param value the value to put
 7      * @param onlyIfAbsent if true, don''t change existing value
 8      * @param evict if false, the table is in creation mode.
 9      * @return previous value, or null if none
10      */
11     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
12                    boolean evict) {
13         Node<K,V>[] tab; Node<K,V> p; int n, i;
14         if ((tab = table) == null || (n = tab.length) == 0)
15             n = (tab = resize()).length;
16         if ((p = tab[i = (n - 1) & hash]) == null)
17             tab[i] = newNode(hash, key, value, null);
18         else {
19             Node<K,V> e; K k;
20             if (p.hash == hash &&
21                 ((k = p.key) == key || (key != null && key.equals(k))))
22                 e = p;
23             else if (p instanceof TreeNode)
24                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
25             else {
26                 for (int binCount = 0; ; ++binCount) {
27                     if ((e = p.next) == null) {
28                         p.next = newNode(hash, key, value, null);
29                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
30                             treeifyBin(tab, hash);
31                         break;
32                     }
33                     if (e.hash == hash &&
34                         ((k = e.key) == key || (key != null && key.equals(k))))
35                         break;
36                     p = e;
37                 }
38             }
39             if (e != null) { // existing mapping for key
40                 V oldValue = e.value;
41                 if (!onlyIfAbsent || oldValue == null)
42                     e.value = value;
43                 afterNodeAccess(e);
44                 return oldValue;
45             }
46         }
47         ++modCount;
48         if (++size > threshold)
49             resize();
50         afterNodeInsertion(evict);
51         return null;
52     }

  其中红色部分就是当链表上的键值对大于 8 时,将链表转化为红黑树。TREEIFY_THRESHOLD  的初始化值为 8。

3.hashtable 是线程安全且效率低的

  hashTable 其实和 hashMap 原理相似(1.7,1.8),不同点有四个:

   (1.hashTable是线程安全而 HashMap不是线程安全的。

  (2.HashTable不允许keyvaluenullHashMap允许。

  (3.hashtable初始化大小为11,默认加载因子为0.75,扩容后容量是原来的2倍+1,而hashMap初始化容量大小为16,默认加载因子为0.75
扩容后的容量是原来的2倍。

(4).hashtable计算hash是直接使用keyhashcodetable数组的长度直接进行取模,hashmap计算hashkeyhashcode进行了二次hash
以获得更好的散列值,然后对table数组长度取摸

  实现线程安全的方法则是使用 synchronized 关键字,下面看下 hashtable 部分源码:

public synchronized int size() {
    return count;    
}

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
        V old = e.value;
        e.value = value;
        return old;
        }
    }

    modCount++;
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

            tab = table;
            index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    Entry<K,V> e = tab[index];
    tab[index] = new Entry<K,V>(hash, key, value, e);
    count++;
    return null;
    }

  可以看出,在源码中,在很多方法汇总都插入了 synchronized 关键在保证同步,因此,在扩容时,不会出现多个线程同一时间间隔内扩容,所以不会出现死循环。在 LZ 上篇文中(https://www.cnblogs.com/xyzyj/p/11148497.html)已经详细介绍了 synchronized,它一次只允许一个线程执行锁中的代码,故而,hashtable 是线程安全且效率低的。

  HashMap 中只有一条记录可以是一个空的 key,但任意数量的条目可以是空的 value。如果在表中没有发现搜索键,或者如果发现了搜索键,但它是一个空的值,那么 get () 将返回 null。如果有必要,用 containKey () 方法来区别这两种情况。

  为什么 HashTable 和 ConcurrentHashMap 都不允许 key 和 value 为 null 而 HashMap 允许?

  网上找到的答案是这样的:ConcurrentHashmap 和 Hashtable 都是支持并发的,这样会有一个问题,当你通过 get (k) 获取对应的 value 时,如果获取到的是 null 时,你无法判断,它是 put(k,v)的时候 value 为 null,还是这个 key 从来没有做过映射。HashMap 是非并发的,可以通过 contains (key) 来做这个判断。而支持并发的 Map 在调用 m.contains(key)和 m.get (key),m 可能已经不同了。

4. 优秀的 ConcurrentHashMap

  在涉及到 Java 多线程开发时,如果我们使用 HashMap 可能会导致死锁问题,使用 HashTable 效率又不高。而 ConcurrentHashMap 既可以保持同步也可以提高并发效率,所以这个时候 ConcurrentHashmap 是我们最好的选择。

  CurrentHashMap 底层是一个复杂的数据结构,先看图。

  

  上图就是 ConcurrenthashMap (1.8) 的数据结构图,它是由 Segment 数组和 hashMap 组成的。其中每一个 Segment 都对应一个 hashmap,由 Segment,在 jdk1.7 中,ConcurrentHashMap 使用的 hashmap 是 jdk1.7 中的 hashMap,在 jdk1.8 中,ConcurrentHashMap 使用的 HashMap 是 jdk1.8 中的 hashMap,其原理类似,且 Jdk1.7 中的 hashMap 上文已经做过介绍,故,在此只介绍 1,8 中的 ConcurrentHashMap。

  ConcurrentHashMap 的优点是使用了 Segment 数组,Segment 数组的每一个元素对用一个 hashmap。Segment 继承了 ReentrantLock ,使用 ReentrantLock 对数组某些元素加锁,即只对部分 hashMap 加锁,从而实现了只对需要加锁的的某一段数进行加锁,实现了多线程并发的操作,这种加锁方式就是分段锁

  Segment 继承了 ReentrantLock 的源码如下:

/**
     * Stripped-down version of helper class used in previous version,
     * declared for the sake of serialization compatibility
     */
    static class Segment<K,V> extends ReentrantLock implements Serializable {
        private static final long serialVersionUID = 2249069246763182397L;
        final float loadFactor;
        Segment(float lf) { this.loadFactor = lf; }
    }

 

  一些默认的参数:

/*
     * 最大可能的扩容数量为1 << 30,即2的30次方。
     * 说明:
     * 1.HashMap在确定数组下标Index的时候,采用的是( length-1) & hash的方式,
     *   只有当length为2的指数幂的时候才能较均匀的分布元素
     * 2.由于HashMap规定了其容量是2的n次方,所以我们采用位运算<<来控制HashMap的大小。
     * 使用位运算同时还提高了Java的处理速度。HashMap内部由Entry[]数组构成,
     * Java的数组下标是由Int表示的。所以对于HashMap来说其最大的容量应该是不超过int最大值的一个2的指数幂,
     * 而最接近int最大值的2个指数幂用位运算符表示就是 1 << 30
     */
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    /*
     *  默认初始表容量。 必须是2的幂,(即至少为1)且最多为MAXIMUM_CAPACITY。
     *  所以HashMap规定了其容量必须是2的n次方
     */
    private static final int DEFAULT_CAPACITY = 16;

    /*
     * 最大可能(非幂2)阵列大小,需要使用toArray和相关方法。
     * MAX_VALUE = 0x7fffffff;
     * 数组作为一个对象,需要一定的内存存储对象头信息,对象头信息最大占用内存不可超过8字节
     */
    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /*
     * 此表的默认并发级别。即Segment数组的大小,
     * 也就是默认会创建 16 个箱子,箱子的个数不能太多或太少。
     * 如果太少,很容易触发扩容,如果太多,遍历哈希表会比较慢。
     */
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

    /*
     * 默认加载因子,
     * 当键值对的数量大于 16 * 0.75 = 12 时,就会触发扩容
     */
    private static final float LOAD_FACTOR = 0.75f;

    /*
     * 计数阈值,当链表中的数量大于等于8时,链表转化为红黑树
     * 因为红黑树需要的结点至少为8个
     */
    static final int TREEIFY_THRESHOLD = 8;

    /*
     * 在哈希表扩容时,如果发现链表长度小于 6,则会由树重新退化为链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;

   /*
    * 在转变成树之前,会做一次判断,只有键值对数量大于 64 才会发生转换。
    * 这是为了避免在哈希表建立初期,多个键值对恰好被放入了同一个链表中而导致不必要的转化。
    */
    static final int MIN_TREEIFY_CAPACITY = 64;

   ConcurrentHashMap 和 hashMap 的原理类似,下面是一些重要的类:

  Node:

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;

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

 

Node 类是构造链表或者红黑树的结点的类,主要包含 key,value,hash 和 next。

TreeNode:

static final class TreeNode<K,V> extends Node<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;

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

        Node<K,V> find(int h, Object k) {
            return findTreeNode(h, k, null);
        }

        /**
         * 返回给定键的TreeNode(如果未找到,则返回null)
         * 从给定的根开始。
         */
        final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
            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;
                    if ((ph = p.hash) > h)
                        p = pl;
                    else if (ph < h)
                        p = pr;
                    else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                        return p;
                    else if (pl == null)
                        p = pr;
                    else if (pr == null)
                        p = pl;
                    else if ((kc != null ||
                              (kc = comparableClassFor(k)) != null) &&
                             (dir = compareComparables(kc, k, pk)) != 0)
                        p = (dir < 0) ? pl : pr;
                    else if ((q = pr.findTreeNode(h, k, kc)) != null)
                        return q;
                    else
                        p = pl;
                } while (p != null);
            }
            return null;
        }
    }
TreeNode类是对红黑树的描述,主要方法是返回给定键的TreeNode。
再看put方法:
final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        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();
            //找到具体的数组下标,如果此位置没有值,那么直接初始化一下 Node ,并把值放在这个位置
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            //将结点加入到链表中
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        //将结点加入到红黑树中
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        //如果结点个数大于等于8,则转化为红黑树
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

 

 参考资料:

https://blog.csdn.net/qq_33296156/article/details/82428026

 

 

 

 欢迎关注公众号,不定时更新一些笔记

 

我们今天的关于Java并发(四):并发集合ConcurrentHashMap的源码分析java 并发集合的分享就到这里,谢谢您的阅读,如果想了解更多关于ConcurrentHashMap比其他并发集合的安全效率要高一些?、ConcurrentHashMap源码分析-Java8、HashMap、Hashtable、ConcurrentHashMap、ConcurrentSkipListMap对比及java并发包(java.util.concurrent)、Java 并发分析 —ConcurrentHashMap的相关信息,可以在本站进行搜索。

本文标签: