最近拜读了一些Java Map的相干源码，不得不惊叹于JDK开发者们的巧夺天工。他山之石可以攻玉，这些奇妙的设计思维十分有借鉴价值，堪称是最佳实际。然而，大多数无关Java Map原理的科普类文章都是专一于“点”，并没有连成“线”，甚至造成“网状结构”。因而，本文基于集体了解，对所浏览的局部源码进行了分类与总结，演绎出Map中的几个外围个性，包含：主动扩容、初始化与懒加载、哈希计算、位运算与并发，并联合源码进行深刻解说，心愿看完本文的你也能从中获取到些许播种（本文默认采纳JDK1.8中的HashMap）。

一 主动扩容

最小可用准则，容量超过肯定阈值便主动进行扩容。

扩容是通过resize办法来实现的。扩容产生在putVal办法的最初，即写入元素之后才会判断是否须要扩容操作，当自增后的size大于之前所计算好的阈值threshold，即执行resize操作。

通过位运算<<1进行容量裁减，即扩容1倍，同时新的阈值newThr也扩容为老阈值的1倍。

扩容时，总共存在三种状况：

哈希桶数组中某个地位只有1个元素，即不存在哈希抵触时，则间接将该元素copy至新哈希桶数组的对应地位即可。

哈希桶数组中某个地位的节点为树节点时，则执行红黑树的扩容操作。

哈希桶数组中某个地位的节点为一般节点时，则执行链表扩容操作，在JDK1.8中，为了防止之前版本中并发扩容所导致的死链问题，引入了高下位链表辅助进行扩容操作。

在日常的开发过程中，会遇到一些bad case，比方：

HashMap hashMap = new HashMap(2);
hashMap.put("1", 1);
hashMap.put("2", 2);
hashMap.put("3", 3);

当hashMap设置最初一个元素3的时候，会发现以后的哈希桶数组大小曾经达到扩容阈值2*0.75=1.5，紧接着会执行一次扩容操作，因而，此类的代码每次运行的时候都会进行一次扩容操作，效率低下。在日常开发过程中，肯定要充沛评估好HashMap的大小，尽可能保障扩容的阈值大于存储元素的数量，缩小其扩容次数。

二 初始化与懒加载

初始化的时候只会设置默认的负载因子，并不会进行其余初始化的操作，在首次应用的时候才会进行初始化。

当new一个新的HashMap的时候，不会立刻对哈希数组进行初始化，而是在首次put元素的时候，通过resize()办法进行初始化。

resize()中会设置默认的初始化容量DEFAULT_INITIAL_CAPACITY为16，扩容的阈值为0.75*16 = 12，即哈希桶数组中元素达到12个便进行扩容操作。

最初创立容量为16的Node数组，并赋值给成员变量哈希桶table，即实现了HashMap的初始化操作。

三 哈希计算

哈希表以哈希命名，足以阐明哈希计算在该数据结构中的重要水平。而在实现中，JDK并没有间接应用Object的native办法返回的hashCode作为最终的哈希值，而是进行了二次加工。

以下别离为HashMap与ConcurrentHashMap计算hash值的办法，外围的计算逻辑雷同，都是应用key对应的hashCode与其hashCode右移16位的后果进行异或操作。此处，将高16位与低16位进行异或的操作称之为扰动函数，目标是将高位的特色融入到低位之中，升高哈希抵触的概率。

举个例子来了解下扰动函数的作用：

hashCode(key1) = 0000 0000 0000 1111 0000 0000 0000 0010
hashCode(key2) = 0000 0000 0000 0000 0000 0000 0000 0010

若HashMap容量为4，在不应用扰动函数的状况下，key1与key2的hashCode注定会抵触（后两位雷同，均为01）。

通过扰动函数解决后，可见key1与key2 hashcode的后两位不同，上述的哈希抵触也就防止了。

hashCode(key1) ^ (hashCode(key1) >>> 16)
0000 0000 0000 1111 0000 0000 0000 1101

