ConcurrentSkipListMap 是 Java 中的一个线程安全的有序映射表，它基于跳表（Skip List）数据结构实现。这种数据结构通过维护多个层级的链表来提高搜索效率，每一层都是下一层的一个子集，从而允许快速地跳过一些元素。它提供了高并发的插入、删除和查找操作，同时保持了键的有序性。ConcurrentSkipListMap 适用于需要有序且线程安全的映射表的场景，如实现 LRU 缓存、范围查询等。

肖哥弹架构 跟大家“弹弹” 高并发锁， 关注公号回复 ‘mvcc’ 获得手写数据库事务代码

欢迎 点赞，关注，评论。

关注公号Solomon肖哥弹架构获取更多精彩内容

历史热点文章

• 解锁大语言模型参数：零基础掌握大型语言模型参数奥秘与实践指南
• 高性能连接池之HikariCP框架分析：高性能逐条分解(架构师篇)
• 缓存雪崩/穿透/击穿/失效原理图/14种缓存数据特征+10种数据一致性方案
• Java 8函数式编程全攻略：43种函数式业务代码实战案例解析(收藏版)
• 一个项目代码讲清楚DO/PO/BO/AO/E/DTO/DAO/ POJO/VO
• 17个Mybatis Plugs注解：Mybatis Plugs插件架构设计与注解案例(必须收藏)

1、 ConcurrentSkipListMap

设计思考：

1. 需求场景：
   • 在多线程环境中，需要一个高效的数据结构来维护有序的键值对集合，同时支持快速的插入、删除和查找操作。
   • 适用于需要有序数据且高并发访问的场景，如实时数据索引、多维数据范围查询等。
2. 现有技术局限性：
   • TreeMap 提供了有序的键值对存储，但它不是线程安全的，需要额外的同步措施来保证线程安全，这会影响并发性能。
   • ConcurrentHashMap 提供了高效的并发性能，但它不维护元素的顺序。
3. 技术融合：
   • ConcurrentSkipListMap 结合了跳表的有序性和其他并发控制技术，以提供线程安全的有序映射。
4. 设计理念：
   • ConcurrentSkipListMap 旨在提供一个线程安全的有序映射，它允许多个线程高效地执行插入、删除和查找操作，同时保持元素的排序。
5. 实现方式：
   • ConcurrentSkipListMap 内部使用跳表来存储键值对，跳表是一种通过多级索引来提高查找效率的有序数据结构。
   • 它使用了多种并发控制技术，包括分段锁和 CAS（Compare-And-Swap）操作，以实现高效的并发访问。

2、 数据结构

图说明：

• ConcurrentSkipListMap：这是整个跳表的根结构，表示一个线程安全的有序映射结构。
• HeadIndex：这是跳表的头部索引节点，它不存储数据，而是作为多层索引结构的起点。
• Level 3 Index：这是跳表的第三层索引节点，用于快速定位到第二层索引节点。
• Level 2 Index：这是跳表的第二层索引节点，用于快速定位到第一层索引节点。
• Level 1 Index：这是跳表的第一层索引节点，直接指向数据节点。
• Node A, Node B, Node C：这些是数据节点，每个节点包含一个键（Key）和一个值（Value），并形成链表结构。
• Key A, Key B, Key C：这些是数据节点中的键。
• Value A, Value B, Value C：这些是数据节点中的值。
• Null：表示链表的末尾，没有更多的节点。

3、 执行流程

图说明：

• 创建 ConcurrentHashMap 实例：初始化 ConcurrentHashMap 对象。
• 执行操作：决定要执行的操作类型，可以是插入、查找或删除。
• 插入元素(put) ：执行将键值对插入到 ConcurrentHashMap 的操作。
• 查找元素(get) ：执行根据键查找值的操作。
• 删除元素(remove) ：执行根据键删除键值对的操作。
• 计算键的哈希码：计算操作键的哈希码以确定其在跳表中的位置。
• 确定节点索引：根据哈希码确定节点在跳表中的索引位置。
• 遍历索引节点：从高层索引开始，逐层向下遍历到底层数据节点。
• 找到节点：在数据层找到包含指定键的节点。
• 更新节点值：在找到的节点上执行更新操作，插入或覆盖值。
• 返回节点值：返回找到节点的值。
• 删除节点：从跳表中删除指定的节点。
• 重新平衡索引：删除节点后，可能需要对索引进行重新平衡以维持跳表的性能。

4、优点

1. 有序性：
   • 元素会根据键的自然顺序或构造时提供的 Comparator 进行排序。
2. 线程安全：
   • 提供了线程安全的 Map 操作，无需额外的同步措施。
3. 高效的并发性能：
   • 通过跳表的结构和细粒度的并发控制，实现了高效的并发访问。
4. 范围查询：
   • 支持高效的范围查询操作，如获取所有小于给定键的元素。

5、缺点

1. 内存开销：
   • 相比于无序的并发 Map 实现，ConcurrentSkipListMap 可能需要更多的内存来存储跳表的结构。
2. 实现复杂性：
   • 跳表的实现相对复杂，需要处理多级索引和并发控制。

6、使用场景

• 需要有序数据的场景：
  • 适用于需要按顺序遍历键值对的场景，如有序缓存、实时数据索引等。
• 高并发的有序映射：
  • 在多线程环境中，需要保证数据的一致性和完整性，同时保持高效的并发性能。

7、类设计

8、应用案例

ConcurrentSkipListMap 通常用于需要高效并发访问和保持元素有序的数据集合。这是一个在线购物平台的商品评分系统：

import java.util.concurrent.ConcurrentSkipListMap;

public class ProductRatingSystem {
    // 使用 ConcurrentSkipListMap 存储商品评分，键是商品ID，值是平均评分
    private ConcurrentSkipListMap<Integer, Double> productRatings;

    public ProductRatingSystem() {
        productRatings = new ConcurrentSkipListMap<>();
    }

    // 添加或更新商品评分
    public void addOrUpdateRating(int productId, double rating) {
        // computeIfAbsent 原子地添加新商品或更新现有商品的评分
        productRatings.computeIfAbsent(productId, k -> 0.0) += rating;
        // 重新计算平均评分
        adjustAverageRating(productId, rating);
    }

    // 调整平均评分
    private void adjustAverageRating(int productId, double newRating) {
        double totalRating = productRatings.get(productId);
        int ratingCount = (int) totalRating / newRating;
        productRatings.put(productId, (totalRating + newRating) / (ratingCount + 1));
    }

    // 获取商品评分
    public double getRating(int productId) {
        return productRatings.getOrDefault(productId, 0.0);
    }

    // 主方法，用于演示 ProductRatingSystem 的使用
    public static void main(String[] args) {
        ProductRatingSystem ratingSystem = new ProductRatingSystem();

        // 添加商品评分
        ratingSystem.addOrUpdateRating(1, 5.0);
        ratingSystem.addOrUpdateRating(1, 4.0);
        ratingSystem.addOrUpdateRating(2, 3.0);

        // 获取并打印商品评分
        System.out.println("Product 1 rating: " + ratingSystem.getRating(1));
        System.out.println("Product 2 rating: " + ratingSystem.getRating(2));
    }
}