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;
}
}
原文始发于微信公众号（bug生产基地）：并发容器之ConcurrentSkipListMap
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/257150.html