hashCode(key2) ^ (hashCode(key2) >>> 16)
0000 0000 0000 0000 0000 0000 0000 0010

这种增益会随着HashMap容量的缩小而减少。《An introduction to optimising a hashing strategy》文章中随机选取了哈希值不同的352个字符串，当HashMap的容量为2^9时，应用扰动函数能够缩小10%的碰撞，可见扰动函数的必要性。

此外，ConcurrentHashMap中通过扰乱函数解决之后，须要与HASH_BITS做与运算，HASH_BITS为0x7ffffff，即只有最高位为0，这样运算的后果使hashCode永远为负数。在ConcurrentHashMap中，预约义了几个非凡节点的hashCode，如：MOVED、TREEBIN、RESERVED，它们的hashCode均定义为负值。因而，将一般节点的hashCode限定为负数，也就是为了避免与这些非凡节点的hashCode产生抵触。

1 哈希抵触

通过哈希运算，能够将不同的输出值映射到指定的区间范畴内，随之而来的是哈希抵触问题。思考一个极其的case，假如所有的输出元素通过哈希运算之后，都映射到同一个哈希桶中，那么查问的复杂度将不再是O(1)，而是O(n)，相当于线性表的程序遍历。因而，哈希抵触是影响哈希计算性能的重要因素之一。哈希抵触如何解决呢？次要从两个方面思考，一方面是防止抵触，另一方面是在抵触时正当地解决抵触，尽可能进步查问效率。前者在下面的章节中曾经进行介绍，即通过扰动函数来减少hashCode的随机性，防止抵触。针对后者，HashMap中给出了两种计划：拉链表与红黑树。

拉链表

在JDK1.8之前，HashMap中是采纳拉链表的办法来解决抵触，即当计算出的hashCode对应的桶上曾经存在元素，但两者key不同时，会基于桶中已存在的元素拉出一条链表，将新元素链到已存在元素的后面。当查问存在抵触的哈希桶时，会程序遍历抵触链上的元素。同一key的判断逻辑如下图所示，先判断hash值是否雷同，再比拟key的地址或值是否雷同。

（1）死链

在JDK1.8之前，HashMap在并发场景下扩容时存在一个bug，造成死链，导致get该地位元素的时候，会死循环，使CPU利用率高居不下。这也阐明了HashMap不适于用在高并发的场景，高并发应该优先思考JUC中的ConcurrentHashMap。然而，精益求精的JDK开发者们并没有抉择绕过问题，而是抉择直面问题并解决它。在JDK1.8之中，引入了高下位链表（双端链表）。

什么是高下位链表呢？在扩容时，哈希桶数组buckets会扩容一倍，以容量为8的HashMap为例，原有容量8扩容至16，将[0, 7]称为低位，[8, 15]称为高位，低位对应loHead、loTail，高位对应hiHead、hiTail。

扩容时会顺次遍历旧buckets数组的每一个地位下面的元素：

若不存在抵触，则从新进行hash取模，并copy到新buckets数组中的对应地位。

若存在抵触元素，则采纳高下位链表进行解决。通过e.hash & oldCap来判断取模后是落在高位还是低位。举个例子：假如以后元素hashCode为0001（疏忽高位），其运算后果等于0，阐明扩容后后果不变，取模后还是落在低位[0, 7]，即0001 & 1000 = 0000，还是原地位，再用低位链表将这类的元素链接起来。假如以后元素的hashCode为1001， 其运算后果不为0，即1001 & 1000 = 1000 ，扩容后会落在高位，新的地位刚好是旧数组索引（1） + 旧数据长度（8） = 9，再用高位链表将这些元素链接起来。最初，将高下位链表的头节点别离放在扩容后数组newTab的指定地位上，即实现了扩容操作。这种实现升高了对共享资源newTab的拜访频次，先组织抵触节点，最初再放入newTab的指定地位。防止了JDK1.8之前每遍历一个元素就放入newTab中，从而导致并发扩容下的死链问题。

红黑树

