ConcurrentHashMap是不是绝对并发安全的,concurrenthashmap并发能力为什么优于hashtable

　　00-1010前言红黑树红黑树数据结构基础复习红黑树插入数据多线程竞争下读写扩展的原理是扩展。在扩展期间，有多个线程争用读操作。扩展期间写操作的摘要

　　00-1010我是fancy，一个年纪轻轻bug累积到3200的程序员。同事夸我一个人养活了整个测试组。

　　最近迷上了并发编程。这个东西怎么说？意思是平时工作用不到，但是一旦用上了就可以用在面试中。不，并发容器再次被卷起。

　　说到并发容器，你肯定也知道那些，CopyOnWriteArrayList，BlockingQueue等等。但是，作为采访佳能，在谈及并发容器时，不能绕过ConcurrentHashMap。

　　由于篇幅原因，本文不会具体解释那些基本问题，比如为什么哈希表数组的长度一定是2的n次方等。将更多地关注并发性这个话题。如果有必要，我们稍后会解释。

　　那么在这篇文章中，我们就来深入谈谈八股文中的兰博基尼：ConcurrentHashMap，这是本次大厂面试最喜欢的对象。

　　以下技术点基于JDK1.8~

　　00-1010众所周知，从JDK1.8开始，ConcurrentHashMap的底层数据结构从原来的段锁变成了数组链表的红黑树形式。

　　它是一个并发容器，一个包含数据的容器在并发环境下肯定会出现各种问题。如果你在单线程环境下玩单机，那么在并发环境下其他线程会和你抢数据、斗。所以写JUC包的大神Doug Lea把这些场景都一一进行了改编，可以说是绝对的并发安全。至少它运行了这么多年没有任何bug。

目录

前言

JDK1.8这里的红黑树，准确的说是TreeBin代理类，作为红黑树的具体实现充当存储，TreeNode是封装红黑树的数据结构，所以你可以理解为TreeNode是封装TreeNode的容器。

　　黑树在ConcurrentHashMap中的体现是一个双向链表：

　　00-1010这里，红黑树维护一个字段dir。

　　在插入数据时，会获取该节点的哈希值，以便与当前节点p的哈希值进行比较，如果插入节点的哈希值小于当前节点，则dir的值为-1，否则为1:

　　因此，当dir的值为-1时，意味着插入的节点需要插入到当前节点的左子树中，或者继续在左子树上搜索。相反，如果dir的值为1，它将向右搜索。这里的规则和二叉查找树的一样。

　　00-1010，因为读操作本身是线程安全的。所以多线程同时读取同一个桶是没有问题的。

　　但是，如果写操作相互竞争，那么只有一个线程可以通过同步锁的方式同时获得某个桶的资源。

　　从源代码可以看出，put()方法的核心是putVal():

　　PutVal()很长。它主要通过同步锁定每个节点来保证并发的安全性。

　　这里最重要的两点

　　首先判断你放进去的元素是在链表里还是在红黑树上；

　　二是判断当前插入的键是否与链表或红黑树中的某个元素一致。如果当前插入的键与链表中所有元素的键不一致，则当前插入操作被追加到链表的末尾。否则，对应于该键的值被替换。

　　00-1010在你知道扩容的原理之前，你得知道什么会导致扩容。

　　因此，需要了解两个重要领域：

　　MIN_TREEIFY_CAPACITY:数组的初始长度，默认为64TREEIFY_THRESHOLD:树化阈值。如果桶位链表的长度达到8，则树形操作线程会将每个元素添加到桶中，并判断链表的长度。只有当元素个数大于阈值MIN_TREEIFY_CAPACITY且链表长度大于8时，才会调用treeifyBin()将链表转换为红色和黑色。

　　这里的扩展是指扩展数组的桶数，以便容纳更多的元素。

　　此外，扩展还维护另一个重要字段，sizeCtl:

　　通过翻译，我们可以知道这个场有三种状态：

　　>sizeCtl < 0：若为-1则起标记作用，告知其它线程此时正在初始化；若为其它的值表示当前table正在扩容sizeCtl = 0：表示创建table数组时还未进行扩容，没有指定的初始容量sizeCtl > 0：表示当table初始化后下次扩容的触发条件字段的值可以转化为32位的二进制数值，它的高16位表示扩容标识戳，用来标识扩容的范围，如从长度16扩容到32；低16位表示当前参与扩容的线程数量。

　　扩容操作会新建一个长度更大的数组，然后将老数组上的元素全部迁移到新的数组去。

　　扩容的本质目的是为了减少桶位链表的长度，提高查询效率。因为链表的查询复杂度是O(n)，如果链表过长就会影响查询效率。

　　假设桶位的长度从16扩容到32，说明桶位变多了，那迁移到新数组后就需要有元素去到新的桶位。这就需要通过一些算法将老数组和新数组的元素位置做一个映射。因为扩容后元素有的需要迁移到新的位置，有的还是处于和老数组一样的位置，只不过是换了一个数组。

