并发容器之ConcurrentSkipListMap

2024-03-27 14:20

本文主要是介绍并发容器之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,Vextends 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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/852392

相关文章

SpringBoot结合Docker进行容器化处理指南

《SpringBoot结合Docker进行容器化处理指南》在当今快速发展的软件工程领域,SpringBoot和Docker已经成为现代Java开发者的必备工具,本文将深入讲解如何将一个SpringBo... 目录前言一、为什么选择 Spring Bootjavascript + docker1. 快速部署与

Spring IoC 容器的使用详解(最新整理)

《SpringIoC容器的使用详解(最新整理)》文章介绍了Spring框架中的应用分层思想与IoC容器原理,通过分层解耦业务逻辑、数据访问等模块,IoC容器利用@Component注解管理Bean... 目录1. 应用分层2. IoC 的介绍3. IoC 容器的使用3.1. bean 的存储3.2. 方法注

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

python多线程并发测试过程

《python多线程并发测试过程》:本文主要介绍python多线程并发测试过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、并发与并行?二、同步与异步的概念?三、线程与进程的区别?需求1:多线程执行不同任务需求2:多线程执行相同任务总结一、并发与并行?1、

Linux高并发场景下的网络参数调优实战指南

《Linux高并发场景下的网络参数调优实战指南》在高并发网络服务场景中,Linux内核的默认网络参数往往无法满足需求,导致性能瓶颈、连接超时甚至服务崩溃,本文基于真实案例分析,从参数解读、问题诊断到优... 目录一、问题背景:当并发连接遇上性能瓶颈1.1 案例环境1.2 初始参数分析二、深度诊断:连接状态与

SpringIOC容器Bean初始化和销毁回调方式

《SpringIOC容器Bean初始化和销毁回调方式》:本文主要介绍SpringIOC容器Bean初始化和销毁回调方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录前言1.@Bean指定初始化和销毁方法2.实现接口3.使用jsR250总结前言Spring Bea

Java并发编程之如何优雅关闭钩子Shutdown Hook

《Java并发编程之如何优雅关闭钩子ShutdownHook》这篇文章主要为大家详细介绍了Java如何实现优雅关闭钩子ShutdownHook,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 目录关闭钩子简介关闭钩子应用场景数据库连接实战演示使用关闭钩子的注意事项开源框架中的关闭钩子机制1.

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

如何将Tomcat容器替换为Jetty容器

《如何将Tomcat容器替换为Jetty容器》:本文主要介绍如何将Tomcat容器替换为Jetty容器问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat容器替换为Jetty容器修改Maven依赖配置文件调整(可选)重新构建和运行总结Tomcat容器替