数据结构

java源码中对ConcurrentSkipListMap的描述如下：

图中，第0层为具体的数据，第1层的每一个node都有两个子node，一个指向同层的右边，一个指向下一层，它的类结构图如下：

head: head是类型为Index的数据结构，里面包含了一个保存key-value值的Node、指向右边的索引right、指向下一层的索引down

对于跳跃表的分析主要是它的增删改查，其中增与改在doPut方法，因此本文主要分析类图中的doGet(), doPUT(), doRemove方法

以下面的图先看下跳跃表的具体结构

head索引：比普通的索引多一个level字段，记录层级

以图中的索引4为例，它的right为8，down为4

findPredecessor

再开始之前先介绍这个方法，因为后面的三个方法中都会用到它，它的作用就是寻找的目标值的前一个节点，以前面的图为例，假设要寻找9，则需先找到它的前一个索引8，具体的步骤如下：

具体源码如下：

public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable {// 查找带查询key的左边范围起始值，次起始值必须是最底层的值private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {// 1. 如果key为null则直接抛出异常if (key == null)throw new NullPointerException(); // don't postpone errorsfor (;;) { // 2. 外层循环的作用：当其他线程修改了数据，当前线程重试开始寻找头结点for (Index<K,V> q = head, r = q.right, d;;) {if (r != null) {Node<K,V> n = r.node;K k = n.key;if (n.value == null) {// 3. 如果n的value为null,则将q->right->right.right修改为q->right.right，将right从链表中删除if (!q.unlink(r))// 其他线程已经修改数据，跳到最外层循环从头开始重新寻找break;r = q.right; continue;}if (cpr(cmp, key, k) > 0) {// 4. 如果待查询的key大于right的key，说明待查询的key在right的右边，则继续往右寻找q = r;r = r.right;continue;}}if ((d = q.down) == null)// 6. 已经查询到最底层，返回最底层的值return q.node;// 5. right的key大于等于待查询的key，说明带查询的key位于head的key与right的key之间，往下寻找q = d;r = d.right;}}}
}

doGet

假设要查找9，则查找路径如下红色路线图：

