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

原因: 若队列在删除的过程中没有引入 maker 节点, 有可能导致刚刚插入的节点无缘无故地消失
下面是一个例子:
原本: 有3个节点 A, B, C 组成的队列
A -> B -> C (A.next = B, B.next = C)
现在有两个线程 (thread1, thread2) 进行操作, thread1 进行删除节点B, thread2 在节点B后插入节点D
进行操作前:
+------++------++------+|A|------>|B|----->|C| +------++------++------+进行操作后:
D 插入到节点B之后成功了, 可是队列的头结点是 A, 通过A.next().next().next()….. 方法
无法访问到节点D(D节点已经丢失了)
+------++------+|B|----->|D|+------++------+|V+------++------+|A|------>----->----->|C| +------++------+有 marker 节点的世界如图 demo2(有 marker 节点):
有三个链接在一起的Node (node 有三个属性 key, value, next, 且所有操作都是 cas)
+------+ +------+ +------+... | A |------>| B |----->| C | ...+------+ +------+ +------+我们假定有 2 个线程：
Thread 1 Thread 2 - if B.value =http://kandian.youth.cn/index/= null 判断B的value是否为null B.value = null - A.casNext(B, B.next) - - Node D = new Node(C); B.casNext(C, D);
步骤：

Thread 2 准备在B的后面插入一个节点 D, 它先判断 B.value =http://kandian.youth.cn/index/= null, 发现 B 没被删除(假设 value = null 是删除)
Thread1 对 B 节点进行删除 B.value = http://kandian.youth.cn/index/null
Thread 1 在B的后面追加一个 MarkerNode M
Thread 1 将 B 与 M 一起删除
这时你会发现 Thread 2 的 B.casNext(C, D) 发生的可能 :

1) 在Thread 1 设置 marker 节点前操作, 则B.casNext(C, D) 成功, B 与 marker 也一起删除
2) 在Thread 1 设置maker之后, 删除 b与marker之前, 则B.casNext(C, D) 操作失败(b.next 变成maker了), 所以在代码中加个 loop 循环尝试
3) 在Thread 1 删除 B, marker 之后, 则B.casNext(C, D) 失败(b.next变成maker, B.casNext(C,D) 操作失败, 在 loop 中重新进行尝试插入)

最终结论 maker 节点的存在致使非阻塞链表能实现中间节点的删除和插入同时安全进行(反过来就是若没有marker节点, 有可能刚刚插入的数据就丢掉了)

doGet() 获取元素整体流程

寻找 key 的前继节点 b (这时b.next = null || b.next > key, 则说明不存key对应的 Node)
接着就判断 b, b.next 与 key之间的关系(其中有些 helpDelete操作)

源码

/** * 获取 key 对应的值 * @param key the key * @return the value, or null if absent * * @author 老马啸西风 */private V doGet(Object key) {if (key == null)throw new NullPointerException();Comparator cmp = comparator;outer: for (;;) {// 获取前继节点for (Node b = findPredecessor(key, cmp), n = b.next;;) {Object v; int c;// b.next 为 null,直接返回 nullif (n == null)break outer;// 被其他线程修改 ， 重试Node f = n.next;if (n != b.next)// inconsistent readbreak;// n 被删除 ， 重试if ((v = n.value) == null) {// n is deletedn.helpDelete(b, f);break;}// b 被删除 ， 重试if (b.value =http://kandian.youth.cn/index/= null || v == n)// b is deletedbreak;// 找到元素 ， 返回if ((c = cpr(cmp, key, n.key)) == 0) {@SuppressWarnings("unchecked") V vv = (V)v;return vv;}// 未找到 ， 跳出循环 。if (c < 0)break outer;// b = b.next// n = n.next// 向右继续查找b = n;n = f;}}return null;}

小结好家伙，这个源码看得太累了，特别是这个 doPut 方法。
不过看完之后还是收获颇丰，下一节我们学习一下 ConcurrentSkipListSet 。
希望本文对你有帮助，如果有其他想法的话，也可以评论区和大家分享哦。
【万字长文，ConcurrentSkipListMap源码详解】各位极客的点赞收藏转发，是老马持续写作的最大动力！

文章插图