万字长文，ConcurrentSkipListMap源码详解( 二 ) ConcurrentSkipListMap思维导图简介

尽管可以通过将标记节点定义为不包含键/值字段来进一步压缩空间，但这不值得额外的类型测试开销。
删除标记在遍历期间很少遇到，通常会很快被垃圾收集。（请注意，这种技术在没有垃圾收集的系统中无法很好地工作。）
除了使用删除标记外，列表还使用值字段的空值来表示删除，其样式类似于典型的延迟删除方案。
如果节点的值为null ，则即使仍可访问，也将其在逻辑上被删除并忽略。
这样可以保持对并发替换与删除操作的适当控制-如果删除操作使字段为空，则尝试替换必须失败，并且删除操作必须返回该字段中保留的最后一个非空值。
（注意：此处将Null而不是一些特殊的标记用于值字段，因为它恰好与Map API的要求相吻合，即如果没有映射，则get方法将返回null ，这使节点即使删除也能保持并发可读性。在这里使用其他任何标记值充其量都是混乱的。）
以下是最初删除具有前身b和后继f的节点n的事件序列：
+------++------++------+ ...|b|------>|n|----->|f| ...+------++------++------+（1）CAS n的值字段从非null到null 。从这一点开始，没有遇到节点的公共操作都认为此映射存在。但是，其他正在进行的插入和删除操作仍可能会修改n的下一个指针。
（2）CAS n的下一个指针指向新的标记节点。从这一点开始，不能将其他节点附加到n上。这样可以避免基于CAS的链接列表中的删除错误。
+------++------++------++------+...|b|------>|n|----->|marker|------>|f| ...+------++------++------++------+（3）CAS b在n及其标记上的下一个指针。从这一点开始，没有新的遍历将遇到n ，并且最终可以对其进行GC 。
+------++------+ ...|b|----------------------------------->|f| ...+------++------+步骤1的失败会导致失败重试，原因是与其他操作的静态失败（lost race）。
步骤2-3可能会失败，因为在遍历具有空值的节点时注意到了其他某个线程，并通过标记和/或取消链接来帮助了其他线程。
这种帮助可以确保没有线程在等待删除线程的进展时被阻塞。
使用标记节点会使辅助代码稍微复杂化，因为遍历必须跟踪多达四个节点（b ， n ， marker ， f）的一致读取，而不仅仅是（b ， n ， f），尽管标记的下一个字段是不变，一旦下一个字段被CAS指向标记，它就再也不会改变，因此需要较少的照顾。
跳过列表为该方案添加了索引，因此基本级别遍历开始于被查找，插入或删除的位置附近-通常，基本级别遍历仅遍历几个节点。
除了需要确保基本遍历从没有（在结构上）删除的前任（此处为b）开始，否则不会改变基本算法，否则在处理删除后重试。
使用CAS链接和取消链接，将索引级别维护为具有可变下一个字段的列表。
索引列表操作中允许使用竞争，这些操作可能（很少）无法链接到新的索引节点或删除一个索引节点。（我们当然不能对数据节点执行此操作。）
但是，即使发生这种情况，索引列表仍然保持排序，因此可以正确地用作索引。
这可能会影响性能，但是由于跳过列表无论如何都是概率性的，因此最终结果是在争用情况下，有效的 p 值可能低于其标称值。
而且竞赛窗口要保持足够小，以至于在实践中，即使有很多争论，这些失败也是很少见的。
ps: 事实胜于雄辩，很少失败就是很少失败。
其他数据结构做得到吗？
文章插图
其他数据结构做得到吗?
由于建立索引，重试（针对基本列表和索引列表）相对代价较低，这一事实允许对重试逻辑进行一些较小的简化。
在大多数“帮助”（helping-out）案例之后执行遍历重启。
这并非总是严格必要的，但是隐式的退避往往有助于减少其他下游出现故障的CAS ，足以抵消重启成本。
这会使最坏的情况恶化，但似乎甚至可以改善竞争激烈的情况。
与大多数跳过列表实现不同，这里的索引插入和删除要求在基本级操作之后进行单独的遍历遍历，以添加或删除索引节点。
这增加了单线程开销，但是通过缩小干扰窗口来提高竞争性多线程性能，并允许删除以确保从公共删除操作返回后所有索引节点都将不可访问，从而避免了不必要的垃圾保留。
这在这里比在其他一些数据结构中更重要，因为我们不能使引用用户密钥的节点字段无效，因为它们可能仍被其他正在进行的遍历读取。