Java 并发编程之 ConcurrentSkipListMap

介绍

线程安全的排序集合。

跳跃列表

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 节点

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

HeadIndex 头索引

每一层头节点

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

put 示意图

remove 流程

正常链表

     +------+       +------+      +------+
...  |   b  |------>|   n  |----->|   f  | ...
     +------+       +------+      +------+

因为链表的并发基于CAS，所以可能存在删除时和插入并发的异常，在删除n时不直接删除，而选择使用一个标记节点marker

     +------+       +------+      +------+       +------+
...  |   b  |------>|   n  |----->|marker|------>|   f  | ...
     +------+       +------+      +------+       +------+

删除n节点时直接将b节点的next字段指向f节点

     +------+                                    +------+
...  |   b  |----------------------------------->|   f  | ...
     +------+                                    +------+

跳跃列表

https://en.wikipedia.org/wiki/Skip_list