共计 13103 个字符，预计需要花费 33 分钟才能阅读完成。
介绍
跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。
跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。
跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。
存储结构
跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。
源码分析
主要内部类
内部类跟存储结构结合着来看，大概能预测到代码的组织方式。
// 数据节点，典型的单链表结构
static final class Node<K,V> {
final K key;
// 注意：这里 value 的类型是 Object，而不是 V
// 在删除元素的时候 value 会指向当前元素本身
volatile Object value;
volatile Node<K,V> next;
Node(K key, Object value, Node<K,V> next) {
this.key = key;
this.value = value;
this.next = next;
}
Node(Node<K,V> next) {
this.key = null;
this.value = this; // 当前元素本身 (marker)
this.next = next;
}
}
// 索引节点，存储着对应的 node 值，及向下和向右的索引指针
static class Index<K,V> {
final Node<K,V> node;
final Index<K,V> down;
volatile Index<K,V> right;
Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
this.node = node;
this.down = down;
this.right = right;
}
}
// 头索引节点，继承自 Index，并扩展一个 level 字段，用于记录索引的层级
static final class HeadIndex<K,V> extends Index<K,V> {
final int level;
HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {super(node, down, right);
this.level = level;
}
}
（1）Node，数据节点，存储数据的节点，典型的单链表结构；
（2）Index，索引节点，存储着对应的 node 值，及向下和向右的索引指针；
（3）HeadIndex，头索引节点，继承自 Index，并扩展一个 level 字段，用于记录索引的层级；
构造方法
public ConcurrentSkipListMap() {
this.comparator = null;
initialize();}
public ConcurrentSkipListMap(Comparator<? super K> comparator) {
this.comparator = comparator;
initialize();}
public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
this.comparator = null;
initialize();
putAll(m);
}
public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {this.comparator = m.comparator();
initialize();
buildFromSorted(m);
}
## 四个构造方法里面都调用了 initialize() 这个方法
private static final Object BASE_HEADER = new Object();
private void initialize() {
keySet = null;
entrySet = null;
values = null;
descendingMap = null;
// Node(K key, Object value, Node<K,V> next)
// HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level)
head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
null, null, 1);
}
可以看到，这里初始化了一些属性，并创建了一个头索引节点，里面存储着一个数据节点，这个数据节点的值是空对象，且它的层级是 1。
所以，初始化的时候，跳表中只有一个头索引节点，层级是 1，数据节点是一个空对象，down 和 right 都是 null。
通过内部类的结构我们知道，一个头索引指针包含 node, down, right 三个指针，为了便于理解，我们把指向 node 的指针用虚线表示，其它两个用实线表示，也就是虚线不是表明方向的。
增加元素
我们知道跳表插入元素的时候， 会随机的方式决定出它需要的层级，然后向下找到各层链中它所在的位置， 最后通过单链表插入的方式把节点及索引插入进去来实现的。
public V put(K key, V value) {
// 不能存储 value 为 null 的元素
// 因为 value 为 null 标记该元素被删除（后面会看到）if (value == null)
throw new NullPointerException();
// 调用 doPut() 方法添加元素
return doPut(key, value, false);
}
private V doPut(K key, V value, boolean onlyIfAbsent) {
// 添加元素后存储在 z 中
Node<K,V> z; // added node
// key 也不能为 null
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
// Part I：找到目标节点的位置并插入
// 这里的目标节点是数据节点，也就是最底层的那条链
// 自旋
outer: for (;;) {
// 寻找目标节点之前最近的一个索引对应的数据节点，存储在 b 中，b=before
// 并把 b 的下一个数据节点存储在 n 中，n=next
// 为了便于描述，我这里把 b 叫做当前节点，n 叫做下一个节点
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
// 如果下一个节点不为空
// 就拿其 key 与目标节点的 key 比较，找到目标节点应该插入的位置
if (n != null) {
// v=value，存储节点 value 值
// c=compare，存储两个节点比较的大小
Object v; int c;
// n 的下一个数据节点，也就是 b 的下一个节点的下一个节点（孙子节点）Node<K,V> f = n.next;
// 如果 n 不为 b 的下一个节点
// 说明有其它线程修改了数据，则跳出内层循环
// 也就是回到了外层循环自旋的位置，从头来过
if (n != b.next) // inconsistent read
break;
// 如果 n 的 value 值为空，说明该节点已删除，协助删除节点
if ((v = n.value) == null) { // n is deleted
// todo 这里为啥会协助删除？后面讲
n.helpDelete(b, f);
break;
}
// 如果 b 的值为空或者 v 等于 n，说明 b 已被删除
// 这时候 n 就是 marker 节点，那 b 就是被删除的那个
if (b.value == null || v == n) // b is deleted
break;
// 如果目标 key 与下一个节点的 key 大
// 说明目标元素所在的位置还在下一个节点的后面
if ((c = cpr(cmp, key, n.key)) > 0) {
// 就把当前节点往后移一位
// 同样的下一个节点也往后移一位
// 再重新检查新 n 是否为空，它与目标 key 的关系
b = n;
n = f;
continue;
}
// 如果比较时发现下一个节点的 key 与目标 key 相同
// 说明链表中本身就存在目标节点
if (c == 0) {
// 则用新值替换旧值，并返回旧值（onlyIfAbsent=false）if (onlyIfAbsent || n.casValue(v, value)) {@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
// 如果替换旧值时失败，说明其它线程先一步修改了值，从头来过
break; // restart if lost race to replace value
}
// 如果 c <0，就往下走，也就是找到了目标节点的位置
// else c < 0; fall through
}
// 有两种情况会到这里
// 一是到链表尾部了，也就是 n 为 null 了
// 二是找到了目标节点的位置，也就是上面的 c <0
// 新建目标节点，并赋值给 z
// 这里把 n 作为新节点的 next
// 如果到链表尾部了，n 为 null，这毫无疑问
// 如果 c <0，则 n 的 key 比目标 key 大，相妆于在 b 和 n 之间插入目标节点 z
z = new Node<K,V>(key, value, n);
// 原子更新 b 的下一个节点为目标节点 z
if (!b.casNext(n, z))
// 如果更新失败，说明其它线程先一步修改了值，从头来过
break; // restart if lost race to append to b
// 如果更新成功，跳出自旋状态
break outer;
}
}
// 经过 Part I，目标节点已经插入到有序链表中了
// Part II：随机决定是否需要建立索引及其层次，如果需要则建立自上而下的索引
// 取个随机数
int rnd = ThreadLocalRandom.nextSecondarySeed();
// 0x80000001 展开为二进制为 10000000000000000000000000000001
// 只有两头是 1
// 这里 (rnd & 0x80000001) == 0
// 相当于排除了负数（负数最高位是 1），排除了奇数（奇数最低位是 1）// 只有最高位最低位都不为 1 的数跟 0x80000001 做 & 操作才会为 0
// 也就是正偶数
if ((rnd & 0x80000001) == 0) { // test highest and lowest bits
// 默认 level 为 1，也就是只要到这里了就会至少建立一层索引
int level = 1, max;
// 随机数从最低位的第二位开始，有几个连续的 1 则 level 就加几
// 因为最低位肯定是 0，正偶数嘛
// 比如，1100110，level 就加 2
while (((rnd >>>= 1) & 1) != 0)
++level;
// 用于记录目标节点建立的最高的那层索引节点
Index<K,V> idx = null;
// 取头索引节点（这是最高层的头索引节点）HeadIndex<K,V> h = head;
// 如果生成的层数小于等于当前最高层的层级
// 也就是跳表的高度不会超过现有高度
if (level <= (max = h.level)) {
// 从第一层开始建立一条竖直的索引链表
// 这条链表使用 down 指针连接起来
// 每个索引节点里面都存储着目标节点这个数据节点
// 最后 idx 存储的是这条索引链表的最高层节点
for (int i = 1; i <= level; ++i)
idx = new Index<K,V>(z, idx, null);
}
else { // try to grow by one level
// 如果新的层数超过了现有跳表的高度
// 则最多只增加一层
// 比如现在只有一层索引，那下一次最多增加到两层索引，增加多了也没有意义
level = max + 1; // hold in array and later pick the one to use
// idxs 用于存储目标节点建立的竖起索引的所有索引节点
// 其实这里直接使用 idx 这个最高节点也是可以完成的
// 只是用一个数组存储所有节点要方便一些
// 注意，这里数组 0 号位是没有使用的
@SuppressWarnings("unchecked")Index<K,V>[] idxs =
(Index<K,V>[])new Index<?,?>[level+1];
// 从第一层开始建立一条竖的索引链表（跟上面一样，只是这里顺便把索引节点放到数组里面了）for (int i = 1; i <= level; ++i)
idxs[i] = idx = new Index<K,V>(z, idx, null);
// 自旋
for (;;) {
// 旧的最高层头索引节点
h = head;
// 旧的最高层级
int oldLevel = h.level;
// 再次检查，如果旧的最高层级已经不比新层级矮了
// 说明有其它线程先一步修改了值，从头来过
if (level <= oldLevel) // lost race to add level
break;
// 新的最高层头索引节点
HeadIndex<K,V> newh = h;
// 头节点指向的数据节点
Node<K,V> oldbase = h.node;
// 超出的部分建立新的头索引节点
for (int j = oldLevel+1; j <= level; ++j)
newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
// 原子更新头索引节点
if (casHead(h, newh)) {
// h 指向新的最高层头索引节点
h = newh;
// 把 level 赋值为旧的最高层级的
// idx 指向的不是最高的索引节点了
// 而是与旧最高层平齐的索引节点
idx = idxs[level = oldLevel];
break;
}
}
}
// 经过上面的步骤，有两种情况
// 一是没有超出高度，新建一条目标节点的索引节点链
// 二是超出了高度，新建一条目标节点的索引节点链，同时最高层头索引节点同样往上长
// Part III：将新建的索引节点（包含头索引节点）与其它索引节点通过右指针连接在一起
// 这时 level 是等于旧的最高层级的，自旋
splice: for (int insertionLevel = level;;) {
// h 为最高头索引节点
int j = h.level;
// 从头索引节点开始遍历
// 为了方便，这里叫 q 为当前节点，r 为右节点，d 为下节点，t 为目标节点相应层级的索引
for (Index<K,V> q = h, r = q.right, t = idx;;) {
// 如果遍历到了最右边，或者最下边，// 也就是遍历到头了，则退出外层循环
if (q == null || t == null)
break splice;
// 如果右节点不为空
if (r != null) {
// n 是右节点的数据节点，为了方便，这里直接叫右节点的值
Node<K,V> n = r.node;
// 比较目标 key 与右节点的值
int c = cpr(cmp, key, n.key);
// 如果右节点的值为空了，则表示此节点已删除
if (n.value == null) {
// 则把右节点删除
if (!q.unlink(r))
// 如果删除失败，说明有其它线程先一步修改了，从头来过
break;
// 删除成功后重新取右节点
r = q.right;
continue;
}
// 如果比较 c >0，表示目标节点还要往右
if (c > 0) {
// 则把当前节点和右节点分别右移
q = r;
r = r.right;
continue;
}
}
// 到这里说明已经到当前层级的最右边了
// 这里实际是会先走第二个 if
// 第一个 if
// j 与 insertionLevel 相等了
// 实际是先走的第二个 if，j 自减后应该与 insertionLevel 相等
if (j == insertionLevel) {
// 这里是真正连右指针的地方
if (!q.link(r, t))
// 连接失败，从头来过
break; // restart
// t 节点的值为空，可能是其它线程删除了这个元素
if (t.node.value == null) {
// 这里会去协助删除元素
findNode(key);
break splice;
}
// 当前层级右指针连接完毕，向下移一层继续连接
// 如果移到了最下面一层，则说明都连接完成了，退出外层循环
if (--insertionLevel == 0)
break splice;
}
// 第二个 if
// j 先自减 1，再与两个 level 比较
// j、insertionLevel 和 t(idx) 三者是对应的，都是还未把右指针连好的那个层级
if (--j >= insertionLevel && j < level)
// t 往下移
t = t.down;
// 当前层级到最右边了
// 那只能往下一层级去走了
// 当前节点下移
// 再取相应的右节点
q = q.down;
r = q.right;
}
}
}
return null;
}
// 寻找目标节点之前最近的一个索引对应的数据节点
private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
// key 不能为空
if (key == null)
throw new NullPointerException(); // don't postpone errors
// 自旋
for (;;) {
// 从最高层头索引节点开始查找，先向右，再向下
// 直到找到目标位置之前的那个索引
for (Index<K,V> q = head, r = q.right, d;;) {
// 如果右节点不为空
if (r != null) {
// 右节点对应的数据节点，为了方便，我们叫右节点的值
Node<K,V> n = r.node;
K k = n.key;
// 如果右节点的 value 为空
// 说明其它线程把这个节点标记为删除了
// 则协助删除
if (n.value == null) {if (!q.unlink(r))
// 如果删除失败
// 说明其它线程先删除了，从头来过
break; // restart
// 删除之后重新读取右节点
r = q.right; // reread r
continue;
}
// 如果目标 key 比右节点还大，继续向右寻找
if (cpr(cmp, key, k) > 0) {
// 往右移
q = r;
// 重新取右节点
r = r.right;
continue;
}
// 如果 c <0，说明不能再往右了
}
// 到这里说明当前层级已经到最右了
// 两种情况：一是 r ==null，二是 c <0
// 再从下一级开始找
// 如果没有下一级了，就返回这个索引对应的数据节点
if ((d = q.down) == null)
return q.node;
// 往下移
q = d;
// 重新取右节点
r = d.right;
}
}
}
// Node.class 中的方法，协助删除元素
void helpDelete(Node<K,V> b, Node<K,V> f) {
/*
* Rechecking links and then doing only one of the
* help-out stages per call tends to minimize CAS
* interference among helping threads.
*/
// 这里的调用者 this==n，三者关系是 b ->n->f
if (f == next && this == b.next) {
// 将 n 的值设置为 null 后，会先把 n 的下个节点设置为 marker 节点
// 这个 marker 节点的值是它自己
// 这里如果不是它自己说明 marker 失败了，重新 marker
if (f == null || f.value != f) // not already marked
casNext(f, new Node<K,V>(f));
else
// marker 过了，就把 b 的下个节点指向 marker 的下个节点
b.casNext(this, f.next);
}
}
// Index.class 中的方法，删除 succ 节点
final boolean unlink(Index<K,V> succ) {
// 原子更新当前节点指向下一个节点的下一个节点
// 也就是删除下一个节点
return node.value != null && casRight(succ, succ.right);
}
// Index.class 中的方法，在当前节点与 succ 之间插入 newSucc 节点
final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
// 在当前节点与下一个节点中间插入一个节点
Node<K,V> n = node;
// 新节点指向当前节点的下一个节点
newSucc.right = succ;
// 原子更新当前节点的下一个节点指向新节点
return n.value != null && casRight(succ, newSucc);
}我们这里把整个插入过程分成三个部分：
Part I：找到目标节点的位置并插入
- 这里的目标节点是数据节点，也就是最底层的那条链；
- 寻找目标节点之前最近的一个索引对应的数据节点（数据节点都是在最底层的链表上）；
- 从这个数据节点开始往后遍历，直到找到目标节点应该插入的位置；
- 如果这个位置有元素，就更新其值（onlyIfAbsent=false）；
- 如果这个位置没有元素，就把目标节点插入；
- 至此，目标节点已经插入到最底层的数据节点链表中了；
Part II：随机决定是否需要建立索引及其层次，如果需要则建立自上而下的索引
- 取个随机数 rnd，计算 (rnd & 0x80000001)；
- 如果不等于 0，结束插入过程，也就是不需要创建索引，返回；
- 如果等于 0，才进入创建索引的过程（只要正偶数才会等于 0）；
- 计算 while (((rnd >>>= 1) & 1) != 0)，决定层级数，level 从 1 开始；
- 如果算出来的层级不高于现有最高层级，则直接建立一条竖直的索引链表（只有 down 有值），并结束 Part II；
- 如果算出来的层级高于现有最高层级，则新的层级只能比现有最高层级多 1；
- 同样建立一条竖直的索引链表（只有 down 有值）；
- 将头索引也向上增加到相应的高度，结束 Part II；
- 也就是说，如果层级不超过现有高度，只建立一条索引链，否则还要额外增加头索引链的高度（脑补一下，后面举例说明）；
Part III：将新建的索引节点（包含头索引节点）与其它索引节点通过右指针连接在一起（补上 right 指针）
- 从最高层级的头索引节点开始，向右遍历，找到目标索引节点的位置；
- 如果当前层有目标索引，则把目标索引插入到这个位置，并把目标索引前一个索引向下移一个层级；
- 如果当前层没有目标索引，则把目标索引位置前一个索引向下移一个层级；
- 同样地，再向右遍历，寻找新的层级中目标索引的位置，回到第（2）步；
- 依次循环找到所有层级目标索引的位置并把它们插入到横向的索引链表中；
总结起来，一共就是三大步：
- 插入目标节点到数据节点链表中；
- 建立竖直的 down 链表；
- 建立横向的 right 链表；
添加元素举例
假设初始链表是这样：
假如，我们现在要插入一个元素 9。
（1）寻找目标节点之前最近的一个索引对应的数据节点，在这里也就是找到了 5 这个数据节点；
（2）从 5 开始向后遍历，找到目标节点的位置，也就是在 8 和 12 之间；
（3）插入 9 这个元素，Part I 结束；
然后，计算其索引层级，假如是 3，也就是 level=3。
（1）建立竖直的 down 索引链表；
（2）超过了现有高度 2，还要再增加 head 索引链的高度；
（3）至此，Part II 结束；
最后，把 right 指针补齐。
（1）从第 3 层的 head 往右找当前层级目标索引的位置；
（2）找到就把目标索引和它前面索引的 right 指针连上，这里前一个正好是 head；
（3）然后前一个索引向下移，这里就是 head 下移；
（4）再往右找目标索引的位置；
（5）找到了就把 right 指针连上，这里前一个是 3 的索引；
（6）然后 3 的索引下移；
（7）再往右找目标索引的位置；
（8）找到了就把 right 指针连上，这里前一个是 5 的索引；
（9）然后 5 下移，到底了，Part III 结束，整个插入过程结束；
删除元素
删除元素，就是把各层级中对应的元素删除即可.
public V remove(Object key) {return doRemove(key, null);
}
final V doRemove(Object key, Object value) {
// key 不为空
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
// 自旋
outer: for (;;) {
// 寻找目标节点之前的最近的索引节点对应的数据节点
// 为了方便，这里叫 b 为当前节点，n 为下一个节点，f 为下下个节点
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
// 整个链表都遍历完了也没找到目标节点，退出外层循环
if (n == null)
break outer;
// 下下个节点
Node<K,V> f = n.next;
// 再次检查
// 如果 n 不是 b 的下一个节点了
// 说明有其它线程先一步修改了，从头来过
if (n != b.next) // inconsistent read
break;
// 如果下个节点的值奕为 null 了
// 说明有其它线程标记该元素为删除状态了
if ((v = n.value) == null) { // n is deleted
// 协助删除
n.helpDelete(b, f);
break;
}
// 如果 b 的值为空或者 v 等于 n，说明 b 已被删除
// 这时候 n 就是 marker 节点，那 b 就是被删除的那个
if (b.value == null || v == n) // b is deleted
break;
// 如果 c <0，说明没找到元素，退出外层循环
if ((c = cpr(cmp, key, n.key)) < 0)
break outer;
// 如果 c >0，说明还没找到，继续向右找
if (c > 0) {
// 当前节点往后移
b = n;
// 下一个节点往后移
n = f;
continue;
}
// c=0，说明 n 就是要找的元素
// 如果 value 不为空且不等于找到元素的 value，不需要删除，退出外层循环
if (value != null && !value.equals(v))
break outer;
// 如果 value 为空，或者相等
// 原子标记 n 的 value 值为空
if (!n.casValue(v, null))
// 如果删除失败，说明其它线程先一步修改了，从头来过
break;
// P.S. 到了这里 n 的值肯定是设置成 null 了
// 关键！！！！// 让 n 的下一个节点指向一个 market 节点
// 这个 market 节点的 key 为 null，value 为 marker 自己，next 为 n 的下个节点 f
// 或者让 b 的下一个节点指向下下个节点
// 注意：这里是或者 ||，因为两个 CAS 不能保证都成功，只能一个一个去尝试
// 这里有两层意思：// 一是如果标记 market 成功，再尝试将 b 的下个节点指向下下个节点，如果第二步失败了，进入条件，如果成功了就不用进入条件了
// 二是如果标记 market 失败了，直接进入条件
if (!n.appendMarker(f) || !b.casNext(n, f))
// 通过 findNode() 重试删除（里面有个 helpDelete() 方法）findNode(key); // retry via findNode
else {
// 上面两步操作都成功了，才会进入这里，不太好理解，上面两个条件都有非 "!" 操作
// 说明节点已经删除了，通过 findPredecessor() 方法删除索引节点
// findPredecessor() 里面有 unlink() 操作
findPredecessor(key, cmp); // clean index
// 如果最高层头索引节点没有右节点，则跳表的高度降级
if (head.right == null)
tryReduceLevel();}
// 返回删除的元素值
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
}
return null;
}
（1）寻找目标节点之前最近的一个索引对应的数据节点（数据节点都是在最底层的链表上）；
（2）从这个数据节点开始往后遍历，直到找到目标节点的位置；
（3）如果这个位置没有元素，直接返回 null，表示没有要删除的元素；
（4）如果这个位置有元素，先通过 n.casValue(v, null) 原子更新把其 value 设置为 null；
（5）通过 n.appendMarker(f) 在当前元素后面添加一个 marker 元素标记当前元素是要删除的元素；
（6）通过 b.casNext(n, f) 尝试删除元素；
（7）如果上面两步中的任意一步失败了都通过 findNode(key) 中的 n.helpDelete(b, f) 再去不断尝试删除；
（8）如果上面两步都成功了，再通过 findPredecessor(key, cmp) 中的 q.unlink(r) 删除索引节点；
（9）如果 head 的 right 指针指向了 null，则跳表高度降级；
删除元素举例
假如初始跳表如下图所示，我们要删除 9 这个元素。
（1）找到 9 这个数据节点；
（2）把 9 这个节点的 value 值设置为 null；
（3）在 9 后面添加一个 marker 节点，标记 9 已经删除了；
（4）让 8 指向 12；
（5）把索引节点与它前一个索引的 right 断开联系；
（6）跳表高度降级；
至于，为什么要有（2）（3）（4）这么多步骤呢，因为多线程下如果直接让 8 指向 12，可以其它线程先一步在 9 和 12 间插入了一个元素 10 呢，这时候就不对了。
所以这里搞了三步来保证多线程下操作的正确性。
如果第（2）步失败了，则直接重试；
如果第（3）或（4）步失败了，因为第（2）步是成功的，则通过 helpDelete() 不断重试去删除；
其实 helpDelete() 里面也是不断地重试（3）和（4）；
只有这三步都正确完成了，才能说明这个元素彻底被删除了。
查找元素
经过上面的插入和删除，查找元素就比较简单了：
public V get(Object key) {return doGet(key);
}
private V doGet(Object key) {
// key 不为空
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
// 自旋
outer: for (;;) {
// 寻找目标节点之前最近的索引对应的数据节点
// 为了方便，这里叫 b 为当前节点，n 为下个节点，f 为下下个节点
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
// 如果链表到头还没找到元素，则跳出外层循环
if (n == null)
break outer;
// 下下个节点
Node<K,V> f = n.next;
// 如果不一致读，从头来过
if (n != b.next) // inconsistent read
break;
// 如果 n 的值为空，说明节点已被其它线程标记为删除
if ((v = n.value) == null) { // n is deleted
// 协助删除，再重试
n.helpDelete(b, f);
break;
}
// 如果 b 的值为空或者 v 等于 n，说明 b 已被删除
// 这时候 n 就是 marker 节点，那 b 就是被删除的那个
if (b.value == null || v == n) // b is deleted
break;
// 如果 c ==0，说明找到了元素，就返回元素值
if ((c = cpr(cmp, key, n.key)) == 0) {@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
// 如果 c <0，说明没找到元素
if (c < 0)
break outer;
// 如果 c >0，说明还没找到，继续寻找
// 当前节点往后移
b = n;
// 下一个节点往后移
n = f;
}
}
return null;
}
（1）寻找目标节点之前最近的一个索引对应的数据节点（数据节点都是在最底层的链表上）；
（2）从这个数据节点开始往后遍历，直到找到目标节点的位置；
（3）如果这个位置没有元素，直接返回 null，表示没有找到元素；
（4）如果这个位置有元素，返回元素的 value 值；
查找元素举例
假如有如下图所示这个跳表，我们要查找 9 这个元素，它走过的路径是怎样的呢？可能跟你相像的不一样。。
（1）寻找目标节点之前最近的一个索引对应的数据节点，这里就是 5；
（2）从 5 开始往后遍历，经过 8，到 9；
（3）找到了返回；
整个路径如下图所示：
为啥不从 9 的索引直接过来呢？实际打断点调试来看确实是按照上图的路径来走的。
我猜测可能是因为 findPredecessor() 这个方法是插入、删除、查找元素多个方法共用的，在单链表中插入和删除元素是需要记录前一个元素的，而查找并不需要，这里为了兼容三者使得编码相对简单一点，所以就使用了同样的逻辑，而没有单独对查找元素进行优化。
正文完
