跳表（SkipList）和 ConcurrentSkipListMap

一、跳表（SkipList）

對于單連結清單，即使連結清單是有序的，如果想要在其中查找某個資料，也隻能從頭到尾周遊連結清單，這樣效率自然就會很低，跳表就不一樣了。跳表是一種可以用來快速查找的資料結構，有點類似于平衡樹。它們都可以對元素進行快速的查找。但一個重要的差別是：

對平衡樹的插入和删除往往很可能導緻平衡樹進行一次全局的調整；而對跳表的插入和删除，隻需要對整個資料結構的局部進行操作即可

。這樣帶來的好處是：

在高并發的情況下，需要一個全局鎖，來保證整個平衡樹的線程安全；而對于跳表，則隻需要部分鎖即可

。這樣，在高并發環境下，就可以擁有更好的性能。就查詢的性能而言，跳表的時間複雜度是 O(logn)。

跳表的本質，其實是同時維護了多個連結清單，并且連結清單是分層的：

其中最低層的連結清單，維護了跳表内所有的元素，每往上一層連結清單，都是下面一層的子集。

跳表内每一層連結清單的元素都是有序的。查找時，可以從頂級連結清單開始找。一旦發現被查找的元素大于目前連結清單中的取值，就會轉入下一層連結清單繼續查找。也就是說在查找過程中，搜尋是跳躍式的。如上圖所示，在跳表中查找元素18：

可以看到，在查找 18 的時候，原來需要周遊 12 次，現在隻需要 7 次即可。針對連結清單長度比較大的時候，建構索引，查找效率的提升就會非常明顯。

從上面很容易看出，

跳表是一種利用空間換時間的算法

。

二、ConcurrentSkipListMap

ConcurrentSkipListMap 是一個線程安全的基于跳躍表實作的非阻塞的 Map，它要求 Map 中的 key 和 value 都不能為 null。相較于哈希實作的 Map，跳表内的所有元素都是有序的；相較于紅黑樹結構 treeMap，ConcurrentSkipListMap 是線程安全的。

ConcurrentSkipListMap 适用于高并發的場景，在資料量一定的情況下，并發的線程越多，ConcurrentSkipListMap 越能展現出他查詢的優勢。

ConcurrentSkipListMap 的存取性能遜色于 ConcurrentHashMap（在 4 線程 1.6 萬資料的條件下，ConcurrentHashMap 存取速度是 ConcurrentSkipListMap 的 4倍左右），它的優勢在于跳表内的所有元素都是有序的。

在非多線程的情況下，應當盡量使用 TreeMap。此外對于并發性相對較低的并行程式可以使用 Collections.synchronizedSortedMap 将 TreeMap 進行包裝，也可以保證線程安全。

三、ConcurrentSkipListMap 資料結構

從源碼可以分析得到 ConcurrentSkipListMap 的整個資料結構如下：

來分别看看 HeadIndex、Index 和 Node 的類資訊：

static class Index<K,V> {
        final Node<K,V> node;
        final Index<K,V> down;
        volatile Index<K,V> right;
    }

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

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

可以看到，Index 包含了 Node 的引用，并用 right 和 down 引用分别指向各自的 Index 域；HeadIndex 繼承自 Index，作為索引的頭節點，維護了跳表中 level 的概念；Node 節點存儲了實際的 key、value 資訊，并用 next 引用建構單連結清單。

具體的源碼分析可以參見這篇文章：https://www.jianshu.com/p/2075a76a43a3

四、ConcurrentSkipListMap 示例

下面是 “多個線程同時操作并且周遊 map” 的示例，以驗證 ConcurrentSkipListMap 的線程安全：

當 map 是 ConcurrentSkipListMap 對象時，程式能正常運作。
當 map 是 TreeMap 對象時，程式會産生 ConcurrentModificationException 異常。

public class ConcurrentSkipListMapTest {

    //private static Map<String, String> MAP = new TreeMap<String, String>();
    private static Map<String, String> MAP = new ConcurrentSkipListMap<String, String>();

    public static void main(String[] args) {
        // 同時啟動兩個線程對map進行操作！
        new MyThread("A").start();
        new MyThread("B").start();
    }

    private static void printAll() {
        String key, value;
        Iterator iterator = MAP.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator.next();
            key = (String) entry.getKey();
            value = (String) entry.getValue();
            System.out.print("(" + key + ", " + value + "), ");
        }
        System.out.println();
    }

    private static class MyThread extends Thread {
        MyThread(String name) {
            super(name);
        }

        @Override
        public void run() {
            int i = 0;
            while (i++ < 6) {
                // "線程名" + "序号"
                String val = Thread.currentThread().getName() + i;
                MAP.put(val, "0");
                printAll();
            }
        }
    }
}

五、ConcurrentSkipListSet

Java 中所有 Set 幾乎都是内部用一個 Map 來實作, 因為 Map 裡的 KeySet() 就是一個 Set 集合，而 value 是假值，全部使用同一個 Object 即可。

ConcurrentSkipListSet 也不例外，它内部使用 ConcurrentSkipListMap 集合實作，并利用其 addIfAbsent() 方法實作元素去重。

跳表（SkipList） 和 ConcurrentSkipListMap