在JDK1.8之中，HashMap引入了红黑树来解决哈希抵触问题，而不再是拉链表。那么为什么要引入红黑树来代替链表呢？尽管链表的插入性能是O(1)，但查问性能确是O(n)，当哈希抵触元素十分多时，这种查问性能是难以承受的。因而，在JDK1.8中，如果抵触链上的元素数量大于8，并且哈希桶数组的长度大于64时，会应用红黑树代替链表来解决哈希抵触，此时的节点会被封装成TreeNode而不再是Node（TreeNode其实继承了Node，以利用多态个性），使查问具备O(logn)的性能。

这里简略地回顾一下红黑树，它是一种均衡的二叉树搜寻树，相似地还有AVL树。两者外围的区别是AVL树谋求“相对均衡”，在插入、删除节点时，老本要高于红黑树，但也因而领有了更好的查问性能，实用于读多写少的场景。然而，对于HashMap而言，读写操作其实难分伯仲，因而抉择红黑树也算是在读写性能上的一种折中。

四 位运算

1 确定哈希桶数组大小

找到大于等于给定值的最小2的整数次幂。

tableSizeFor依据输出容量大小cap来计算最终哈希桶数组的容量大小，找到大于等于给定值cap的最小2的整数次幂。乍眼一看，这一行一行的位运算让人云里雾里，莫不如采纳相似找法则的形式来摸索其中的神秘。

当cap为3时，计算过程如下：

cap = 3
n = 2
n |= n >>> 1 010 | 001 = 011 n = 3
n |= n >>> 2 011 | 000 = 011 n = 3
n |= n >>> 4 011 | 000 = 011 n = 3
….
n = n + 1 = 4

当cap为5时，计算过程如下：

cap = 5
n = 4
n |= n >>> 1 0100 | 0010 = 0110 n = 6
n |= n >>> 2 0110 | 0001 = 0111 n = 7
….
n = n + 1 = 8

因而，计算的意义在于找到大于等于cap的最小2的整数次幂。整个过程是找到cap对应二进制中最高位的1，而后每次以2倍的步长（顺次移位1、2、4、8、16）复制最高位1到前面的所有低位，把最高位1前面的所有位全副置为1，最初进行+1，即实现了进位。

相似二进制位的变动过程如下：

0100 1010
0111 1111
1000 0000

找到输出cap的最小2的整数次幂作为最终容量能够了解为最小可用准则，尽可能地少占用空间，然而为什么必须要2的整数次幂呢？答案是，为了进步计算与存储效率，使每个元素对应hash值可能精确落入哈希桶数组给定的范畴区间内。确定数组下标采纳的算法是 hash & (n - 1)，n即为哈希桶数组的大小。因为其总是2的整数次幂，这意味着n-1的二进制模式永远都是0000111111的模式，即从最低位开始，间断呈现多个1，该二进制与任何值进行&运算都会使该值映射到指定区间[0, n-1]。比方：当n=8时，n-1对应的二进制为0111，任何与0111进行&运算都会落入[0,7]的范畴内，即落入给定的8个哈希桶中，存储空间利用率100%。举个反例，当n=7，n-1对应的二进制为0110，任何与0110进行&运算会落入到第0、6、4、2个哈希桶，而不是[0,6]的区间范畴内，少了1、3、5三个哈希桶，这导致存储空间利用率只有不到60%，同时也减少了哈希碰撞的几率。

2 ASHIFT偏移量计算

获取给定值的最高有效位数（移位除了可能进行乘除运算，还能用于保留高、低位操作，右移保留高位，左移保留低位）。

ConcurrentHashMap中的ABASE+ASHIFT是用来计算哈希数组中某个元素在理论内存中的初始地位，ASHIFT采取的计算形式是31与scale前导0的数量做差，也就是scale的理论位数-1。scale就是哈希桶数组Node[]中每个元素的大小，通过((long)i << ASHIFT) + ABASE)进行计算，便可失去数组中第i个元素的起始内存地址。