　　如何计算出这个元素迁移后要呆在哪个桶位呢？这里使用了一个按位与的算法。就是将这个桶位key的hash值 & (扩容前数组长度 - 1)，若生成的值等于0则不需要迁移，否则就要进行迁移。并且维护两个变量ln和hn代表是否需要进行位置迁移。然后采用尾插法将元素插入。这就是LastRun机制。

　　注：尾插法指的就是后面插入的元素都处于前一个元素的后面

　　这里简单普通的扩容是没什么问题的，大多数场景都和HashMap的扩容是一样的。

　　问题就在于当前是处于并发环境的，而扩容也需要时间。

正在扩容 && 有多个线程正在竞争

所以，比较复杂的场景来了。若是桶位正在扩容，且有多个线程正在竞争读写咋办？厚礼谢

　　没关系，我们依然分情况来讨论。

扩容期间的读操作

如果扩容期间，有线程进行元素的读取，比如你去get()某个key的value，那读不读的到呢？

　　答案是可以。但是前提是你这个节点已经迁移结束，如果你是一个正在扩容迁移的节点，那就访问不到。

　　具体的操作，就是去调用find()。

　　当一个桶位要进行数据迁移，就会往这个桶位上放置一个ForwardingNode节点。除此之外还需要去标识这个节点是正在迁移还是已经迁移结束了的；

　　在这里我们统称迁移前的桶位节点叫老节点，迁移后的桶位节点叫新节点。当其中某一个节点迁移完成后，就会在老节点上添加一个fwd引用，它指向新节点的地址。

　　所以当某个线程访问了这个节点，看到它上面存在fwd引用，就说明当前table正在扩容，那么就会根据这个引用上的newtable字段去新数组的对应桶位上找到数据然后返回。

扩容期间的写操作

写操作相较于读操作会更加复杂一点，原因就是读操作只需要获取对应数据返回就行了，而写操作还要修改数据，所以当一个写线程来修改数据刚好碰到容器处于扩容期间，那么它还要协助容器进行扩容。

　　具体的扩容操作依然还要分情况，假如访问的桶位数据还没有被迁移走的话，那就直接竞争锁，然后在老节点上进行操作就行。

　　但是假如线程修改的节点正好是一个fwd节点，说明当前节点正处于扩容操作，那么为了节约线程数并且快速完成任务，当前线程就会进行协助扩容。如果有多个线程进行同时写，那么它们都会调用helpTransfer()进行协助扩容。

　　这里协助扩容的方式就是拿到一个扩容标识戳，这个标识戳的作用就是用来标识扩大的容量大小。因为每个线程都是独立的嘛，互不通信，但是它们要做的事情是相同的，就是将桶位扩大相同的值，所以它们就必须拿到这个相同的标识戳，只有标识戳一致才会进行扩容。

　　假设一个容器从16个桶位扩容到32个桶位，有线程A、B两个线程。

　　若A触发了扩容的机制，那么线程A就会进行扩容，此时线程B也来进行写操作，发现正在扩容就会进入到协助扩容的步骤中去。

　　所以线程A和线程B共同负责桶位的扩容。

　　一个线程负责扩容的桶位个数，是根据CPU核心数来算的。最少是16个，也就是一个线程最少要负责16个元素的扩容：

　　我们在上面有提过，sizeCtl转化为32位后，它的低16位是表示当前参与扩容的线程数量。所以当A线程触发了扩容之后，它就会将sizeCtl低16位的最后一位值+1，表示扩容线程多了一位，当它退出扩容时又会将最后一位的值-1，表示扩容线程少了一位，就这样各个线程共同维护这个字段。

　　所以你一定会好奇了：那我要是最后一个退出扩容的线程要怎么维护啊？是的，最后一个线程还有一些别的事情要做。当某一个线程完成任务后去判断sizeCtl的值得时候，发现它的低16位只剩下最后一位是1，再减下去就是0了，那就代表它是最后一个退出扩容的线程。此时它还需要去检查一遍老的table数组，判断是否还有遗漏的slot没有迁移。具体的操作就是去轮询检查是否还留有fwd节点，如果没有的话代表迁移完成，如果有的话还需要继续将它迁移到新的桶位：

　　由于源码非常长，所以我们就不贴全部源码了，通过流程图的方式来帮助大家理解这个扩容期间的操作：

总结

有的童鞋在看Juc这一块的时候会去背诵源码，将方法的调用链都讲的头头是道，我认为没有必要，相反面试官可能会觉得你过于抽象，背的这么清楚。并发的核心在于如何用手段去解决可能遇到的安全问题，并且让它更高效点，面试的目的也是为了体现你思维能力。

　　以上就是java并发容器ConcurrentHashMap深入分析的详细内容，更多关于ConcurrentHashMap并发容器的资料请关注盛行IT其它相关文章！

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