對(duì)于有序并且對(duì)增刪改操作友好的數(shù)據(jù)結(jié)構(gòu)有List、Tree等，對(duì)于Tree實(shí)現(xiàn)起來可能比較復(fù)雜，而SkipList(跳表)也可實(shí)現(xiàn)有序存儲(chǔ)并且增刪改的性能也不錯(cuò)，只是增加了空間復(fù)雜度，是一種空間換時(shí)間的思路，在Java中ConcurrentSkipListMap就是基于跳表實(shí)現(xiàn)的，它可以作為并發(fā)安全的有序集合使用，并且鎖粒度可控，比Collections.synchronizedMap性能要好。至于為什么不用Tree來實(shí)現(xiàn)并發(fā)安全的有序集合，很大程度上是因?yàn)門ree的復(fù)雜性很難控制鎖粒度。

1、SkipList

下面以一個(gè)例子來解釋跳表的原理：

一個(gè)LinkedList，存儲(chǔ)了【1,3,6,8,9,11,15,33】，它的存儲(chǔ)結(jié)構(gòu)是這個(gè)樣子的：

image.png

當(dāng)然作為鏈表，查找操作一個(gè)元素的時(shí)間復(fù)雜度是O(n)，效率更高的樹存儲(chǔ)，可以達(dá)到O(lgn)。但是如上面所說樹的復(fù)雜性較高，實(shí)現(xiàn)起來需要注意很多地方，而在并發(fā)場(chǎng)景下更重要的是樹沒法最小化控制鎖粒度，而跳表則更適合，在SkipList中上面例子的存儲(chǔ)結(jié)構(gòu)可能是這樣的：

image.png

SkipList使用分層的結(jié)構(gòu)，第一層結(jié)構(gòu)和List一樣，往上一層以一定間隔提取數(shù)據(jù)建立一個(gè)類似索引的結(jié)構(gòu)，往上依次可以理解為一級(jí)索引與二級(jí)索引。
比如查找33就不需要從頭遍歷鏈表了，查找路徑是這樣的：

image.png

2、ConcurrentSkipListMap

首先參考上面的圖來介紹ConcurrentSkipListMap中定義的存儲(chǔ)結(jié)構(gòu)

Node：

數(shù)據(jù)存儲(chǔ)還是使用Node節(jié)點(diǎn)，包括key、value、next：

static final class Node<K,V> {
    final K key;
    volatile Object value;
    volatile Node<K,V> next;
......
}

index：

從上面的圖可以知道，還需要一個(gè)結(jié)構(gòu)來定義某一層的某一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)需要存儲(chǔ)的信息有自己所屬的level、下一個(gè)節(jié)點(diǎn)、右一個(gè)節(jié)點(diǎn)、該節(jié)點(diǎn)對(duì)應(yīng)的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;
    }

    /**
     * compareAndSet right field.
     */
    final boolean casRight(Index<K,V> cmp, Index<K,V> val) {
        return RIGHT.compareAndSet(this, cmp, val);
    }

    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);
    }

    final boolean unlink(Index<K,V> succ) {
        return node.value != null && casRight(succ, succ.right);
    }

    // VarHandle mechanics
    private static final VarHandle RIGHT;
    static {
        try {
            MethodHandles.Lookup l = MethodHandles.lookup();
            RIGHT = l.findVarHandle(Index.class, "right", Index.class);
        } catch (ReflectiveOperationException e) {
            throw new Error(e);
        }
    }
}


  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;
    }
}

在ConcurrentSkipListMap中定義了Index和HeadIndex兩個(gè)。

我們從最基本的查詢數(shù)據(jù)方法來看看ConcurrentSkipListMap是怎么實(shí)現(xiàn)的：

private Node<K,V> findNode(Object key) {
    if (key == null)
        throw new NullPointerException(); // don't postpone errors
    Comparator<? super K> cmp = comparator;         //比較器，可以構(gòu)造初始化時(shí)傳入
    outer: for (;;) {
        for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {     //findPredecessor獲取前驅(qū)節(jié)點(diǎn)
            Object v; int c;
            if (n == null)
                break outer;
            Node<K,V> f = n.next;
            if (n != b.next)                // inconsistent read          //兩次讀取不一致，循環(huán)重試
                break;
            if ((v = n.value) == null) {    // n is deleted          //該節(jié)點(diǎn)已被刪除，循環(huán)重試
                n.helpDelete(b, f);
                break;
            }
            if (b.value == null || v == n)  // b is deleted      //前驅(qū)節(jié)點(diǎn)被刪除，循環(huán)重試
                break;
            if ((c = cpr(cmp, key, n.key)) == 0)     //比較節(jié)點(diǎn)key值，相等則返回該節(jié)點(diǎn)value，不等說明這期間發(fā)生了變化，循環(huán)重試
                return n;
            if (c < 0)
                break outer;
            b = n;
            n = f;
        }
    }
    return null;
}

/**
 * Returns a base-level node with key strictly less than given key,
 * or the base-level header if there is no such node.  Also
 * unlinks indexes to deleted nodes found along the way.  Callers
 * rely on this side-effect of clearing indices to deleted nodes.
 * @param key the key
 * @return a predecessor of key
 */
private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
    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;
                if (n.value == null) {
                    if (!q.unlink(r))
                        break;           // restart
                    r = q.right;         // reread r
                    continue;
                }
                if (cpr(cmp, key, k) > 0) {
                    q = r;
                    r = r.right;
                    continue;
                }
            }
            if ((d = q.down) == null)
                return q.node;
            q = d;
            r = d.right;
        }
    }
}

簡(jiǎn)單的說跳表查找數(shù)據(jù)key-A的值的時(shí)候先通過index索引節(jié)點(diǎn)來定位到小于A的level =1的最大索引節(jié)點(diǎn)，再向右遍歷查找到key = A的節(jié)點(diǎn)。（這也是跳表相比與樹的另一個(gè)優(yōu)勢(shì)：跳表查找某一區(qū)間的數(shù)的復(fù)雜度也是lgn，因?yàn)橹灰ㄎ坏阶髤^(qū)間，向右就可以遍歷到右區(qū)間了，而樹對(duì)于獲取區(qū)間值卻不行，Redis中數(shù)據(jù)存儲(chǔ)使用的就是跳表+散列表。當(dāng)然像紅黑樹這種對(duì)于跳表的優(yōu)勢(shì)在于出現(xiàn)的比較早，Java中很多已有的結(jié)構(gòu)都是紅黑樹實(shí)現(xiàn)的，直接用就行了，而跳表用的比較少，如果自己實(shí)現(xiàn)還要寫跳表的邏輯）