咱们持续看下前导0的数量是怎么计算出来的，numberOfLeadingZeros是Integer的静态方法，还是沿用找法则的形式一探到底。

假如 i = 0000 0000 0000 0100 0000 0000 0000 0000，n = 1

i >>> 16 0000 0000 0000 0000 0000 0000 0000 0100 不为0

i >>> 24 0000 0000 0000 0000 0000 0000 0000 0000 等于0

右移了24位等于0，阐明24位到31位之间必定全为0，即n = 1 + 8 = 9，因为高8位全为0，并且曾经将信息记录至n中，因而能够舍弃高8位，即 i <<= 8。此时，

i = 0000 0100 0000 0000 0000 0000 0000 0000

相似地，i >>> 28 也等于0，阐明28位到31位全为0，n = 9 + 4 = 13，舍弃高4位。此时，

i = 0100 0000 0000 0000 0000 0000 0000 0000

持续运算，

i >>> 30 0000 0000 0000 0000 0000 0000 0000 0001 不为0
i >>> 31 0000 0000 0000 0000 0000 0000 0000 0000 等于0

最终可得出n = 13，即有13个前导0。n -= i >>> 31是查看最高位31位是否是1，因为n初始化为1，如果最高位是1，则不存在前置0，即n = n - 1 = 0。

总结一下，以上的操作其实是基于二分法的思维来定位二进制中1的最高位，先看高16位，若为0，阐明1存在于低16位；反之存在高16位。由此将搜寻范畴由32位（确切的说是31位）缩小至16位，进而再一分为二，校验高8位与低8位，以此类推。

计算过程中校验的位数顺次为16、8、4、2、1，加起来刚好为31。为什么是31不是32呢？因为前置0的数量为32的状况下i只能为0，在后面的if条件中曾经进行过滤。这样一来，非0值的状况下，前置0只能呈现在高31位，因而只须要校验高31位即可。最终，用总位数减去计算出来的前导0的数量，即可得出二进制的最高有效位数。代码中应用的是31 - Integer.numberOfLeadingZeros(scale)，而不是总位数32，这是为了可能失去哈希桶数组中第i个元素的起始内存地址，不便进行CAS等操作。

五 并发

1 乐观锁

全表锁

HashTable中采纳了全表锁，即所有操作均上锁，串行执行，如下图中的put办法所示，采纳synchronized关键字润饰。这样尽管保障了线程平安，然而在多核处理器时代也极大地影响了计算性能，这也以致HashTable逐步淡出开发者们的视线。

分段锁

针对HashTable中锁粒度过粗的问题，在JDK1.8之前，ConcurrentHashMap引入了分段锁机制。整体的存储构造如下图所示，在原有构造的根底上拆分出多个segment，每个segment下再挂载原来的entry（上文中常常提到的哈希桶数组），每次操作只须要锁定元素所在的segment，不须要锁定整个表。因而，锁定的范畴更小，并发度也会失去晋升。

2 乐观锁

Synchronized+CAS

尽管引入了分段锁的机制，即能够保障线程平安，又能够解决锁粒度过粗导致的性能低下问题，然而对于谋求极致性能的工程师来说，这还不是性能的天花板。因而，在JDK1.8中，ConcurrentHashMap摒弃了分段锁，应用了乐观锁的实现形式。放弃分段锁的起因次要有以下几点：

应用segment之后，会减少ConcurrentHashMap的存储空间。

当单个segment过大时，并发性能会急剧下降。

ConcurrentHashMap在JDK1.8中的实现废除了之前的segment构造，沿用了与HashMap中的相似的Node数组构造。

ConcurrentHashMap中的乐观锁是采纳synchronized+CAS进行实现的。这里次要看下put的相干代码。

当put的元素在哈希桶数组中不存在时，则间接CAS进行写操作。

