Java 并发编程之 ConcurrentSkipListMap
Java juc About 2,052 words介绍
线程安全的排序集合。
跳跃列表
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 | ...
+------+ +------+
跳跃列表
Views: 1,953 · Posted: 2021-11-03
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...