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

（1）根据给定的key从跳表的左上方往右或者往下查找到Node链表的前驱Node结点，这个查找过程会删除一些已经标记为删除的结点。
（2）找到前驱结点后，开始往后插入查找插入的位置（因为找到前驱结点后，可能有另外一个线程在此前驱结点后插入了一个结点，所以步骤 1 得到的前驱现在可能不是要插入的结点的前驱，所以需要往后查找）。
（3）随机生成一个种子，判断是否需要增加层级，并且在各层级中插入对应的 Index 结点。
友情提示： doPut 的内容较多，不感兴趣的伙伴可以跳过，知道大概流程即可。
源码static final class Values extends AbstractCollection {final ConcurrentNavigableMap m;Values(ConcurrentNavigableMap map) {m = map;}@SuppressWarnings("unchecked")public Iterator iterator() {if (m instanceof ConcurrentSkipListMap)return ((ConcurrentSkipListMap)m).valueIterator();elsereturn ((SubMap)m).valueIterator();}//...}findPredecessor 找到前继节点这个方法我们在 skiplist 中其实也有。
就是从左往右，从上往下找。
/** * 找到最底层的节点， key 严格小于给定的 key 。* 或者返回 base-level 的 header 节点，如果元素不存在。* * 同时在遍历的过程中，还会把删除的节点进行 unlink 操作。* 调用者依靠清除索引删除节点的这种副作用。* ** @author 老马啸西风 */private Node findPredecessor(Object key, Comparator cmp) {// 禁止 key 为 nullif (key == null)throw new NullPointerException(); // don't postpone errorsfor (;;) {// 这个流程和 skiplist 一样的// 从最高层索引，从左到右，从上到下寻找。// 最高层，只因为可以快速定位到元素的大概位置，从上到下，是为了精确地找到 base-level 的元素信息。for (Index q = head, r = q.right, d;;) {if (r != null) {Node n = r.node;K k = n.key;// value 为 null ，说明被删除了。// 执行 unlink 操作，如果失败，则进行重试.if (n.value =http://kandian.youth.cn/index/= null) {if (!q.unlink(r))break;// restart// r 变为 q.right 右边元素，继续执行r = q.right;// reread rcontinue;}// 比较器比较 key> k ，则继续向右。if (cpr(cmp, key, k) > 0) {q = r;r = r.right;continue;}}// 到这里说明当前层级已经到最右了// 两种情况：一是r==null ，二是c<0// 再从下一级开始找// 如果没有下一级了，就返回这个索引对应的数据节点// 元素位于最右边，且无法继续向下，只能返回这个节点，作为前继节点。if ((d = q.down) == null)return q.node;// 向下，向右q = d;r = d.right;}}}findNode 查找节点除了查找前继节点，上面还有一个查询 Node 的方法，也值得我们注意。
返回保持键的节点；如果没有，则返回null ，清除沿途看到的所有已删除节点。反复遍历基本级别，以查找从findPredecessor返回的前任者开始的键，并在遇到时处理基本级别的删除。
实际上上面调用的时候，也正是利用这种清除无效节点的副作用（side effect）。
在以下情况下，重新启动将以节点n为中心进行遍历：
（1）在读取n的下一个字段之后，不再假定n是前任b的当前后继者，这意味着我们没有一致的3节点快照，因此无法取消链接遇到的任何后续已删除节点。
（2）n的value字段为null ，表示n被删除，在这种情况下，我们在重试之前帮助进行正在进行的结构删除。
即使在某些情况下这种取消链接不需要重新启动，也不会在此处进行分类，因为这样做通常不会超过重新启动的成本。
（3）n是标记，或者n的前任值字段为null ，表示（除其他可能性外）findPredecessor返回了已删除的节点。
我们无法取消链接该节点，因为我们不知道它的前任节点，因此请依赖另一个调用findPredecessor的通知并返回一些更早的前任节点，它将执行此操作。
仅在循环开始时才需要严格执行此检查（并且根本不需要严格进行b.value检查），但每次迭代均需执行此检查，以帮助避免调用者与其他线程的争用，因为它们将无法更改链接，因此无论如何都会重试。
doPut ， doRemove和findNear中的遍历循环都包含相同的三种检查。
专门的版本出现在findFirst和findLast及其变体。
他们不容易共享代码，因为每个人都使用执行顺序执行的本地人读取字段。
/** * Nodes heading each level keep track of their level. */static final class HeadIndex extends Index {final int level;HeadIndex(Node node, Index down, Index right, int level) {super(node, down, right);this.level = level;}}插入的例子为了让大家更好地理解这些源码，我们和大家一起看一个例子。