这里波及到了两个重要的操作，tabAt与casTabAt。能够看出，这外面都应用了Unsafe类的办法。Unsafe这个类在日常的开发过程中比拟常见。咱们通常对Java语言的认知是：Java语言是平安的，所有操作都基于JVM，在平安可控的范畴内进行。然而，Unsafe这个类会突破这个边界，使Java领有C的能力，能够操作任意内存地址，是一把双刃剑。这里应用到了前文中所提到的ASHIFT，来计算出指定元素的起始内存地址，再通过getObjectVolatile与compareAndSwapObject别离进行取值与CAS操作。

在获取哈希桶数组中指定地位的元素时为什么不能间接get而是要应用getObjectVolatile呢？因为在JVM的内存模型中，每个线程有本人的工作内存，也就是栈中的局部变量表，它是主存的一份copy。因而，线程1对某个共享资源进行了更新操作，并写入到主存，而线程2的工作内存之中可能还是旧值，脏数据便产生了。Java中的volatile是用来解决上述问题，保障可见性，任意线程对volatile关键字润饰的变量进行更新时，会使其它线程中该变量的正本生效，须要从主存中获取最新值。尽管ConcurrentHashMap中的Node数组是由volatile润饰的，能够保障可见性，然而Node数组中元素是不具备可见性的。因而，在获取数据时通过Unsafe的办法间接到主存中拿，保障获取的数据是最新的。

持续往下看put办法的逻辑，当put的元素在哈希桶数组中存在，并且不处于扩容状态时，则应用synchronized锁定哈希桶数组中第i个地位中的第一个元素f（头节点2），接着进行double check，相似于DCL单例模式的思维。校验通过后，会遍历以后抵触链上的元素，并抉择适合的地位进行put操作。此外，ConcurrentHashMap也沿用了HashMap中解决哈希抵触的计划，链表+红黑树。这里只有在产生哈希抵触的状况下才应用synchronized锁定头节点，其实是比分段锁更细粒度的锁实现，只在特定场景下锁定其中一个哈希桶，升高锁的影响范畴。

Java Map针对并发场景解决方案的演进方向能够归结为，从乐观锁到乐观锁，从粗粒度锁到细粒度锁，这也能够作为咱们在日常并发编程中的指导方针。

3 并发求和

CounterCell是JDK1.8中引入用来并发求和的利器，而在这之前采纳的是【尝试无锁求和】+【抵触时加锁重试】的策略。看下CounterCell的正文，它是改编自LongAdder和Striped64。咱们先看下求和操作，其实就是取baseCount作为初始值，而后遍历CounterCell数组中的每一个cell，将各个cell的值进行累加。这里额定阐明下@sun.misc.Contender注解的作用，它是Java8中引入用来解决缓存行伪共享问题的。什么是伪共享呢？简略说下，思考到CPU与主存之间速度的微小差别，在CPU中引入了L1、L2、L3多级缓存，缓存中的存储单位是缓存行，缓存行大小为2的整数次幂字节，32-256个字节不等，最常见的是64字节。因而，这将导致有余64字节的变量会共享同一个缓存行，其中一个变量生效会影响到同一个缓存行中的其余变量，以致性能降落，这就是伪共享问题。思考到不同CPU的缓存行单位的差异性，Java8中便通过该注解将这种差异性屏蔽，依据理论缓存行大小来进行填充，使被润饰的变量可能独占一个缓存行。

再来看下CounterCell是如何实现计数的，每当map中的容量有变动时会调用addCount进行计数，外围逻辑如下：

当counterCells不为空，或counterCells为空且对baseCount进行CAS操作失败时进入到后续计数解决逻辑，否则对baseCount进行CAS操作胜利，间接返回。

后续计数解决逻辑中会调用外围计数办法fullAddCount，但须要满足以下4个条件中的任意一个：1、counterCells为空；2、counterCells的size为0；3、counterCells对应地位上的counterCell为空；4、CAS更新counterCells对应地位上的counterCell失败。这些条件背地的语义是，当前情况下，计数曾经或已经呈现过并发抵触，须要优先借助于CounterCell来解决。若counterCells与对应地位上的元素曾经初始化（条件4），则先尝试CAS进行更新，若失败则调用fullAddCount持续解决。若counterCells与对应地位上的元素未初始化实现（条件1、2、3），也要调用AddCount进行后续解决。

