ConcurrentSkipListMap
1.介绍
跳表是一种可以用来快速查找的数据结构，类似于平衡树，他们都可以对元素进行快速的查找。但一个重要的区别是：对平衡树的插入往往可能导致平衡树进行一次全局的调整；而对跳表的插入和删除之需要的局部数据操作即可。这样的好处是，在高并发环境下，对平衡树的操作需要一个全局锁来保证线程安全，但是对于跳表则只需要部分锁，这样会拥有更好地性能。 就查询的性能而言，跳表的时间复杂度也是O(logN)。因此，在并发的数据结构中，JDK使用跳表实现一个Map。 跳表的本质是分层的多个链表，最上层的元素最少，查找操作从最上层开始进行。 使用跳表实现Map和使用Hash算法实现Map的另一个不同之处在于，HashMap并不会维护元素的顺序，而跳表内的所有元素都是排序的，在对跳表遍历时会得到一个有序的结果。因此，如果需要一个有序的并发安全的Map，使用跳表是不二的选择。
2.代码分析
ConcurrentSkipListMap是使用跳表实现的并发安全的Map结构，其内部由几个关键的数据结构组成。首先是Node。一个Node表示跳表的某一层的一个节点。
代码语言：javascript复制 //一个Node表示跳表的一个节点
static final class Node<K,V> {
//该节点的key
final K key;
//该节点的value
volatile Object value;
//数据域，指向同一层的后继节点
volatile Node<K,V> next;
Node(K key, Object value, Node<K,V> next) {
this.key = key;
this.value = value;
this.next = next;
}另一个重要的数据结构是Index，它内部包装了Node，同时增加了向下的引用和向右的引用：
代码语言：javascript复制 static class Index<K,V> {
//内部封装了一个Node
final Node<K,V> node;
//数据域，指向下一层的节点
final Index<K,V> down;
//数据域，指向同一层的右边的节点
volatile 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;
}此外，还有一个HeadIndex的数据结构，表示链表头部的第一个Index，并记录当前在第几层：
代码语言：javascript复制 //HeadIndex表示第level层的表头Index
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;
}
}对于跳表的所有操作，就是组织好这些Index之间的连接关系。
3.适用场景
如果想在高并发环境下，使用一个有序的Map，那么ConcurrentSkipListMap将是不二的选择。
