concurrenthashmap详解,concurrenthashmap1.8原理

　　Yyds干货库存

　　ConcurrentHashMap原理是面试中的高频知识点，属于第一阶段。

　　如果回答了，那么面试官可能会问，如何提高ConcurrentHashMap的插入效率？于是一个接一个的连环提问开始了，直到你水落石出才停止。

　　今天我们用一篇文章把ConcurrentHashMap解释清楚，帮助你在面试时从容不迫，从容应对。

　　1.ConcurrentHashMap原理概述ConcurrentHashMap是一个用于存储键/值对的容器，它是线程安全的。我们先来看看ConcurrentHashMap的存储结构，如下图所示：

　　这是数组加链表的经典形式。并且当链表长度过长时，会转换成红黑树存储(Java 8的优化)来加快查找速度。

　　存储结构定义了容器的“形状”。集装箱内的物品应该按照什么规则摆放？换句话说，一个键是按照什么逻辑放在容器的相应位置的？

　　我们假设要存放的密钥是对象x，这个过程如下：

　　通过其hashCode()方法获取对象x的hashCode；将hashCode映射到数组中的一个位置；将此元素存储在链表中的此位置。从容器中获取数据的逻辑如下：

　　通过其hashCode()方法获取对象x的hashCode；将hashCode映射到数组中的一个位置；遍历这个位置的链表或者从红黑树中找到匹配的对象并返回。这个数组链表的存储结构其实就是一个哈希表。

　　将对象X映射到数组中某个位置的函数叫做hash函数。

　　这个函数的质量决定了元素在哈希表中的分布是否均匀。如果元素都堆叠在一个位置，那么取值时就需要遍历一个长链表。

　　但如果元素均匀分布在数组中，链表会更短，通过哈希函数定位位置后可以快速找到对应的元素。

　　我们将在后面详细讨论如何在ConcurrentHashMap中实现hash函数。

　　扩大电信容量

　　我们对ConcurrentHashMap的存储结构有了一个大致的了解。

　　那我们来思考一个问题。当数组中存储的链表越来越多时，那么再次存储的元素将大概率被插入到已有的链表中，而不是使用数组中剩余的空间。

　　这样会导致数组中存储的链表越来越长，会减缓哈希表的搜索速度，并使链表的时间复杂度从O (1)逐渐趋近于O (n/2)，这显然违背了哈希表的初衷。

　　因此，ConcurrentHashMap会做一个叫做expansion的操作。

　　也就是说增加数组的长度，增加更多的空位。最终目的是防止链表过长，使搜索的时间复杂度趋于O (1)。

　　数组为空时不会进行扩展操作，因为当桶快满时，新保存的元素有较大概率命中已经使用的位置，所以最后几个桶可能很难使用，而链表越来越长。ConcurrentHashMap会在更合适的时候展开，通常是在数组中75%的位置被使用的时候。

　　此外，ConcurrentHashMap还会有将链表转换为红黑树的操作，以加快搜索速度。红黑树的时间复杂度是O (logn)，而链表是O (n/2)，所以只有在O (logn) O (n/2)，也就是以8为分界点时才会进行转换。

　　其实上面的内容和HashMap差不多。另外，ConcurrentHashMap提供了线程安全的保证，主要通过CAS和Synchronized关键字来实现。让我们在源代码分析中详细看看。

　　我们来做个总结：

　　ConcurrentHashMap采用数组链表红黑树的存储结构；存储的键值通过自己的hashCode映射到数组的对应位置；为了保证查询效率，ConcurrentHashMap会增加特定时间的数据长度。这种操作称为扩展。当链表的长度增加到8时，可能会触发链表转换为红黑树(如果数组长度小于64，首选扩展，详见后面的源代码分析)。接下来，我们从以下几个方面分析源代码：ConcurrentHashMap的组成、保存元素、哈希算法、扩展、searc

　　2.ConcurrentHashMap 2.1重要属性的构成我们来看看ConcurrentHashMap的几个重要属性。

　　1、暂态易变节点K，V []表

　　这个节点数组是ConcurrentHashMap用来存储数据的哈希表。

　　2、私有静态final int DEFAULT _ CAPACITY=16

　　这是默认的初始化哈希表数组大小。

　　3、静态最终int TREEIFY_THRESHOLD=8

　　转换为红黑树的链表长度的阈值

　　4、静态最终int MOVED=-1

　　该标识位用于标识容量扩展期间正在传输的数据。

　　5、静态final int HASH _ BITS=0x7fffffff

　　用于计算哈希值以删除符号位的参数。

　　6、私有瞬态易变节点K，V[]next table；

　　当传输数据时，一个新的哈希表数组

　　可能有些属性你看了解释还是很困惑。没关系，我们后面分析源代码的时候，会相应解释具体用到的地方。

　　2.2重要元素节点

