本文主要是介绍并发容器之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;
}
}
https://zhhll.icu/2022/多线程/并发容器/5.ConcurrentSkipListMap/
本文由 mdnice 多平台发布
这篇关于并发容器之ConcurrentSkipListMap的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