这里确定cell下标时采纳了ThreadLocalRandom.getProbe()作为哈希值，这个办法返回的是以后Thread中threadLocalRandomProbe字段的值。而且当哈希值抵触时，还能够通过advanceProbe办法来更换哈希值。这与HashMap中的哈希值计算逻辑不同，因为HashMap中要保障同一个key进行屡次哈希计算的哈希值雷同并且能定位到对应的value，即使两个key的哈希值抵触也不能轻易更换哈希值，只能采纳链表或红黑树解决抵触。然而在计数场景，咱们并不需要保护key-value的关系，只须要在counterCells中找到一个适合的地位放入计数cell，地位的差别对最终的求和后果是没有影响的，因而当抵触时能够基于随机策略更换一个哈希值来防止抵触。

接着，咱们来看下外围计算逻辑fullAddCount，代码还是比拟多的，外围流程是通过一个死循环来实现的，循环体中蕴含了3个解决分支，为了不便解说我将它们顺次定义A、B、C。

A：示意counterCells曾经初始化实现，因而能够尝试更新或创立对应地位的CounterCell。

B：示意counterCells未初始化实现，且无抵触（拿到cellsBusy锁），则加锁初始化counterCells，初始容量为2。

C：示意counterCells未初始化实现，且有抵触（未能拿到cellsBusy锁），则CAS更新baseCount，baseCount在求和时也会被算入到最终后果中，这也相当于是一种兜底策略，既然counterCells正在被其余线程锁定，那以后线程也没必要再期待了，间接尝试应用baseCount进行累加。

其中，A分支中波及到的操作又能够拆分为以下几点：

a1：对应地位的CounterCell未创立，采纳锁+Double Check的策略尝试创立CounterCell，失败的话则continue进行重试。这外面采纳的锁是cellsBusy，它保障创立CounterCell并放入counterCells时肯定是串行执行，防止反复创立，其实就是应用了DCL单例模式的策略。在CounterCells的创立、扩容中都须要应用该锁。

a2：冲突检测，变量wasUncontended是调用方addCount中传入的，示意前置的CAS更新cell失败，有抵触，须要更换哈希值【a7】后持续重试。

a3：对应地位的CounterCell不为空，间接CAS进行更新。

a4：
冲突检测，当counterCells的援用值不等于以后线程对应的援用值时，阐明有其余线程更改了counterCells的援用，呈现抵触，则将collide设为false，下次迭代时可进行扩容。
容量限度，counterCells容量的最大值为大于等于NCPU（理论机器CPU外围的数量）的最小2的整数次幂，当达到容量限度时前面的扩容分支便永远不会执行。这里限度的意义在于，实在并发度是由CPU外围来决定，当counterCells容量与CPU外围数量相等时，现实状况下就算所有CPU外围在同时运行不同的计数线程时，都不应该呈现抵触，每个线程抉择各自的cell进行解决即可。如果呈现抵触，肯定是哈希值的问题，因而采取的措施是从新计算哈希值a7，而不是通过扩容来解决。工夫换空间，防止不必要的存储空间节约，十分赞的想法~

a5：更新扩容标记位，下次迭代时将会进行扩容。

a6：进行加锁扩容，每次扩容1倍。

a7：更换哈希值。

