17.3 基于跳表的Map和Set

Java并发包中与TreeMap/TreeSet对应的并发版本是ConcurrentSkipListMap和Concurrent-SkipListSet，本节就来简要探讨这两个类，先介绍基本概念，然后介绍基本实现原理。

17.3.1 基本概念

我们知道，TreeSet是基于TreeMap实现的，与此类似，ConcurrentSkipListSet也是基于ConcurrentSkipListMap实现的，所以我们主要介绍ConcurrentSkipListMap。

ConcurrentSkipListMap是基于SkipList实现的，SkipList称为跳跃表或跳表，是一种数据结构，稍后我们会进一步介绍。并发版本为什么采用跳表而不是树呢？原因也很简单，因为跳表更易于实现高效并发算法。ConcurrentSkipListMap有如下特点。

1）没有使用锁，所有操作都是无阻塞的，所有操作都可以并行，包括写，多线程可以同时写。
2）与ConcurrentHashMap类似，迭代器不会抛出ConcurrentModificationException，是弱一致的，迭代可能反映最新修改也可能不反映，一些方法如putAll、clear不是原子的。
3）与ConcurrentHashMap类似，同样实现了ConcurrentMap接口，支持一些原子复合操作。
4）与TreeMap一样，可排序，默认按键的自然顺序，也可以传递比较器自定义排序，实现了SortedMap和NavigableMap接口。

看段简单的使用代码：

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}

表示是有序的。

我们之前介绍过ConcurrentSkipListMap的大部分方法，有序的方法与TreeMap是类似的，原子复合操作与ConcurrentHashMap是类似的，此处不再赘述。

需要说明的是ConcurrentSkipListMa的size方法，与大多数容器实现不同，这个方法不是常量操作，它需要遍历所有元素，复杂度为O(N)，而且遍历结束后，元素个数可能已经变了。一般而言，在并发应用中，这个方法用处不大。下面我们主要介绍其基本实现原理。

17.3.2 基本实现原理

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

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

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

图17-1 跳表结构示例

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

为了快速查找，跳表有多层索引结构，这个例子中有两层，第一层有5个节点，第二层有2个节点。高层的索引节点一定同时是低层的索引节点，比如9和21。高层的索引节点少，低层的多。统计概率上，第一层索引节点是实际元素数的1/2，第二层是第一层的1/2，逐层减半，但这不是绝对的，有随机性，只是大致如此。每个索引节点有两个指针：一个向右，指向下一个同层的索引节点；另一个向下，指向下一层的索引节点或基本链表节点。

有了这个结构，就可以实现类似二分查找了。查找元素总是从最高层开始，将待查值与下一个索引节点的值进行比较，如果大于索引节点，就向右移动，继续比较，如果小于索引节点，则向下移动到下一层进行比较。图17-2所示的两条线展示了查找值19和8的过程。

图17-2 在跳表中查找的示例

对于值19，查找过程是：
1）与9相比，大于9；
2）向右与21相比，小于21；
3）向下与17相比，大于17；
4）向右与21相比，小于21；
5）向下与19相比，找到。

对于值8，查找过程是：
1）与9相比，小于9；
2）向下与6相比，大于6；
3）向右与9相比，小于9；
4）向下与7相比，大于7；
5）向右与9相比，小于9，不能再向下，没找到。

这个结构是有序的，查找的性能与二叉树类似，复杂度是O(log(N))。不过，这个结构是如何构建起来的呢？与二叉树类似，这个结构是在更新过程中进行保持的，保存元素的基本思路是：
1）先保存到基本链表，找到待插入的位置，找到位置后，插入基本链表；
2）更新索引层。

对于索引更新，随机计算一个数，表示为该元素最高建几层索引，一层的概率为1/2，二层的概率为1/4，三层的概率为1/8，以此类推。然后从最高层到最低层，在每一层，为该元素建立索引节点，建立索引节点的过程也是先查找位置，再插入。

对于删除元素，ConcurrentSkipListMap不是直接进行真正删除，而是为了避免并发冲突，有一个复杂的标记过程，在内部遍历元素的过程中进行真正删除。

以上我们只是介绍了基本思路，为了实现并发安全、高效、无锁非阻塞，Concurrent-SkipListMap的实现非常复杂，具体我们就不探讨了，感兴趣的读者可以参考其源码，其中提到了多篇学术论文，论文中描述了它参考的一些算法。对于常见的操作，如get/put/remove/containsKey, ConcurrentSkipListMap的复杂度都是O(log(N))。

上面介绍的SkipList结构是为了便于并发操作的，如果不需要并发，可以使用另一种更为高效的结构，数据和所有层的索引放到一个节点中，如图17-3所示。

图17-3 数据和索引都在一个节点中的跳表

对于一个元素，只有一个节点，只是每个节点的索引个数可能不同，在新建一个节点时，使用随机算法决定它的索引个数。平均而言，1/2的元素有两个索引，1/4的元素有三个索引，以此类推。

简单总结下，ConcurrentSkipListMap和ConcurrentSkipListSet基于跳表实现，有序，无锁非阻塞，完全并行，主要操作复杂度为O(log(N))。