与体验课程有关的问题和对象(2)

treeifyBin不一定执行红黑树转换，它可能只是执行数组扩展. 构造空节点TreeBin之后，将开始构造红黑树. 第一个节点为左，右，左子节点设置为空，红黑树的根节点设置为黑，父节点为空. 然后，在添加每个节点之后，将调用balanceInsertion方法以维护此红黑树的属性和平衡. 红黑树所有操作的复杂度为O（logn），因此，当元素比率较大时，效率也很高. **数组的扩展**我们对ConcurrentHashMap的存储结构有一个大致的了解，因此我们考虑一个问题，当越来越多的链接列表存储在数组中时，存储在其中的元素的可能性很高. 它们将被插入到现有的链表中，而不是使用数组中剩余的空位. 这将导致存储在数组中的链接列表越来越长，这将导致哈希表查找速度降低，并且从O（1）开始的时间复杂度将逐渐接近链接列表O（n / 2），从而显然违反了哈萨克斯坦. 该表的初衷.

因此ConcurrentHashMap将执行一项称为容量扩展的操作. 那就是增加数组的长度并增加更多的空缺. 最终目标是防止链表变得太长，以使搜索的时间复杂度趋于O（1）. 当数组不为空时，将不会执行扩展操作，因为当存储桶几乎已满时，新保存的元素将更可能到达已经使用的位置，因此最后几个存储桶可能很难使用，和链接列表，但是它越来越长. ConcurrentHashMap将在更合适的时间扩展，通常是在使用75％的数组位置时. 实际上，以上内容类似于HashMap. ConcurrentHashMap还提供线程安全保证. 它主要通过CAS和Synchronized关键字实现. 我们将在源代码分析中对其进行详细研究. 让我们做一个总结: 1. ConcurrentHashMap采用数组+链表+红黑树的存储结构； 2.通过其自身的hashCode将存储的Key值映射到数组的相应位置； 3. ConcurrentHashMap用于确保查询效率. 它将增加数据的长度. 此操作称为容量扩展. 4.当链接列表的长度增加到8时，它可能会触发将链接列表转换为红黑树. （如果数组的长度小于64，则将首先扩展容量. 请参阅源代码分析. ）

接下来，我们从ConcurrentHashMap的结构，保存元素，哈希算法，扩展和查找数据的方面分析源代码. 扩展后阵列的容量增加了一倍. **数据迁移（容量扩展过程中的线程安全性）** ConcurrentHashMap的扩展时间与HashMap相同，在put方法的下一步中将对这两者进行检查，以确定是否需要扩展容量. 但是，容量扩展过程完全不同，ConcurrentHashMap的扩展方法称为传输. 您可以通过输入put方法的addCount方法找到传输方法. 传输方法的主要思想是: 首先，扩展后需要将旧数组的所有值复制到新数组中. 开始复制；复制阵列插槽时，请先锁定原始阵列插槽，以确保原始阵列插槽无法使用. 将副本成功复制到新阵列后，将原始阵列插槽分配给传输节点；如果此时有新数据，正当有必要将其放入该插槽时，发现该插槽是一个传输节点，它将永远等待，因此与该插槽对应的数据在扩展为完成它从数组的尾部复制到头部. 复制成功后，将原始阵列中的节点设置为传输节点. 直到全部将数据集复制到新数组时，该数组直接以新的赋值分配到整个容器数组，用这种方法完整复制的putTreeVal（）不会以类似的遍历方式进行描述.

④Get方法ConcurrentHashMap读取相对简单. 首先，获取数组的索引，然后判断数组索引的键是否等于我们的键. 如果相等，则直接返回. 如果索引的插槽是链表或红色，则在黑色树的情况下，将分别调用查找数据的相应方法. 总体思路类似于HashMap. 源代码如下: 计算哈希值. 根据哈希值（n – 1）＆h查找数组的对应位置. 根据该位置节点的性质进行相应搜索. 如果位置为null，则直接返回null. 如果该位置的节点正是您需要的节点，则返回该节点的值. 如果此位置上节点的哈希值小于0，则表示容量正在扩展或为红黑树. 如果不满足以上三个条件，则它是一个链表，可以遍历和比较. **初始化数组**初始化数组时，必须首先旋转以确保可以成功初始化它，然后通过CAS设置SIZECTL变量的值以确保只有一个线程可以在同一位置初始化数组时间. CAS成功后，还将再次判断当前数组是否已初始化. 如果已经初始化，则不会再次初始化. 通过旋转+ CAS +双重检查可确保数组初始化期间的线程安全. 源代码如下: 有一个键值sizeCtl，该值具有多种含义.

1，-1表示线程正在创建表； 2，-N表示N-1个线程正在复制表； 3.在表初始化之前，这意味着基于构造函数传递的值的计算值应为Initialized size； 4.初始化表后，将其设置为表大小的75％，该值表示表的容量（数组容量）. InitTable使用1和4，其他方法使用2和3. 下面我们可以首先看一下ConcurrentHashMap的构造方法，该方法将使用以上3种方法，最后回顾并总结HashMap和ConcurrentHashMap与ConcurrentHashMap和HashMap的相似之处: 1.数组和链表的结构几乎相同，所以数据结构的底层结构的操作思想是相同的（但是相同的思想，底层的实现是不同的）； 2.都实现了Map接口并继承了AbstractMap抽象类，因此大多数方法也相同，HashMap有一些方法，几乎​​是ConcurrentHashMap，因此当我们需要从HashMap切换到ConcurrentHashMap时，我们不必担心关于两者之间的兼容性问题. 1.红黑树结构略有不同. HashMap的红黑树中的节点称为TreeNode. TreeNode不仅仅具有属性. ，还维护红黑树的结构，例如查找，添加等；红黑树在ConcurrentHashMap中分为两部分. TreeNode仅维护属性和搜索功能，并添加TreeBin来维护红黑树. 结构，并负责锁定和解锁根节点； 2.添加了ForwardingNode（传输）节点，该节点将在容量扩展期间使用. 通过使用此节点，可以确保容量扩展期间的线程安全.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-156432-2.html