public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>implements Co ncurrentNavigableMap<K,V>, Cloneable, Serializable {private V doGet(Object key) {if (key == null)throw new NullPointerException();Comparator<? super K> cmp = comparator;outer: for (;;) {// 1. 查找索引for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {Object v; int c;if (n == null)// 2. 如果n为null说明跳表中没有key的值，退出循环break outer;Node<K,V> f = n.next;if (n != b.next)                // inconsistent read// 3. 另一线程已经修改数据，调到外层outer循环重新开始break;if ((v = n.value) == null) {    // n is deleted// 4. n已被另一线程删除，当前线程原子性参与删除, 调到外层outer循环重新开始n.helpDelete(b, f);break;}if (b.value == null || v == n)  // b is deleted// 5. b已被另一线程删除，重新查找break;if ((c = cpr(cmp, key, n.key)) == 0) {// 7. 查找到值，返回value@SuppressWarnings("unchecked") V vv = (V)v;return vv;}if (c < 0)// 8. 跳表中没有值，直接跳出循环break outer;// 6. n的key小于带查询key，继续next向右查找。b = n;n = f;}}return null;}
}

doRemove

如图中，假设要删除节点8：

1. 首先需要找到Node8
2. 将Node8标志为删除
3. 遍历删除所有Index8

这里回顾一下**ConcurrentSkipListMap<K, V>**的索引数据结构

在本例中有2两个Index8，这两个Index中的Node指向的是同一个值，也就是第2步中将Node8标记为删除，则所有的Index8中的Node都被标记为删除，这样一来第3步遍历的时候就会删除所有的Index8。看下源码

public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>implements Co ncurrentNavigableMap<K,V>, Cloneable, Serializable {final V doRemove(Object key, Object value) {if (key == null)throw new NullPointerException();Comparator<? super K> cmp = comparator;outer: for (;;) {// 1. findPredecessor需找到底层中最接近的8的索引b（本例中为4）, n = b.nextfor (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 readbreak;if ((v = n.value) == null) {        // n is deletedn.helpDelete(b, f);break;}if (b.value == null || v == n)      // b is deletedbreak;if ((c = cpr(cmp, key, n.key)) < 0)// 要删除的key不存在，退出break outer;if (c > 0) {// 要删除的key在n的右边，继续往右寻找b = n;n = f;continue;}// 2. 找到Index8if (value != null && !value.equals(v))// value不为null并且与key对应的值不匹配则不能删除break outer;// 将n的value设置为nullif (!n.casValue(v, null))// 另一线程已经修改n的value，重新开始break;// 设置删除标志，并将b->n->f修改为b->nif (!n.appendMarker(f) || !b.casNext(n, f))// 3. findNode中遍历的时候同样会删除无用的IndexfindNode(key);                  // retry via findNodeelse {// 3. 将n所在的Index从跳表中删除，即findPredecessor的第3步findPredecessor(key, cmp);      // clean indexif (head.right == null)// 减少无用的层级tryReduceLevel();}@SuppressWarnings("unchecked") V vv = (V)v;return vv;}}return null;}
}

doPut

假设要往跳表中插入7，则出现的结果可能有两种，如图：

1. 第一种情况是层级不变，这里称为情况A
2. 第二种是层级改变，这里称为情况B

至于层级增加或者不变是随机，接下来代码的时候详细分析，这里先把插入值的步骤理一下：

1. 找到底层的插入的位置，将新值插入到底层

2. 创建新值的层级索引
   

3. 将新值的层级索引与原层级的索引连接
   

接下来按这个顺序分析源码

新值插入底层

public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>implements Co ncurrentNavigableMap<K,V>, Cloneable, Serializable { private V doPut(K key, V value, boolean onlyIfAbsent) {Node<K,V> z;             // added nodeif (key == null)throw new NullPointerException();Comparator<? super K> cmp = comparator;outer: for (;;) {// 1. 查找合适的索引Index并获取其节点Nodefor (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {if (n != null) {Object v; int c;// n的下一个节点fNode<K,V> f = n.next;if (n != b.next)               // inconsistent read// n被另一个线程修改，重新开始break;if ((v = n.value) == null) {   // n is deleted// n被另一个线程删除，重新开始n.helpDelete(b, f);break;}if (b.value == null || v == n) // b is deleted// b被另一线程删除，重新开始break;if ((c = cpr(cmp, key, n.key)) > 0) {// 2. 待插入的key大于n的key， 向右继续寻找插入点b = n;n = f;continue;}if (c == 0) { // 待插入的key已经存在// 3. 更新原值并返回值if (onlyIfAbsent || n.casValue(v, value)) {@SuppressWarnings("unchecked") V vv = (V)v;// 返回原值并退出return vv;}break; // restart if lost race to replace value}// else c < 0; fall through}// 4. 找到插入点，即n的前一个位置， 修改底层的链表， b->n 更新为 b->z->n，即将新节点z插入链表z = new Node<K,V>(key, value, n);if (!b.casNext(n, z))// 另一线程已经更改，当前线程重新开始break;         // restart if lost race to append to b// 5. 底层链表更新结束break outer;}}}
}

创建新值的索引

public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>implements Co ncurrentNavigableMap<K,V>, Cloneable, Serializable { private V doPut(K key, V value, boolean onlyIfAbsent) {Node<K,V> z;             // added node// ......// 1. 获取随机数，根据随机数二进制中从右往左连续1的个数决定链表新的levelint rnd = ThreadLocalRandom.nextSecondarySeed();// 最高层级32层，最底层1层if ((rnd & 0x80000001) == 0) { // test highest and lowest bitsint level = 1, max;// 2. 计算新值需要创建索引的层级。举例子：如果是5，即101，则level为1；如果是7，即111，则level+2为3while (((rnd >>>= 1) & 1) != 0)++level;Index<K,V> idx = null;HeadIndex<K,V> h = head;// 假设此时level为3， max为3， level<=max，则先创建新插入节点的索引，即情况Aif (level <= (max = h.level)) {for (int i = 1; i <= level; ++i)// 3. 创建新值每一层的索引idx = new Index<K,V>(z, idx, null);}else { // try to grow by one level// 假设level为7， max为3，则level为4，及情况B，此种情况head也需要更新层数level = max + 1; // hold in array and later pick the one to use// 创建4层新插入节点的索引@SuppressWarnings("unchecked")Index<K,V>[] idxs =(Index<K,V>[])new Index<?,?>[level+1];for (int i = 1; i <= level; ++i)// 3. 创建新值每一层的索引// 注意这里的z，每一层的node都为z，也就是doRemove中所说的。idxs[i] = idx = new Index<K,V>(z, idx, null);for (;;) {h = head;int oldLevel = h.level;if (level <= oldLevel) // lost race to add levelbreak;HeadIndex<K,V> newh = h;Node<K,V> oldbase = h.node;// 补齐头结点，并将第四层的头结点的right直接指向新插入节点的索引for (int j = oldLevel+1; j <= level; ++j)newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);// 将第四层的newh作为该跳表的headif (casHead(h, newh)) {h = newh;idx = idxs[level = oldLevel];break;}}}// ......}return null;}
}

连接索引

public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>implements Co ncurrentNavigableMap<K,V>, Cloneable, Serializable { private V doPut(K key, V value, boolean onlyIfAbsent) {Node<K,V> z;             // added node// ......// 更新层级，添加索引int rnd = ThreadLocalRandom.nextSecondarySeed();// 最高层级32层，最底层1层if ((rnd & 0x80000001) == 0) { // test highest and lowest bits// ......// find insertion points and splice insplice: for (int insertionLevel = level;;) {int j = h.level;for (Index<K,V> q = h, r = q.right, t = idx;;) {if (q == null || t == null)// 已经到底层，结束更新break splice;if (r != null) {Node<K,V> n = r.node;int c = cpr(cmp, key, n.key);if (n.value == null) {// n已经被标记，删除nif (!q.unlink(r))break;r = q.right;continue;}if (c > 0) {// 新插入的key大于right的key，向右移动q = r;r = r.right;continue;}}if (j == insertionLevel) {// 将q->r更新为q->t->rif (!q.link(r, t))// 另一线程已修改数据，重新开始break; // restartif (t.node.value == null) {// t已被删除，通过findNode函数将key删除findNode(key);break splice;}// 已经是最底层，退出循环if (--insertionLevel == 0)break splice;}// 向下一层继续更新if (--j >= insertionLevel && j < level)t = t.down;q = q.down;r = q.right;}}}return null;}
}

至此，关于ConcurrentSkipListMap的分析到此结束，感谢阅读。