ConcurrentSkipListMap

ConcurrentSkipListMap

底层使用的是SkipList结构，也就是跳表

SkipList

SkipList让已排序的数据分布在多层链表中，以0-1随机数决定一个数据的向上攀升与否，通过以时间换空间，在每个节点中增加了向前的指针，在插入、删除、查找时可以忽略一些不可能涉及到的节点，从而提高效率

SkipList具备如下特性：

• 由很多层结构组成，level是通过一定的概率随机产生的
• 每一层都是一个有序的链表，默认是升序，也可以根据创建映射时所提供的Comparator进行排序，具体取决于使用的构造方法
• 最底层(Level 1)的链表包含所有元素
• 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现
• 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素

ConcurrentSkipListMap实现

ConcurrentSkipListMap内部采用了SkipList数据结构实现，使用三个内部类来构建这样的结构：Node、Index、HeadIndex

* Head nodes          Index nodes
* +-+    right        +-+                      +-+
* |2|---------------->| |--------------------->| |->null
* +-+                 +-+                      +-+
*  | down              |                        |
*  v                   v                        v
* +-+            +-+  +-+       +-+            +-+       +-+
* |1|----------->| |->| |------>| |----------->| |------>| |->null
* +-+            +-+  +-+       +-+            +-+       +-+
*  v              |    |         |              |         |
* Nodes  next     v    v         v              v         v
* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+

Node结构

与一般的单链表结构相似

static final class Node<K,V> {
    final K key;
    volatile Object value;
    volatile Node<K,V> next;
}

Index结构

提供了一个基于Node节点的索引，以及向下和向右的索引

static class Index<K,V> {
    final Node<K,V> node;
    final Index<K,V> down;
    volatile Index<K,V> right;
}

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