private final void fullAddCount(long x, boolean wasUncontended) {

    int h;    // 初始化probe    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;        // 【A】counterCells曾经初始化结束        if ((as = counterCells) != null && (n = as.length) > 0) {            // 【a1】对应地位的CounterCell未创立            if ((a = as[(n - 1) & h]) == null) {                // cellsBusy其实是一个锁，cellsBusy=0时示意无抵触                if (cellsBusy == 0) {            // Try to attach new Cell                    // 创立新的CounterCell                    CounterCell r = new CounterCell(x); // Optimistic create                    // Double Check，加锁（通过CAS将cellsBusy设置1）                    if (cellsBusy == 0 &&                        U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {                        boolean created = false;                        try {               // Recheck under lock                            CounterCell[] rs; int m, j;                            // Double Check                            if ((rs = counterCells) != null &&                                (m = rs.length) > 0 &&                                rs[j = (m - 1) & h] == null) {                                // 将新创建的CounterCell放入counterCells中                                rs[j] = r;                                created = true;                            }                        } finally {                            // 解锁，这里为什么不必CAS？因为以后流程中须要在获取锁的前提下进行，即串行执行，因而不存在并发更新问题，只须要失常更新即可                            cellsBusy = 0;                        }                        if (created)                            break;                        // 创立失败则重试                        continue;           // Slot is now non-empty                    }                }                // cellsBusy不为0，阐明被其余线程争抢到了锁，还不能思考扩容                collide = false;            }            //【a2】冲突检测            else if (!wasUncontended)       // CAS already known to fail                // 调用方addCount中CAS更新cell失败，有抵触，则持续尝试CAS                wasUncontended = true;      // Continue after rehash            //【a3】对应地位的CounterCell不为空，间接CAS进行更新            else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))                break;            //【a4】容量限度            else if (counterCells != as || n >= NCPU)                // 阐明counterCells容量的最大值为大于NCPU（理论机器CPU外围的数量）最小2的整数次幂。                // 这里限度的意义在于，并发度是由CPU外围来决定，当counterCells容量与CPU外围数量相等时，实践上讲就算所有CPU外围都在同时运行不同的计数线程时，都不应该呈现抵触，每个线程抉择各自的cell进行解决即可。如果呈现抵触，肯定是哈希值的问题，因而采取的措施是从新计算哈希值（h = ThreadLocalRandom.advanceProbe(h)），而不是通过扩容来解决                // 当n大于NCPU时前面的分支就不会走到了                collide = false;            // At max size or stale            // 【a5】更新扩容标记位            else if (!collide)                // 阐明映射到cell地位不为空，并且尝试进行CAS更新时失败了，则阐明有竞争，将collide设置为true，下次迭代时执行前面的扩容操作，升高竞争度                // 有竞争时，执行rehash+扩容，当容量大于CPU外围时则进行扩容只进行rehash                collide = true;            // 【a6】加锁扩容            else if (cellsBusy == 0 &&                     U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {                // 加锁扩容                try {                    if (counterCells == as) {// Expand table unless stale                        // 扩容1倍                        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            }            //【a7】更换哈希值            h = ThreadLocalRandom.advanceProbe(h);        }        // 【B】counterCells未初始化实现，且无抵触，则加锁初始化counterCells        else if (cellsBusy == 0 && counterCells == as &&                 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {            boolean init = false;            try {                           // Initialize table                if (counterCells == as) {                    CounterCell[] rs = new CounterCell[2];                    rs[h & 1] = new CounterCell(x);                    counterCells = rs;                    init = true;                }            } finally {                cellsBusy = 0;            }            if (init)                break;        }        // 【C】counterCells未初始化实现，且有抵触，则CAS更新baseCount        else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))            break;                          // Fall back on using base    }

CounterCell的设计很奇妙，它的背地其实就是JDK1.8中的LongAdder。核心思想是：在并发较低的场景下间接采纳baseCount累加，否则联合counterCells，将不同的线程散列到不同的cell中进行计算，尽可能地确保拜访资源的隔离，缩小抵触。LongAdder相比拟于AtomicLong中无脑CAS的策略，在高并发的场景下，可能缩小CAS重试的次数，进步计算效率。

六 结语

以上可能只是Java Map源码中的冰山一角，然而根本包含了大部分的外围个性，涵盖了咱们日常开发中的大部分场景。读源码跟读书一样，好像逾越了历史长河与作者进行近距离对话，琢磨他的心理，学习他的思维并加以传承。信息加工转化为常识并使用的过程是苦楚!