前言我看中了，一个年纪轻轻就积累了3200个bug的程序员，同事夸我一个人撑起了整个测试组。我最近迷上了并发编程。怎么说并发呢，就是你平时工作不用，面试一用就用。这不，并发容器又被卷起来了。说到并发容器，你肯定也知道那些，CopyOnWriteArrayList，并发队列BlockingQueue等等。但是作为一个典型的面试例子，说到并发容器就绕不开ConcurrentHashMap。由于篇幅原因，本文不会具体解释那些比较基础的问题，比如哈希表数组的长度为什么一定要是2的n次方等。会更侧重于并发的话题。如有必要，稍后将提供额外的解释。那么本文就来深入聊聊本次大厂面试的最爱，八股文章中的兰博基尼：ConcurrentHashMap。以下技术点基于JDK1.8~基础回顾大家都知道，从JDK1.8开始，ConcurrentHashMap的底层数据结构从原来的Segment段锁变成了数组+链表+红黑树的形式。它是一个并发容器，一个容纳数据的容器在并发环境下肯定会出现各种问题。如果你在单机单线程环境下玩，在并发环境下其他线程会和你竞争数据和bucketslots。因此，编写JUC包的大师DougLea也将这些场景一一适配。可以说对于并发是绝对安全的。至少运行了这么多年，没有遇到过什么bug。红黑树红黑树数据结构JDK1.8这里的红黑树，准确的说是一个TreeBin代理类，作为红黑树的具体实现进行存储，TreeNode是数据封装红黑树的结构。所以你可以理解为TreeBin是一个封装了TreeNode的容器。ConcurrentHashMap中红黑树的体现是一个双向链表：红黑树在这里插入数据，红黑树维护一个字段dir。插入数据时，会获取该节点的哈希值，并与当前节点p的哈希值进行比较。如果插入节点的hash值小于当前节点，则dir的值为-1，否则为1：所以，当dir的值为-1时，表示需要插入插入节点进入当前节点的左子节点或者继续在左子树上查找。反之，如果dir值为1，则向右查找。这里的规则和二叉搜索树的规则是一样的。多线程竞争下的读写操作自然是线程安全的，因为读操作本身就是线程安全的。所以多个线程同时读取同一个桶是没有问题的。但是，如果存在竞争写操作，则使用Synchronized锁来保证某个bucket在同一时间只能有一个线程获取资源。从源码可以看出，put()方法的核心是putVal()：putVal()很长，主要使用Synchronized对各个节点进行加锁，保证并发的安全。这里最重要的两点，一是判断你放入的元素是在链表中还是在红黑树中；另一种是判断当前插入的key是否与链表或红黑树上的某个元素一致。如果当前插入键与链表中所有元素的键不一致，则将当前插入操作追加到链表末尾。否则，替换键对应的值。扩展原理在了解扩展原理之前，您必须知道什么会导致扩展。因此，有两个重要的字段需要知道：MIN_TREEIFY_CAPACITY：数组的初始长度，默认为64TREEIFY_THRESHOLD：树的阈值，如果指定的桶链表的长度达到8，可能会发生树的操作thread将每一个元素添加到bucket中，会根据对链表的长度进行判断。只有当元素个数大于阈值MIN_TREEIFY_CAPACITY且链表长度大于8时，才会调用treeifyBin()将链表转为红黑树，否则进行扩容操作。这里的扩容是指扩充数组的桶数，以容纳更多的元素。此外，扩展还维护了另一个重要的字段，sizeCtl：通过翻译，我们可以知道这个字段有三种状态：sizeCtl<0：如果是-1，作为一个标记，通知其他线程它正在初始化此时;如果是其他值，说明当前表正在扩容sizeCtl=0:表示创建表数组时表数组还没有扩容，没有指定初始容量sizeCtl>0:表示表数组的值表初始化后下一次扩展的触发条件字段可以转换为32位二进制值。高16位表示扩展标识戳，用于标识扩展范围，比如从16的长度扩展到32；低16位代表当前参与扩容的线程数。扩展操作创建一个长度更大的新数组，然后将旧数组中的所有元素迁移到新数组中。扩容的本质目的是减少桶链表的长度，提高查询效率。因为链表的查询复杂度是O(n)，如果链表过长，会影响查询效率。假设桶的长度从16扩展到32，就意味着桶的数量更多了。迁移到新数组后，元素需要转到新的桶中。这就需要一些算法来映射旧数组和新数组的元素位置。因为扩容后，有的元素需要迁移到新的位置，有的还是和老数组在同一个位置，只是数组变了。如何计算这个元素迁移后会留在哪个桶中？这里使用按位与算法。即bucketkey的hash值&(展开前的数组长度-1)，如果生成的值等于0则不需要迁移，否则需要迁移。并维护两个变量ln和hn，代表是否需要位置迁移。然后使用尾插值插入元素。这就是LastRun机制。注意：尾插入法是指后面插入的元素都在前面的元素后面。这里简单普通的展开是没有问题的。大多数场景和HashMap的扩展是一样的。问题是目前是并发环境，扩容也需要时间。扩容&&有多个线程在竞争那么，更复杂的场景来了。如果桶在膨胀，多个线程竞争读写怎么办？大方的谢了也没关系，还是看情况再商量吧。扩容时的读操作如果扩容时有一个线程去读元素，比如你去get()一个key的值，你能不能读到？答案是肯定的。但是前提是你的节点已经迁移了。如果你是正在扩容和迁移的节点，你将无法访问它。具体操作是调用find()。当一个bucket需要进行数据迁移时，会在这个bucket上放置一个ForwardingNode节点。另外，需要识别节点是正在迁移还是已经迁移；这里我们统称迁移前的bucket节点为旧节点，迁移后的bucket节点为新节点。当其中一个节点迁移时，旧节点将添加一个fwd引用，指向新节点的地址。所以当一个线程访问这个节点，看到它上面的fwd引用，就说明当前表正在扩容，那么它会根据引用上的newtable字段，在新数组对应的bucket中找到数据并返回.扩容时的写操作比读操作复杂。原因是读操作只需要获取相应的数据并返回即可，而写操作还需要修改数据，所以当一个写线程修改数据时，只是命中容器。在扩容期间，还辅助容器的扩容。具体扩容操作还是要视情况而定。如果访问的bucket数据还没有迁移，那么直接竞争锁，然后在老节点上操作。但是，如果线程修改的节点恰好是fwd节点，则说明当前节点处于扩容过程中。为了节省线程数量，快速完成任务，当前线程会辅助扩容。如果有多个线程同时写，都会调用helpTransfer()辅助扩容。这里辅助扩容的方式是获得一个扩容标识戳，用来标识扩容后的容量。因为每个线程都是独立的，相互之间不通信，但是他们要做的事情是一样的，就是把桶扩充到相同的值，所以他们必须得到相同的标识戳，只有当标识戳是consistent将被扩展。假设一个容器从16桶扩容到32桶，有两个线程，线程A和线程B，如果A触发了扩容机制，那么线程A会扩容，此时线程B也会进行写操作时间。如果发现正在进行扩容，则进入辅助扩容步骤。所以线程A和线程B共同负责桶的扩容。一个线程负责扩容的桶数是根据CPU核数计算的。至少16位，即一个线程至少要负责扩容16个元素：上面我们提到，sizeCtl转换为32位后，其低16位表示当前参与扩容的线程数。所以当线程A触发扩容时，会将sizeCtl的最后16位值加1，表示扩容线程还有一位，退出扩容时，会将最后一位值加-1，表示扩展线程少了一位，所以每个线程共同维护这个字段。那么你一定很好奇：如果我是最后一个退出扩容的线程，我该如何维护呢？是的，最后一个线程还有一些其他事情要做。当某个线程完成任务，判断sizeCtl的值，发现只有它的低16位最后一位为1，减去则为0，说明它是最后一个退出的线程扩张。这个时候还需要检查旧表数组，判断是否有缺失的slot没有被迁移。具体操作是轮询，查看是否还剩下fwd节点。如果没有，则表示迁移完成。如果有，则需要继续迁移到新的bucket。由于源码很长，我们就不贴出所有的源码了。扩容期我们会用流程图帮助大家理解操作：总结一下，有的童鞋看juc的时候会背源码，把方法调用链链接起来，都说的好听点，我不'觉得有必要。相反，面试官可能会觉得你太抽象了，背的那么清楚。并发的核心在于如何用手段解决可能出现的安全问题，并使其更加高效。面试的目的也是为了体现你的思维能力。
