摘要：同時，也提供了一個基于的實現類，底層基于紅黑樹設計，是一種有序的。可以看成是并發版本的，但是和不同是，并不是基于紅黑樹實現的，其底層是一種類似跳表的結構。上述所有構造器都調用了方法方法將一些字段置初始化，然后將指針指向新創建的結點。
本文首發于一世流云專欄：https://segmentfault.com/blog...
一、ConcurrentSkipListMap簡介
類繼承結構
在正式講ConcurrentSkipListMap之前，我們先來看下ConcurrentSkipListMap的類繼承圖：
我們知道，一般的Map都是無序的，也就是只能通過鍵的hash值進行定位。JDK為了實現有序的Map，提供了一個SortedMap接口，SortedMap提供了一些根據鍵范圍進行查找的功能，比如返回整個Map中 key最小/大的鍵、返回某個范圍內的子Map視圖等等。
為了進一步對有序Map進行增強，JDK又引入了NavigableMap接口，該接口進一步擴展了SortedMap的功能，提供了根據指定Key返回最接近項、按升序/降序返回所有鍵的視圖等功能。
同時，也提供了一個基于NavigableMap的實現類——TreeMap，TreeMap底層基于紅黑樹設計，是一種有序的Map。關于TreeMap和NavigableMap，本文不作贅述，讀者可以查看Oracle的官方文檔：https://docs.oracle.com/javas...。
ConcurrentSkipListMap的由來
JDK1.6時，為了對高并發環境下的有序Map提供更好的支持，J.U.C新增了一個ConcurrentNavigableMap接口，ConcurrentNavigableMap很簡單，它同時實現了NavigableMap和ConcurrentMap接口：
ConcurrentNavigableMap接口提供的功能也和NavigableMap幾乎完全一致，很多方法僅僅是返回的類型不同：
J.U.C提供了基于ConcurrentNavigableMap接口的一個實現——ConcurrentSkipListMap。ConcurrentSkipListMap可以看成是并發版本的TreeMap，但是和TreeMap不同是，ConcurrentSkipListMap并不是基于紅黑樹實現的，其底層是一種類似跳表（Skip List）的結構。
二、Skip List簡介
什么是Skip List
Skip List（以下簡稱跳表），是一種類似鏈表的數據結構，其查詢/插入/刪除的時間復雜度都是O(logn)。
我們知道，通常意義上的鏈表是不能支持隨機訪問的（通過索引快速定位），其查找的時間復雜度是O(n)，而數組這一可支持隨機訪問的數據結構，雖然查找很快，但是插入/刪除元素卻需要移動插入點后的所有元素，時間復雜度為O(n)。
為了解決這一問題，引入了樹結構，樹的增刪改查效率比較平均，一棵平衡二叉樹（AVL）的增刪改查效率一般為O(logn)，比如工業上常用紅黑樹作為AVL的一種實現。
但是，AVL的實現一般都比較復雜，插入/刪除元素可能涉及對整個樹結構的修改，特別是并發環境下，通常需要全局鎖來保證AVL的線程安全，于是又出現了一種類似鏈表的數據結構——跳表。
Skip List示例
在講Skip List之前，我們先來看下傳統的單鏈表：
上圖的單鏈表中（省去了結點之間的鏈接），當想查找7、15、46這三個元素時，必須從頭指針head開始，遍歷整個單鏈表，其查找復雜度很低，為O(n)。
來看下Skip List的數據結構是什么樣的：
上圖是Skip List一種可能的結構，它分了2層，假設我們要查找“15”這個元素，那么整個步驟如下：
從頭指針head開始，找到第一個結點的最上層，發現其指向的下個結點值為8，小于15，則直接從1結點跳到8結點。
8結點最上層指向的下一結點值為18，大于15，則從8結點的下一層開始查找。
從8結點的最下層一直向后查找，依次經過10、13，最后找到15結點。
上述整個查找路徑如下圖標黃部分所示：
同理，如果要查找“46”這個元素，則整個查找路徑如下圖標黃部分所示：
上面就是跳躍表的基本思想了，每個結點不僅僅只包含指向下一個結點的指針，可能還包含很多個其它指向后續結點的指針。并且，一個結點本身可以看成是一個鏈表（自上向下鏈接）。這樣就可以跳過一些不必要的結點，從而加快查找、刪除等操作，這其實是一種“空間換時間”的算法設計思想。
那么一個結點可以包含多少層呢？ 比如，Skip List也可能是下面這種包含3層的結構(在一個3層Skip List中查找元素“46”)：
層數是根據一種隨機算法得到的，為了不讓層數過大，還會有一個最大層數MAX_LEVEL限制，隨機算法生成的層數不得大于該值。后面講ConcurrentSkipListMap時，我們會具體分析。
以上就是Skip List的基本思想了，總結起來，有以下幾點：
跳表由很多層組成；
每一層都是一個有序鏈表；
對于每一層的任意結點，不僅有指向下一個結點的指針，也有指向其下一層的指針。
三、ConcurrentSkipListMap的內部結構
介紹完了跳表，再來看ConcurrentSkipListMap的內部結構就容易得多了：
ConcurrentSkipListMap內部一共定義了3種不同類型的結點，元素的增刪改查都從最上層的head指針指向的結點開始：
public class ConcurrentSkipListMap2 extends AbstractMap
implements ConcurrentNavigableMap, Cloneable, Serializable {
/**
* 最底層鏈表的頭指針BASE_HEADER
*/
private static final Object BASE_HEADER = new Object();
/**
* 最上層鏈表的頭指針head
*/
private transient volatile HeadIndex head;
/* ---------------- 普通結點Node定義 -------------- */
static final class Node {
final K key;
volatile Object value;
volatile Node next;
// ...
}
/* ---------------- 索引結點Index定義 -------------- */
static class Index {
final Node node; // node指向最底層鏈表的Node結點
final Index down; // down指向下層Index結點
volatile Index right; // right指向右邊的Index結點
// ...
}
/* ---------------- 頭索引結點HeadIndex -------------- */
static final class HeadIndex extends Index {
final int level; // 層級
// ...
}
}
我們來看下這3類結點的具體定義。
結點定義
普通結點：Node
普通結點——Node，也就是ConcurrentSkipListMap最底層鏈表中的結點，保存著實際的鍵值對，如果多帶帶看底層鏈，其實就是一個按照Key有序排列的單鏈表：
static final class Node {
final K key;
volatile Object value;
volatile Node next;
/**
* 正常結點.
*/
Node(K key, Object value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
/**
* 標記結點.
*/
Node(Node next) {
this.key = null;
this.value = this;
this.next = next;
}
/**
* CAS更新結點的value
*/
boolean casValue(Object cmp, Object val) {
return UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val);
}
/**
* CAS更新結點的next
*/
boolean casNext(Node cmp, Node val) {
return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
}
/**
* 判斷當前結點是否為[標記結點]
*/
boolean isMarker() {
return value == this;
}
/**
* 判斷當前結點是否是最底層鏈表的頭結點
*/
boolean isBaseHeader() {
return value == BASE_HEADER;
}
/**
* 在當前結點后面插入一個標記結點.
*
* @param f 當前結點的后繼結點
* @return true 插入成功
*/
boolean appendMarker(Node f) {
return casNext(f, new Node(f));
}
/**
* 輔助刪除結點方法.
*
* @param b 當前結點的前驅結點
* @param f 當前結點的后繼結點
*/
void helpDelete(Node b, Node f) {
/*
* 重新檢查一遍結點位置
* 確保b和f分別為當前結點的前驅/后繼
*/
if (f == next && this == b.next) {
if (f == null || f.value != f) // f為null或非標記結點
casNext(f, new Node(f));
else // 刪除當前結點
b.casNext(this, f.next);
}
}
/**
* 返回結點的value值.
*
* @return 標記結點或最底層頭結點，直接返回null
*/
V getValidValue() {
Object v = value;
if (v == this || v == BASE_HEADER) // 標記結點或最底層頭結點，直接返回null
return null;
V vv = (V) v;
return vv;
}
/**
* 返回當前結點的一個Immutable快照.
*/
AbstractMap.SimpleImmutableEntry createSnapshot() {
Object v = value;
if (v == null || v == this || v == BASE_HEADER)
return null;
V vv = (V) v;
return new AbstractMap.SimpleImmutableEntry(key, vv);
}
// UNSAFE mechanics
private static final sun.misc.Unsafe UNSAFE;
private static final long valueOffset;
private static final long nextOffset;
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class k = Node.class;
valueOffset = UNSAFE.objectFieldOffset
(k.getDeclaredField("value"));
nextOffset = UNSAFE.objectFieldOffset
(k.getDeclaredField("next"));
} catch (Exception e) {
throw new Error(e);
}
}
}
索引結點：Index
Index結點是除底層鏈外，其余各層鏈表中的非頭結點（見示意圖中的藍色結點）。每個Index結點包含3個指針：down、right、node。
down和right指針分別指向下層結點和后繼結點，node指針指向其最底部的node結點。
static class Index {
final Node node; // node指向最底層鏈表的Node結點
final Index down; // down指向下層Index結點
volatile Index right; // right指向右邊的Index結點
Index(Node node, Index down, Index right) {
this.node = node;
this.down = down;
this.right = right;
}
/**
* CAS更新右邊的Index結點
*
* @param cmp 當前結點的右結點
* @param val 希望更新的結點
*/
final boolean casRight(Index cmp, Index val) {
return UNSAFE.compareAndSwapObject(this, rightOffset, cmp, val);
}
/**
* 判斷Node結點是否已經刪除.
*/
final boolean indexesDeletedNode() {
return node.value == null;
}
/**
* CAS插入一個右邊結點newSucc.
*
* @param succ 當前的后繼結點
* @param newSucc 新的后繼結點
*/
final boolean link(Index succ, Index newSucc) {
Node n = node;
newSucc.right = succ;
return n.value != null && casRight(succ, newSucc);
}
/**
* 跳過當前結點的后繼結點.
*
* @param succ 當前的后繼結點
*/
final boolean unlink(Index succ) {
return node.value != null && casRight(succ, succ.right);
}
// Unsafe mechanics
private static final sun.misc.Unsafe UNSAFE;
private static final long rightOffset;
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class k = Index.class;
rightOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("right"));
} catch (Exception e) {
throw new Error(e);
}
}
}
頭索引結點：HeadIndex
HeadIndex結點是各層鏈表的頭結點，它是Index類的子類，唯一的區別是增加了一個level字段，用于表示當前鏈表的級別，越往上層，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;
}
}
構造器定義和初始化
ConcurrentSkipListMap一共定義了4種構造器：
空構造器
/**
* 構造一個新的空Map.
*/
public ConcurrentSkipListMap() {
this.comparator = null;
initialize();
}
指定比較器的構造器
/**
* 構造一個新的空Map.
* 并指定比較器.
*/
public ConcurrentSkipListMap(Comparator comparator) {
this.comparator = comparator;
initialize();
}
從給定Map構建的構造器
/**
* 從已給定的Map構造一個新Map.
*/
public ConcurrentSkipListMap(Map m) {
this.comparator = null;
initialize();
putAll(m);
}
從給定SortedMap構建的構造器
/**
* 從已給定的SortedMap構造一個新Map.
* 并且Key的順序與原來保持一致.
*/
public ConcurrentSkipListMap(SortedMap m) {
this.comparator = m.comparator();
initialize();
buildFromSorted(m);
}
注：ConcurrentSkipListMap會基于比較器——Comparator ，來進行鍵Key的比較，如果構造時未指定Comparator ，那么就會按照Key的自然順序進行比較，所謂Key的自然順序是指key實現Comparable接口。
上述所有構造器都調用了initialize方法：
private void initialize() {
keySet = null;
entrySet = null;
values = null;
descendingMap = null;
head = new HeadIndex(new Node(null, BASE_HEADER, null),null, null, 1);
}
initialize方法將一些字段置初始化null，然后將head指針指向新創建的HeadIndex結點。初始化完成后，ConcurrentSkipListMap的結構如下：
其中，head和BASE_HEADER都是ConcurrentSkipListMap的字段：
/**
* 最底層鏈表的頭指針BASE_HEADER
*/
private static final Object BASE_HEADER = new Object();
/**
* 最上層鏈表的頭指針head
*/
private transient volatile HeadIndex head;
四、ConcurrentSkipListMap的核心操作
put操作
put操作本身很簡單，需要注意的是ConcurrentSkipListMap在插入鍵值對時，Key和Value都不能為null：
/**
* 插入鍵值對.
*
* @param key 鍵
* @param value 值
* @return 如果key存在，返回舊value值；否則返回null
*/
public V put(K key, V value) {
if (value == null) // ConcurrentSkipListMap的Value不能為null
throw new NullPointerException();
return doPut(key, value, false);
}
上述方法內部調用了doPut來做實際的插入操作：
/**
* 插入鍵值對.
*
* @param onlyIfAbsent true: 僅當Key不存在時才進行插入
*/
private V doPut(K key, V value, boolean onlyIfAbsent) {
Node z; // z指向待添加的Node結點
if (key == null) // ConcurrentSkipListMap的Key不能為null
throw new NullPointerException();
Comparator cmp = comparator;
outer:
for (; ; ) {
// b是“是小于且最接近給定key”的Node結點(或底層鏈表頭結點)
for (Node b = findPredecessor(key, cmp), n = b.next; ; ) {
if (n != null) { // b存在后驅結點： b -> n -> f
Object v;
int c;
Node f = n.next; // f指向b的后驅的后驅
if (n != b.next) // 存在并發修改,放棄并重試
break;
if ((v = n.value) == null) { // n為標記刪除結點
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b為標記刪除結點
break;
if ((c = cpr(cmp, key, n.key)) > 0) { // 向后遍歷,找到第一個大于key的結點
b = n;
n = f;
continue;
}
if (c == 0) { // 存在Key相同的結點
if (onlyIfAbsent || n.casValue(v, value)) {
V vv = (V) v;
return vv;
}
break; // CAS更新失敗,則重試
}
}
z = new Node(key, value, n);
if (!b.casNext(n, z)) // 嘗試插入z結點： b -> z -> n
break; // CAS插入失敗，則重試
break outer; // 跳出最外層循環
}
}
int rnd = ThreadLocalRandom.nextSecondarySeed(); // 生成一個隨機數種子
if ((rnd & 0x80000001) == 0) { // 為true表示需要增加層級
/**
* 以下方法用于創建新層級
*/
int level = 1, max;
while (((rnd >>>= 1) & 1) != 0) // level表示新的層級,通過下面這個while循環可以確認新的層級數
++level;
Index idx = null;
HeadIndex h = head;
if (level <= (max = h.level)) { // CASE1: 新層級level沒有超過最大層級head.level（head指針指向最高層）
// 以“頭插法”創建level個Index結點,idx最終指向最高層的Index結點
for (int i = 1; i <= level; ++i)
idx = new Index(z, idx, null);
}
else { // CASE2: 新層級level超過了最大層級head.level
level = max + 1; // 重置level為最大層級+1
// 生成一個Index結點數組,idxs[0]不會使用
Index[] idxs = (Index[]) new Index[level + 1];
for (int i = 1; i <= level; ++i)
idxs[i] = idx = new Index(z, idx, null);
// 生成新的HeadIndex結點
for (; ; ) {
h = head;
int oldLevel = h.level; // 原最大層級
if (level <= oldLevel)
break;
HeadIndex newh = h;
Node oldbase = h.node; // oldbase指向最底層鏈表的頭結點
for (int j = oldLevel + 1; j <= level; ++j)
newh = new HeadIndex(oldbase, newh, idxs[j], j);
if (casHead(h, newh)) {
h = newh;
idx = idxs[level = oldLevel];
break;
}
}
}
/**
* 以下方法用于鏈接新層級的各個HeadIndex和Index結點
*/
splice:
for (int insertionLevel = level; ; ) { // 此時level為oldLevel，即原最大層級
int j = h.level;
for (Index q = h, r = q.right, t = idx; ; ) {
if (q == null || t == null)
break splice;
if (r != null) {
Node n = r.node;
int c = cpr(cmp, key, n.key);
if (n.value == null) {
if (!q.unlink(r))
break;
r = q.right;
continue;
}
if (c > 0) {
q = r;
r = r.right;
continue;
}
}
if (j == insertionLevel) {
if (!q.link(r, t)) // 在q和r之間插入t，即從 q -> r 變成 q -> t -> r
break;
if (t.node.value == null) {
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;
}
我們先不急著看doPut方法，而是看下其內部的findPredecessor方法，findPredecessor用于查找“小于且最接近給定key”的Node結點，并且這個Node結點必須有上層結點：
/**
* 返回“小于且最接近給定key”的數據結點.
* 如果不存在這樣的數據結點，則返回底層鏈表的頭結點.
*
* @param key 待查找的鍵
*/
private Node findPredecessor(Object key, Comparator cmp) {
if (key == null)
throw new NullPointerException();
/**
* 從最上層開始，往右下方向查找
*/
for (; ; ) {
for (Index q = head, r = q.right, d; ; ) { // 從最頂層的head結點開始查找
if (r != null) { // 存在右結點
Node n = r.node;
K k = n.key;
if (n.value == null) { // 處理結點”懶刪除“的情況
if (!q.unlink(r))
break;
r = q.right;
continue;
}
if (cpr(cmp, key, k) > 0) { // key大于k,繼續向右查找
q = r;
r = r.right;
continue;
}
}
//已經到了level1的層
if ((d = q.down) == null) // 不存在下結點，說明q已經是level1鏈表中的結點了
return q.node; // 直接返回對應的Node結點
// 轉到下一層，繼續查找(level-1層)
q = d;
r = d.right;
}
}
}
看代碼不太直觀，我們還是看下面這個圖：
上圖中，假設要查找的Key為72，則步驟如下：
從最上方head指向的結點開始，比較①號標紅的Index結點的key值，發現3小于72，則繼續向右；
比較②號標紅的Index結點的key值，發現62小于72，則繼續向右
由于此時右邊是null，則轉而向下，一直到⑥號標紅結點；
由于⑥號標紅結點的down字段為空（不能再往下了，已經是level1最低層了），則直接返回它的node字段指向的結點，即⑧號結點。
注意：如果我們要查找key為59的Node結點，返回的不是Key為45的結點，而是key為23的結點。讀者可以自己在紙上比劃下。
回到doPut方法，假設現在待插入的Key為3，則當執行完下面這段代碼后，ConcurrentSkipListMap的結構如下：
/**
* 插入鍵值對.
*
* @param onlyIfAbsent true: 僅當Key不存在時才進行插入
*/
private V doPut(K key, V value, boolean onlyIfAbsent) {
Node z; // z指向待添加的Node結點
if (key == null) // ConcurrentSkipListMap的Key不能為null
throw new NullPointerException();
Comparator cmp = comparator;
outer:
for (; ; ) {
// b是“是小于且最接近給定key”的Node結點(或底層鏈表頭結點)
for (Node b = findPredecessor(key, cmp), n = b.next; ; ) {
if (n != null) { // b存在后驅結點： b -> n -> f
Object v;
int c;
Node f = n.next; // f指向b的后驅的后驅
if (n != b.next) // 存在并發修改,放棄并重試
break;
if ((v = n.value) == null) { // n為標記刪除結點
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b為標記刪除結點
break;
if ((c = cpr(cmp, key, n.key)) > 0) { // 向后遍歷,找到第一個大于key的結點
b = n;
n = f;
continue;
}
if (c == 0) { // 存在Key相同的結點
if (onlyIfAbsent || n.casValue(v, value)) {
V vv = (V) v;
return vv;
}
break; // CAS更新失敗,則重試
}
}
z = new Node(key, value, n);
if (!b.casNext(n, z)) // 嘗試插入z結點： b -> z -> n
break; // CAS插入失敗，則重試
break outer; // 跳出最外層循環
}
// ...
}
}
上面是doPut中的第一個循環，作用就是找到底層鏈表的插入點，然后插入結點（在查找過程中可能會刪除一些已標記的刪除結點）。
插入完成后，doPut方法并沒結束，我們之前說過ConcurrentSkipListMap的分層數是通過一個隨機數生成算法來確定，doPut的后半段，就是這個作用：判斷是否需要增加層級，如果需要就在各層級中插入對應的Index結點。
/**
* 插入鍵值對.
*
* @param onlyIfAbsent true: 僅當Key不存在時才進行插入
*/
private V doPut(K key, V value, boolean onlyIfAbsent) {
// ...
int rnd = ThreadLocalRandom.nextSecondarySeed(); // 生成一個隨機數種子
if ((rnd & 0x80000001) == 0) { // 為true表示需要增加層級
/**
* 以下方法用于創建新層級
*/
int level = 1, max;
while (((rnd >>>= 1) & 1) != 0) // level表示新的層級,通過下面這個while循環可以確認新的層級數
++level;
Index idx = null;
HeadIndex h = head;
if (level <= (max = h.level)) { // CASE1: 新層級level沒有超過最大層級head.level（head指針指向最高層）
// 以“頭插法”創建level個Index結點,idx最終指向最高層的Index結點
for (int i = 1; i <= level; ++i)
idx = new Index(z, idx, null);
}
else { // CASE2: 新層級level超過了最大層級head.level
level = max + 1; // 重置level為最大層級+1
// 生成一個Index結點數組,idxs[0]不會使用
Index[] idxs = (Index[]) new Index[level + 1];
for (int i = 1; i <= level; ++i)
idxs[i] = idx = new Index(z, idx, null);
// 生成新的HeadIndex結點
for (; ; ) {
h = head;
int oldLevel = h.level; // 原最大層級
if (level <= oldLevel)
break;
HeadIndex newh = h;
Node oldbase = h.node; // oldbase指向最底層鏈表的頭結點
for (int j = oldLevel + 1; j <= level; ++j)
newh = new HeadIndex(oldbase, newh, idxs[j], j);
if (casHead(h, newh)) {
h = newh;
idx = idxs[level = oldLevel];
break;
}
}
}
/**
* 以下方法用于鏈接新層級的各個HeadIndex和Index結點
*/
splice:
for (int insertionLevel = level; ; ) { // 此時level為oldLevel，即原最大層級
int j = h.level;
for (Index q = h, r = q.right, t = idx; ; ) {
if (q == null || t == null)
break splice;
if (r != null) {
Node n = r.node;
int c = cpr(cmp, key, n.key);
if (n.value == null) {
if (!q.unlink(r))
break;
r = q.right;
continue;
}
if (c > 0) {
q = r;
r = r.right;
continue;
}
}
if (j == insertionLevel) {
if (!q.link(r, t)) // 在q和r之間插入t，即從 q -> r 變成 q -> t -> r
break;
if (t.node.value == null) {
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的結構如下所示：
remove操作
ConcurrentSkipListMap在刪除鍵值對時，不會立即執行刪除，而是通過引入“標記結點”，以“懶刪除”的方式進行，以提高并發效率。
public V remove(Object key) {
return doRemove(key, null);
}
remove方法很簡單，內部調用了doRemove方法：
final V doRemove(Object key, Object value) {
if (key == null)
throw new NullPointerException();
Comparator cmp = comparator;
outer:
for (; ; ) {
// b指向“小于且最接近給定key”的Node結點(或底層鏈表頭結點)
for (Node b = findPredecessor(key, cmp), n = b.next; ; ) { // b -> n
Object v;
int c;
if (n == null)
break outer;
Node f = n.next; // b -> n -> f
if (n != b.next) // 一致性判斷
break;
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b is deleted
break;
if ((c = cpr(cmp, key, n.key)) < 0)
break outer;
if (c > 0) {
b = n;
n = f;
continue;
}
// 此時n指向查到的結點
if (value != null && !value.equals(v))
break outer;
if (!n.casValue(v, null)) // 更新查找到的結點的value為null
break;
// 在n和f之間添加標記結點，并將b直接指向f
if (!n.appendMarker(f) || !b.casNext(n, f)) // n -> marker -> f
findNode(key); // retry via findNode
else {
findPredecessor(key, cmp); // 刪除Index結點
if (head.right == null) // 減少層級
tryReduceLevel();
}
V vv = (V) v;
return vv;
}
}
return null;
}
還是通過示例來理解上述代碼，假設現在要刪除Key==23的結點，刪除前ConcurrentSkipListMap的結構如下：
doRemove方法首先會找到待刪除的結點，在它和后繼結點之間插入一個value為null的標記結點（如下圖中的綠色結點），然后改變其前驅結點的指向：
最后，doRemove會重新調用一遍findPredecessor方法，解除被刪除結點上的Index結點之間的引用：
這樣Key==23的結點其實就被孤立，再后續查找或插入過程中，會被完全清除或被GC回收。
get操作
最后，我們來看下ConcurrentSkipListMap的查找操作——get方法。
public V get(Object key) {
return doGet(key);
}
內部調用了doGet方法：
private V doGet(Object key) {
if (key == null)
throw new NullPointerException();
Comparator cmp = comparator;
outer:
for (; ; ) {
// b指向“小于且最接近給定key”的Node結點(或底層鏈表頭結點)
for (Node b = findPredecessor(key, cmp), n = b.next; ; ) {
Object v;
int c;
if (n == null)
break outer;
Node f = n.next; // b -> n -> f
if (n != b.next)
break;
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b is deleted
break;
if ((c = cpr(cmp, key, n.key)) == 0) {
V vv = (V) v;
return vv;
}
if (c < 0)
break outer;
b = n;
n = f;
}
}
return null;
}
doGet方法非常簡單：
首先找到“小于且最接近給定key”的Node結點，然后用了三個指針：b -> n -> f，
n用于定位最終查找的Key，然后順著鏈表一步步向下查，比如查找KEY==45，則最終三個指針的位置如下：