　　链表中的元素是节点对象。他是链表中的一个节点，链表内部存储了键值，以及他的下一个节点的引用。这样，一系列节点被串在一起形成一个链表。

　　转发节点

　　扩展时，链表应该迁移到新的哈希表中。执行此操作时，数组中的头节点将被ForwardingNode对象替换。ForwardingNode不保存键和值，只保存扩展哈希表(nextTable)的引用。此时，在搜索对应的节点时，需要在nextTable中进行搜索。

　　TreeBin

　　当链表变成红黑树时，数组中保存的引用是TreeBin，key/value不保存在TreeBin中，但是保存TreeNode的列表和红黑树的根。

　　TreeNode

　　黑树的节点。

　　3.put方法源代码分析put方法用于在map中存储一个键值对。代码如下：

　　公共V put(K键，V值){

　　返回putVal(key，value，false)；

　　}实际调用的是putVal方法，第三个参数传入的是false，control键覆盖了原来存在的值。

　　接下来我们来看看putVal的代码。代码很多，所以我把解释直接放到代码里：

　　最终V输出值(K键，V值，仅布尔型，如果不存在){

　　//键和值不能为空

　　if (key==null value==null)抛出新的NullPointerException()；

　　//计算密钥的哈希值。我们将在后面研究spread方法的实现。

　　int hash=spread(key . hashcode())；

　　int bin count=0；

　　//开始旋转，表属性采取惰性加载，第一次放的时候初始化。

　　for(节点K，V [] tab=表；) {

　　节点K，V int n，I，FH；

　　//如果该表未初始化，则初始化该表

　　if(tab==null (n=tab . length)==0)

　　tab=init table()；

　　//通过key的哈希值映射表的位置。如果这个位置的值为空，则生成一个新的节点来存储这个键和值，放在这个位置。

　　else if ((f=tabAt(tab，i=(n - 1) hash))==null) {

　　if (casTabAt(tab，I，null，

　　新节点K，V(哈希，键，值，空)))

　　打破；//添加到空箱时不锁定

　　}

　　//如果移动了该位置的节点元素的哈希值，即-1，则表示正在进行扩展复制。然后线程参与复制工作。

　　else if ((fh=f.hash)==MOVED)

　　tab=helpTransfer(tab，f)；

　　//下面的分支处理在表映射的位置已经存在一个节点的情况。

　　否则{

　　V oldVal=null

　　同步(f) {

　　//再次确认该位置的值是否发生了变化。

　　if (tabAt(tab，i)==f) {

　　//fh大于0，表示链表存储在这个位置。

　　如果(fh=0) {

　　bin count=1；

　　//遍历链表

　　for(节点K，V e=f；binCount) {

　　K ek

　　//如果有相同哈希值的节点，根据onlyIfAbsent的值选择是否覆盖该值。

　　如果(例如，哈希==哈希

　　((ek=e.key)==key

　　(ek！=null key.equals(ek)))) {

　　oldVal=e.val

　　如果(！onlyIfAbsent)

　　e.val=值；

　　打破；

　　}

　　节点K，V pred=e；

　　//如果找到最后一个元素，没有找到相同hash的节点，那么生成一个新的节点存储key/value，作为尾节点放入链表。

　　if ((e=e.next)==null) {

　　pred.next=新节点K，V (hash，key，

　　值，null)；

　　打破；

　　}

　　}

　　}

　　//下面的逻辑处理链表转换为红黑树时的键/值保存。

　　else if (f instanceof TreeBin) {

　　节点K，V

　　bin count=2；

　　if ((p=((TreeBin K，V )f))。putTreeVal(哈希，键，

　　值))！=null) {

　　oldVal=p.val

　　如果(！onlyIfAbsent)

　　p.val=值；

　　}

　　}

　　}

　　}

　　//保存//节点后，判断链表长度是否已经超过阈值，然后展开哈希表或将链表转换为红黑树。

　　if (binCount！=0) {

　　if (binCount=TREEIFY_THRESHOLD)

　　treeifyBin(tab，I)；

　　如果(oldVal！=空)

　　返回oldVal

　　打破；

　　}

　　}

　　}

　　//Count，并判断哈希表使用的桶是否超过阈值，如果是，则扩展容量。

　　addCount(1L，宾count)；

　　返回null

　　}主线流程梳理如下：

　　其实put的核心思想就在这里。接下来，我们分别来看看关键节点的方法源代码。

　　4.spread method源代码分析hash算法的逻辑，决定了ConcurrentHashMap的保存和读取速度。哈希算法是hashmap的核心算法，JDK的实现非常巧妙，值得学习。

　　Spreed方法源代码如下：

　　静态最终int spread(int h) {

　　return(h ^(h 16))hash _ bits；

　　}传递的参数h是key对象的hashCode，spreed方法处理hashCode。再次计算哈希。我们暂且不分析这行代码的逻辑，让我们继续往下看如何使用这个哈希值。

