一、跳表（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() 方法实现元素去重。