JDK版本：AdoptOpenJDK 11.0.10+9

1 基本概念

ConcurrentSkipListMap是在JDK 1.6中新增的，为了对高并发场景下的有序Map提供更好的支持，它有几个特点：

• 高并发场景
• key是有序的
• 添加、删除、查找操作都是基于跳表结构（Skip List）实现的
• key和value都不能为null

2 跳表（Skip List）

跳表（Skip List）是一种类似于链表的数据结构，其查询、插入、删除的时间复杂度都是 O(logn)。

在传统的单链表结构中，查找某个元素需要从链表的头部按顺序遍历，直到找到目标元素为止，查找的时间复杂度为O(n)。

而跳表结合了树和链表的特点，其特性如下：

1. 跳表由很多层组成；
2. 每一层都是一个有序的链表；
3. 最底层的链表包含所有元素；
4. 对于每一层的任意一个节点，不仅有指向其下一个节点的指针，也有指向其下一层的指针；
5. 如果一个元素出现在Level n层的链表中，则它在Level n层以下的链表也都会出现。

Skip List例子：

下图是一种可能的跳表结构：

如图，[1]和[40]节点有3层，[8]和[18]节点有2层。每一层都是有序的链表。

如果要查找目标节点[15]，大致过程如下：

1. 首先查看[1]节点的第1层，发现[1]节点的下一个节点为[40]，大于15，那么查找[1]节点的下一层；
2. 查找[1]节点的第2层，发现[1]节点的下一个节点为[8]，小于15，接着查看下一个节点，发现下一个节点是[18]，大于15，因此查找[8]节点的下一层；
3. 查找[8]节点的第2层，发现[8]节点的下一个节点是[10]，小于15，接着查看下一个节点[13]，小于15，接着查看下一个节点[15]，发现其值等于15，因此找到了目标节点，结束查询。

跳表实际上是一种 空间换时间 的数据结构。

3 ConcurrentSkipListMap结构

ConcurrentSkipListMap用到了两种结构的节点。

Node节点代表了真正存储数据的节点，包含了key、value、指向下一个节点的指针next：

    static final class Node<K,V> {
        final K key;     // 键
        V val;           // 值
        Node<K,V> next;  // 指向下一个节点的指针
        Node(K key, V value, Node<K,V> next) {
            this.key = key;
            this.val = value;
            this.next = next;
        }
    }

Index节点代表了跳表的层级，包含了当前节点node、下一层down、当前层的下一个节点right：

    static final class Index<K,V> {
        final Node<K,V> node;   // 当前节点
        final Index<K,V> down;  // 下一层
        Index<K,V> right;       // 当前层的下一个节点
        Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
            this.node = node;
            this.down = down;
            this.right = right;
        }
    }

如图所示，Node节点将真实的数据按顺序链接起来，Index节点组成了跳表中多层次的索引结构。

4 使用案例

下面是对ConcurrentSkipListMap的简单使用的一个例子：

public class ConcurrentSkipListMapTest {

	public static void main(String[] args) {
		ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();
		map.put(4, "4");
		map.put(5, "5");
		map.put(1, "1");
		map.put(6, "6");
		map.put(2, "2");
		
		System.out.println(map.keySet());
		System.out.println(map);
		System.out.println(map.descendingKeySet());
		System.out.println(map.descendingMap());
	}
}

输出为：

[1, 2, 4, 5, 6]
{1=1, 2=2, 4=4, 5=5, 6=6}
[6, 5, 4, 2, 1]
{6=6, 5=5, 4=4, 2=2, 1=1}

源码解析可以看看这篇文章：Java多线程进阶（二五）—— J.U.C之collections框架：ConcurrentSkipListMap