到目前为止，我们已经看到了在Java World：Hash和Treemap中实现键值的两个数据结构。这两个数据结构具有优势和缺点。
但是，这次我介绍了第三种键值数据结构：Skiplist.skiplist的效率不低于红树和黑树，但是其原理和实施复杂性比红色和黑树更简单。
什么是Skiplist？跳过列表称为跳台，哪个可以替换平衡树的数据结构。它的数据元素根据密钥的密钥值默认，并且自然是有序的。SKIP列表允许排序的数据分配在多层链接列表中，确定向上上升或不使用0-1随机数，并使用“为时间交换空间”的算法将每个节点添加到每个节点上。噬器可以忽略某些不能参与插入，删除和搜索的节点，从而提高效率。
让我们先查看一个简单的链接列表，如下：
如果我们需要查询9、21、30，比较数为3 + 6 + 8 = 17次，那么是否有任何优化计划？索引”，如下：
让我们与这些索引进行比较，以确定下一个元素是正确还是向下。由于“索引”，它将大大减少检索过程中的比较数量。当然，元素不多，很难反映优势。当有足够的元素时，该索引结构将显示他们的技能。
Skiplist具有以下功能：
我们可以在上面进行一些扩展，以变成典型的船只结构
Skiplistd的搜索算法更简单。对于上述我们希望找到元素21，该过程如下：
如图所示
红色虚线表示路径。
Skiplist插入操作主要包括：
假设我们要插入的元素为23，搜索后，可以确认她是在25日之前，在9、16和21之前的位置。当然，您需要考虑级别的K。
如果级别k> 3
需要申请新级别（4级）
如果级别k = 2
只需直接插入2级层
它将在此处涉及算法：l层是通过丢失硬币来确定的，并且算法由ConcurrentsKiplistMap源代码分析。另一个需要注意的是，在插入k层后，应进行新的节点。确保所有小于K层的级别都应出现。
删除节点和插入节点基本上是相同的：查找节点，删除节点和调整指针。
例如，删除节点9，如下：
通过以上，我们知道Skiplist使用时间的算法，其插入和搜索效率O（logn），其效率不低于红树和黑树，但其原理和实现比红色和黑树更简单从总体上讲，链接的列表不会向Skiplist强调。
ConcurrentsKiplistMap是通过Skiplis数据结构实现的。在实现Skiplist的顺序中，ConcurrentsKiplistMap提供了三个内部类来构建此类链接结构：节点，index，headExex.headEndex.honghem，节点代表底部 - 级别的单链路订单订单节点和索引作为索引基于节点的索引层。HeadIndex用于维持索引级别。在这一点上，我们可以说ConcurrentsKiplistMap是通过头衔维持索引级别。通过顶层查看它，查询范围逐步减小。当它到达底层节点时，只需要一小部分数据。JDK中的关系如下所示：
节点
节点的结构与一般的单链列表没有什么不同。键值和下一个节点的下一个点。
指数
索引提供了一个基于节点节点的索引节点，下一层索引的右侧和下层节点。
头衔
HeadIndex是定义级别的级别。
ConcurrentsKiplistMap提供四个构造函数，每个构造函数调用初始化的初始化方法。
请注意，初始化（）方法不仅在构造函数中调用，例如克隆，清除和ReadObject，该方法被调用以初始化步骤。请注意随机种子的初始化。
随机游行一个简单的随机数生成器（稍后引入）。
CoucurrentsKiplistMap提供了将（）方法关联此映射中指定密钥的方法。源代码如下：
首先判断，如果值是null，则丢弃NullPoInterException，否则请致电Doput方法。实际上，如果您看到了JDK的源代码，则应该熟悉此类操作。JDK源代码中的许多方法首先要进行一些必要验证，以首先验证某些必要性验证。然后，实际操作用于调用do **（）方法。
doput（）方法是更多的内容，我们逐步分析。
doput（）方法有三个参数。除了钥匙，值之外，还有一种布尔类型的仅限fabsent。当参数使用当前密钥时，我该怎么办。当仅ififabsent为false时，请替换值并返回到值。使用代码解释：
首先确定密钥是否为null。如果是空的，请投掷NullPoInterException。从这里我们可以确认ConcurrentsKiplist不支持键或值null。然后调用FindPredequeSpor（）方法传递密钥以确认位置。FindPredequeSpor（）方法实际上是为了确认插入密钥的位置。
findpredequepors（）方法的含义非常清楚：寻找前身。从最高的级别索引到右边的最高级别，直到null或右节点的键大于当前键，然后向下看，然后重复依次进行过程。返回的结果注意到节点不是项目，因此插入的位置应为底部节点链接列表。
在此过程中，ConcrrentSkiplistMap赋予该方法一个函数，即确定节点的值是否为null。如果是null，则意味着该节点已被删除，并且通过调用UNLINK（）方法来删除节点。
删除节点的过程非常简单，只需更改正确的指针即可。
通过findpredequepors（）找到前身节点后，我该怎么办？看：
找到正确的位置后，将插入在此位置插入节点。插入节点的过程相对简单，也就是说，将键值打包到节点中，然后将其添加到链接列表中。casnext（）方法。当然，插入之前需要进行一系列验证工作。
在底部插入节点后，下一步是什么？新索引。上一个博客中提到的博客作者说，在插入节点时，将根据扔硬币的方法确定新节点的级别。由于可能存在并发性，ConcurrentsKiplistMap使用threadlocalrandom生成随机数。如下：
扔硬币以确定水平的想法非常简单，也就是说，如果硬币为正，则抛售硬币，级别 + 1，否则停止，如下：
在解释Skiplist插入节点时，解释说，决策的级别将分为两种处理情况。一个是，如果级别级别大于最大级别，则需要添加。在该级别上添加了节点。
等级 <= headIndex.level
从底层开始，小于level的每一层都初始化一个index，每次的node都指向新加入的node，down指向下一层的item，右侧next全部为null。整个处理过程非常简单：为小于level的每一层初始化一个index，然后加入到原来的index链条中去。
level > headIndex.leveel
当硬币确定的级别大于最大级别时，有必要添加一个新层以进行处理。处理逻辑如下：
通过上述步骤，我们发现，尽管已经找到了前一个节点并插入了节点，但它决定确定级别并生成相应的索引，但并未将这些索引中的这些索引插入相应的层中。
该代码分为两个部分，一个是找到相应级别的节点的位置，第二部分在位置插入，然后向下移动。
在这一点上，ConcurrentsKiplistMap的PUT操作已经结束。代码金额更多，这是一个摘要：
与操作相比，获取操作将更加简单。该过程实际上等同于POT操作的第一步：
类似于操作的第一步，第一个调用FindPredequeSpor（）方法以查找前身节点，然后沿右右涂抹。同时，在此过程中，它还承担删除null节点的责任。
删除操作是删除指定的密钥节点，如下：
直接调用doremove（）方法。这里删除有两个参数，一个是密钥，另一个是值，因此Doremove方法提供了删除键，这也提供了同时满足密钥值的时间。
调用findpredequepors（）方法查找前身节点，然后将其移至右侧，然后对其进行比较。找到后，使用CAS将值替换为null，然后确定节点是否是该层的唯一索引。算过层并完成删除。
实际上，可以从中可以看出删除方法是设置节点的值设置为null，并且并未真正删除节点节点。实际上，我们可以从上面的操作中看到并进行操作。他们可以在寻找节点时判断节点。如果为null，请调用UNLINK（）方法以取消关系，如下：
ConcurrentsKiplistMap的size（）操作与confurrenthashmap不同。它不能保持全局变量来计算元素的数量，因此您需要每次调用该方法。
调用findfirs（）方法查找第一个节点，然后使用statistics的Node suft。从本文中，可以返回统计信息，您可以在最多integer.max_value.max_value..note上返回，请注意，该线程在这里安全。
ConcurrentsKiplistMap过程实际上并不复杂。与confurrenthashmap相比，这很简单。如果您熟悉Skiplist，那么ConcurrentsKiplistMap应该是中国餐。
下面，我们开始征服Java并发的阻塞队列
原始：https：//juejin.cn/post/710280117118564030