ConcurrentSkipListMap 是基于 SkipList 实现的，SkipList 称为跳跃表或跳表，是一种数据结构。

并发版本为什么采用跳表而不是树呢？原因也很简单，因为跳表更易于实现高效并发算法。

在非线程安全的 Map 容器中，用 TreeMap 容器来存取大数据；在线程安全的 Map 容器中，用 SkipListMap 容器来存取大数据。

什么是跳跃表？

跳跃表是基于链表扩展实现的一种特殊链表，类似于树的实现，跳跃表不仅实现了横向链表，还实现了垂直方向的分层索引。

一个跳跃表由若干层链表组成，每一层都实现了一个有序链表索引，只有最底层包含了所有数据，每一层由下往上依次通过一个指针指向上层相同值的元素，每层数据依次减少，等到了最顶层就只会保留部分数据了。

跳跃表的这种结构，是利用了空间换时间的方法来提高了查询效率。程序总是从最顶层开始查询访问，通过判断元素值来缩小查询范围。

ConcurrentSkipListMap 的用法：

代码示例：

public static void main(String[] args) {Map<String, String> map = new ConcurrentSkipListMap<>(Collections.reverseOrder());map.put("a", "abstract");map.put("c", "call");map.put("b", "basic");System.out.println(map.toString());
}

程序输出为：

{c=call, b=basic, a=abstract}

基本实现原理：

跳表是基于链表的，在链表的基础上加了多层索引结构。我们通过一个简单的例子来看下，假定容器中包含如下元素：

3, 6, 7, 9, 12, 17, 19, 21, 25, 26

对 Map 来说，这些值可以视为键。ConcurrentSkipListMap 会构造类似下图所示的跳表结构：

最下面一层，就是最基本的单向链表，这个链表是有序的。虽然是有序的，但我们知道，与数组不同，链表不能根据索引直接定位，不能进行二分查找。

为了快速查找，跳表有多层索引结构，这个例子中有两层，第一层有 5 个节点，第二层有 2 个节点。高层的索引节点一定同时是低层的索引节点，比如 9 和 21。

高层的索引节点少，低层的多，统计概率上，第一层索引节点是实际元素数的 1/2，第二层是第一层的 1/2，逐层减半，但这不是绝对的，有随机性，只是大概如此。

对于每个索引节点，有两个指针，一个向右，指向下一个同层的索引节点，另一个向下，指向下一层的索引节点或基本链表节点。 有了这个结构，就可以实现类似二分查找了，查找元素总是从最高层开始，将待查值与下一个索引节点的值进行比较，如果大于索引节点，就向右移动，继续比较，如果小于，则向下移动到下一层进行比较。

下图两条线展示了查找值 19 和 8 的过程：

这个结构是如何构建起来的呢？

与二叉树类似，这个结构是在更新过程中进行保持的，保存元素的基本思路是：

1、先保存到基本链表，找到待插入的位置，找到位置后，先插入基本链表。

2、更新索引层。

对于索引更新，随机计算一个数，表示为该元素最高建几层索引，一层的概率为 1/2，二层为 1/4，三层为 1/8，依次类推。然后从最高层到最低层，在每一层，为该元素建立索引节点，建的过程也是先查找位置，再插入。
对于删除元素，ConcurrentSkipListMap 不是一下子真的进行删除，为了避免并发冲突，有一个复杂的标记过程，在内部遍历元素的过程中会真正删除。