2022-06-16

java基础

5 分钟读完 (大约 783 个字)

ConcurrentSkipListMap原理

SkipList

Skip list让已排序的数据分布在多层链表中，通过“空间来换取时间”的一个算法，在插入、删除、查找时可以忽略一些不可能涉及到的结点，从而提高了效率。

其插入和查找的效率O(logn)，其效率不低于红黑树，但是其原理和实现的复杂度要比红黑树简单多了。

特性

由很多层结构组成，level是通过一定的概率随机产生的
每一层都是一个有序的链表，默认是升序，也可以根据创建映射时所提供的Comparator进行排序，具体取决于使用的构造方法
最底层(Level 1)的链表包含所有元素
如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现（换句话说上层元素是从下层元素中挑选出来的）
整体结构类似一个金字塔类型，通过每层的索引从上层向下层跳跃查询
每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素

插入操作

查找合适的位置。这里需要明确一点就是在确认新节点要占据的层次K时，采用丢硬币的方式，完全随机。如果占据的层次K大于链表的层次，则重新申请新的层，否则插入指定层次
申请新的节点
调整指针

ConcurrentSkipListMap

内部采用SkipLis数据结构实现。为了实现SkipList，ConcurrentSkipListMap提供了三个内部类来构建这样的链表结构：Node、Index、HeadIndex。

通过CAS来实现同步

数据结构

HeadIndex：用来维护索引层次，通过Index从最上层开始往下层查找，一步一步缩小查询范围。

static final class HeadIndex<K,V> extends Index<K,V> {
    final int level;  //索引层，从1开始，Node单链表层为0
    HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
        super(node, down, right);
        this.level = level;
    }
}

Index：提供了一个基于Node节点的索引Node，一个指向下一个Index的right，一个指向下层的down节点

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

    /** 省略些许代码 */
}

Node：数据节点。包含key、value和一个指向下一个节点的next。

static final class Node<K,V> {
    final K key;
    volatile Object value;
    volatile ConcurrentSkipListMap.Node<K, V> next;

    /** 省略些许代码 */
}

参考资料：

https://juejin.cn/post/6844903958499033095

本文出自：monkeyGeek

座右铭：生于忧患，死于安乐

欢迎志同道合的朋友一起交流、探讨！

monkeyGeek

# 并发容器, 面试

支付宝

微信

ConcurrentSkipListMap原理

SkipList

特性

插入操作

ConcurrentSkipListMap

数据结构

喜欢这篇文章？打赏一下作者吧

评论

分类

标签云

最新文章

归档

标签

最新文章

归档

标签

Your browser is out-of-date!