JDK ConcurrentSkipListMap 跳表数据结构

在 JDK 并发包中，除了常用的哈希表外，还实现了一种能够在高并发中保持有序性的数据结构：`跳表`。
之前在看《Redis设计与实现》一书时，了解到`Redis`实现中也用到了该数据结构，但是该书的作者讲解的不是太清楚，今天看《实战Java高并发程序设计》一书时才有种茅塞顿开的感觉。
下面是一个简单的数据结构图：
![微信截图_20180925171203.png][1]
JDK 源码中注释图：
```java
     * 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
     * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
```
可以看到，跳表的本质是同时维护了多张链表，并且链表是分层的。两个主要特征如下：
* 最底层维护了跳表的所有元素，并且是有序的
* 高层级的链表元素是低层级链表元素的子集

在上图中，查找值为 8 的节点，如果是以单链表的查找方式去查找，那么从 1 遍历到 8 ，查找次数是 7 次，但是跳表的查找方式如下：
![微信截图_20180925171203.png][2]
查找次数是 6。
`ConcurrentSkipListMap`用到的三个数据结构如下：
Node：
```java
static final class Node<K,V> {
    final K key;
    volatile Object value;
    volatile Node<K,V> next;
    //...
}
```
和普通链表的 Node 结构没什么区别。
Index：
```java
static class Index<K,V> {
    final Node<K,V> node;
    final Index<K,V> down;
    volatile Index<K,V> right;
    //...
}
```
`Index`包装了`Node`，并且添加了`down`向下和`right`向右的引用。
HeadIndex：
```java
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;
    }
}
```
`HeadIndex`为每一层的表头，`level`记录了当前属于那一层，它继承自`Index`。
  [1]: https://0o0.me/usr/uploads/2018/09/2339301789.png
  [2]: https://0o0.me/usr/uploads/2018/09/2641442349.png

JDK ConcurrentSkipListMap 跳表数据结构

发表评论：