JAVA并發容器-ConcurrentSkipListMap，ConcurrentSkipListSet

ConcurrentSkipListMap其實是TreeMap的并發版本。TreeMap使用的是紅黑樹，并且按照key的順序排序（自然順序、自定義順序），但是他是非線程安全的，如果在并發環境下，建議使用ConcurrentHashMap或者​​ConcurrentSkipListMap​​。

ConcurrentSkipListSet其實是TreeSet的并發版本。TreeSet底層使用紅黑樹，并且按照key的順序排序（自然順序、自定義順序），但是他是非線程安全的，如果在并發環境下ConcurrentSkipListSet。

ConcurrentSkipListMap和ConcurrentSkipListSet底層使用跳表資料結構來實作，跳表全稱叫做跳躍表，它是一個随機化的資料結構，可以被看做二叉樹的一個變種，通過使用“跳躍式”查找的方式使得插入、讀取資料時複雜度變成了O（logn）。它在性能上和紅黑樹，AVL樹不相上下，但是跳表的原理非常簡單，目前在Redis和LeveIDB中都有用到。

跳躍表是一種典型的“空間來換取時間”的一個算法，通過在每個節點中增加了向前的指針，進而提升查找的效率。實作跳表的基礎是保證元素有序。

結構圖

從圖中可以看到， 跳躍表主要由以下部分構成：

• 表頭（head）：負責維護跳躍表的節點指針。
• 跳躍表節點：儲存着元素值，以及多個層。
• 層：儲存着指向其他元素的指針。高層的指針越過的元素數量大于等于低層的指針，為了提高查找的效率，程式總是從高層先開始通路，然後随着元素值範圍的縮小，慢慢降低層次。
• 表尾：全部由 NULL 組成，表示跳躍表的末尾。

ConcurrentSkipListMap源碼分析

ConcurrentSkipListMap類圖

資料節點

static final class Node<K,V> {
    final K key;
    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;
    }
...
}      

層級節點

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

查找節點

我們來看下查找9的流程：

head(4)->4(4)->4(3)->4(2)->7(2)->7(1)->9

ConcurrentSkipListMap.findPredecessor()

找到與key距離最近的一個點，如果沒找到傳回頭結點

// 找到與key距離最近的一個點，如果沒找到傳回頭結點
    private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
        if (key == null)
            throw new NullPointerException(); // don't postpone errors
        for (;;) {
            // 從頭結點開始，q就是要找的節點，r是q同層級的右節點，d是q的下一個層級的節點
            for (Index<K,V> q = head, r = q.right, d;;) {
                if (r != null) {
                    // n是r的資料節點
                    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;
                    }
                    // 比較key的大小，key>k則q指q的右節點，繼續下一次循環
                    if (cpr(cmp, key, k) > 0) {
                        q = r;
                        r = r.right;
                        continue;
                    }
                }
                // 表示已經到最底層了
                if ((d = q.down) == null)
                    return q.node;
                // 如果r==null || key<=k,則q指向q下一層級的節點
                q = d;
                r = d.right;
            }
        }
    }      

ConcurrentSkipListMap.get()

private V doGet(Object key) {
        if (key == null)
            throw new NullPointerException();
        Comparator<? super K> cmp = comparator;
        outer: for (;;) {
            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;
                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) {
                    @SuppressWarnings("unchecked") V vv = (V)v;
                    return vv;
                }
                if (c < 0)
                    break outer;
                b = n;
                n = f;
            }
        }
        return null;
    }      

插入結點

明白了查找的原理後，插入、删除就容易了解了。為了儲存跳表的有序性，是以分三步：查找合适位置——進行插入/删除——更新跳表指針，維護層級性。

ConcurrentSkipListMap.doPut()

private V doPut(K key, V value, boolean onlyIfAbsent) {
        Node<K,V> z;             // added node
        if (key == null)
            throw new NullPointerException();
        Comparator<? super K> cmp = comparator;
        outer: for (;;) {
            for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
                if (n != null) {
                    Object v; int c;
                    Node<K,V> f = n.next;
                    if (n != b.next)               // inconsistent read
                        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) {
                        b = n;
                        n = f;
                        continue;
                    }
                    if (c == 0) {
                        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
                }

                z = new Node<K,V>(key, value, n);
                if (!b.casNext(n, z))
                    break;         // restart if lost race to append to b
                break outer;
            }
        }      

删除結點