一、跳表（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?{
?????final?Node?node;
?????final?Index?down;
?????volatile?Index?right;
?} ?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;
?????}
?} static?final?class?Node?{
????final?K?key;
????volatile?Object?value;
????volatile?Node?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?MAP?=?new?TreeMap();
????private?static?Map?MAP?=?new?ConcurrentSkipListMap();
????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++? 五、ConcurrentSkipListSet
Java 中所有 Set 几乎都是内部用一个 Map 来实现, 因为 Map 里的 KeySet() 就是一个 Set 集合，而 value 是假值，全部使用同一个 Object 即可。
ConcurrentSkipListSet 也不例外，它内部使用 ConcurrentSkipListMap 集合实现，并利用其 addIfAbsent() 方法实现元素去重。
