Java 集合 (11) -- ConcurrentSkipListMap 类

1. 简介

public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable {
    }

ConcurrentSkipListMap 的底层数据结构是跳表。为了实现 SkipList，ConcurrentSkipListMap 提供了三个内部类来构建这样的链表结构：Node、Index、HeadIndex。其中 Node 表示最底层的单链表有序节点、Index 表示为基于 Node 的索引层，HeadIndex 用来维护索引层次

为什么 Redis 选择使用跳表而不是红黑树来实现有序集合 ？首先，我们来分析下 Redis 的有序集合支持的操作：

1. 插入元素
2. 删除元素
3. 查找元素
4. 有序输出所有元素
5. 查找区间内所有元素

其中，前 4 项红黑树都可以完成，且时间复杂度与跳表一致。但是，最后一项，红黑树的效率就没有跳表高了。
在跳表中，要查找区间的元素，我们只要定位到两个区间端点在最低层级的位置，然后按顺序遍历元素就可以了，非常高效。而红黑树只能在定位到端点后，再从首位置开始每次都要查找后继节点，相对来说是比较耗时的。

另外，对平衡树的插入和删除往往很可能导致平衡树进行一次全局的调整。而对跳表的插入和删除只需要对整个数据结构的局部进行操作即可。这样带来的好处是：在高并发的情况下，你需要一个全局锁来保证整个平衡树的线程安全。而对于跳表，你只需要部分锁即可，这样，在高并发环境下，使用跳表就可以拥有更好的性能。

此外，跳表实现起来很容易且易读，红黑树实现起来相对困难，所以 Redis 选择使用跳表来实现有序集合。

2. 继承体系

3. 存储结构

4. 内部类

1. Node 类：数据节点，典型的单链表结构

   static final class Node<K,V> {
         final K key;// 注意：这里value的类型是Object，而不是V// 在删除元素的时候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;}Node(Node<K,V> next) {
         this.key = null;this.value = this; // 当前元素本身(marker)this.next = next;}
   }
   

2. Index 类：索引节点，存储着对应的node值，及向下和向右的索引指针

   static class Index<K,V> {
         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;}
   }
   

3. HeadIndex 类：头索引节点，继承自Index，并扩展一个level字段，用于记录索引的层级

   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;}
   }
   

5. 构造器

1. public ConcurrentSkipListMap() {
         this.comparator = null;initialize();
   }
   

2. public ConcurrentSkipListMap(Comparator<? super K> comparator) {
         this.comparator = comparator;initialize();
   }
   

3. public ConcurrentSkipListMap(Map<? extends K, ? extends V> m) {
         this.comparator = null;initialize();putAll(m);
   }
   

4. public ConcurrentSkipListMap(SortedMap<K, ? extends V> m) {
         this.comparator = m.comparator();initialize();buildFromSorted(m);
   }
   

四个构造方法里面都调用了initialize()这个方法：

private static final Object BASE_HEADER = new Object();private void initialize() {
    keySet = null;entrySet = null;values = null;descendingMap = null;// Node(K key, Object value, Node<K,V> next)// HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level)head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null), null, null, 1);
}

这里初始化了一些属性，并创建了一个头索引节点，里面存储着一个数据节点，这个数据节点的值是空对象，且它的层级是1。所以，初始化的时候，跳表中只有一个头索引节点，层级是1，数据节点是一个空对象，down和right都是null。

通过内部类的结构我们知道，一个头索引指针包含node, down, right三个指针，为了便于理解，我们把指向node的指针用虚线表示，其它两个用实线表示，也就是虚线不是表明方向的。

6. 常用方法

1. public V put(K key, V value)：添加元素
2. public V remove(Object key)：删除元素，就是把各层级中对应的元素删除即可
3. public V get(Object key)：查找元素