　　哈希值用于映射哈希表中键值的位置。取出哈希表中哈希值对应位置的代码如下。

　　tabAt(tab，i=(n - 1) hash)

　　我们先来看看这行代码的逻辑。第一个参数是哈希表，第二个参数是哈希表中的数组下标。

　　通过(n-1)散列计算下标。

　　n是数组长度。我们以默认大小16为例。那么n-1=15。我们可以假设哈希值为100。那么15 100是多少呢？

　　将其左右值转换为二进制，并执行按位and运算。只有两个值是1，一个是0，就是0。

　　然后我们把15和100转换成二进制来计算。在java中，int类型是8个字节，总共32位。

　　n的值15被转换成二进制：

　　0000 0000 0000 0000 0000 0000 0000 1111

　　哈希值100被转换为二进制：

　　0000 0000 0000 0000 0000 0000 0110 0100。

　　计算结果：

　　0000 0000 0000 0000 0000 0000 0000 0100

　　对应的十进制值是4。

　　你看到什么了吗？

　　15的二进制高位都是0，低位都是1。

　　然后经过计算，哈希值100的高位全部清零，低位保持不变，必须小于(n-1)。

　　也就是说，经过这样的计算，通过哈希值得到的数组下标永远不会越界。

　　这里我问两个问题：

　　1.数组大小可以是17，或者18吗？

　　2.为什么不用%来计算余数，以保证不越界？

　　3.为什么不直接用key的hashCode，而是用spreed方法处理的hash值？

　　这些问题在面试中经常被问到。让我们逐一回答。

　　4.1数组大小必须是2的n次方。第一个问题的答案是数组大小必须是2的n次方，即16，32，64.它不能是任何其他值。

　　如果不是2的n次方，那么计算出来的数组下标会增加碰撞的概率。例如，如果数组长度为21，则n-1=20，相应的二进制数为：

　　10100

　　那么如果哈希值的二进制是10000(十进制16)、10010(十进制18)、10001(十进制17)、10100，那么都是10000，也就是都映射到数组16的下标。这三个值将以链表的形式存储在数组中下标16的位置。这显然不是我们想要的结果。

　　但是如果数组长度n是2的n次方，二进制值是10，100，1000，10000.在n-1之后，对应的二进制值是1，11，111，111.这样会保留哈希值原来的低阶值，所以只要哈希值的低阶值不一样，就不会有冲突。

　　其实如果数组长度是2的n次方，那么(n-1) hash就相当于hash% n，那为什么不直接用hash% n呢？这是因为逐位操作效率会更高。经过我的局部测试，计算速度是%运算的50倍左右。

　　因此，JDK使用这种巧妙的算法来表现，既保证了元素的均匀分布，又保证了效率。

　　4.2为什么不直接用key的hashCode？我们本来要分析spreed方法的代码，现在看来这个方法没用了。只需使用key的hashCode来定位哈希表。为什么要用spreed法处理？

　　其实归根结底是为了降低碰撞的概率。让我们先看看spreed方法中的代码做了什么：

　　1、h ^ (h 16)

　　H 16表示将h的二进制值向右移动16位。我们知道整形是32位，所以右移16位后，高16位移至低16位。并且高16位被清除。

　　对于XOR运算，二进制位是逐位比较的。如果相同，则为0，如果不同，则为1。这一行代码意味着对高16位和低16位进行异或运算。如果两个hashCode值的低16位相同，但高16位不同，那么经过这样的计算后，低16位就会变得不同。

　　为什么要让低位不一样？

　　这是因为哈希表数组的长度n会是一个很小的值，所以在进行(n-1)哈希运算时，总是使用hash的较小值。即使哈希值不同，如果低位相等，也会发生冲突。而H(H . 16)处理的哈希值使得hashCode的高阶值也参与到哈希运算中，从而降低了碰撞的概率。

　　2 、( h ^(h . 16))哈希比特

　　让我们再看一遍完整的代码。为什么高位移到低位后，原来的低位被异或，我们还需要用常量HASH_BITS计算？

　　HASH_BITS该常量的值为0x7fffffff，转换为二进制0111 1111 1111 1111 1111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 11 111。

　　此操作之后，最高位将变为0。其实去掉符号位，得到的都是正数。

　　这是因为负hashCode在ConcurrentHashMap中有特殊的含义，所以我们需要得到一个正hashCode。

　　通过总结上面的分析，我们已经知道了在ConcurrentHashMap中如何通过Hash值映射数组位置，这里的算法设计确实很巧妙。也许我们平时用不到代码，但也要记在心里。相信面试的时候会用到。

　　作者李一鸣

　　来源海量开放在线course.com，程序员梦工厂

　　版权归作者所有：原创作品来自博主imooc海量开放网络课程君，转载请联系作者取得授权，否则将追究法律责任。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。