当前位置：首页 > ds >正文

Java集合详解：ConcurrentSkipListMap

ds 2025/5/16 10:27:22

1. ConcurrentSkipListMap简介

并发跳跃映射表 java.util.concurrent.ConcurrentSkipListMap，是一种可扩展高并发的有序映射表实现。ConcurrentSkipListMap 根据键大小进行排序，键可以通过 ConcurrentSkipListMap 的成员 Comparator 比较大小，如果 ConcurrentSkipListMap 没有注册比较器 Comparator，那么就需要键是可比较的（可比较的意思是键的类实现了 java.lang.Comparable 接口）。
ConcurrentSkipListMap 实现了并发的 SkipList（跳表），不但提供了平均时间复杂度为 log(n) 的映射表基本操作，并且保证了在多线程环境下，插入、移除、更新，读取等并发操作的安全执行。
ConcurrentSkipListMap 的并发遍历读操作只支持弱一致性，这是因为在遍历过程中，ConcurrentSkipListMap 的迭代器每次都只会返回键值对的不可变快照给读线程。顺序遍历的速度比逆序遍历的速度要快
ConcurrentSkipListMap 的 size() 方法与其他的集合类不同，因为 ConcurrentSkipListMap 的异步性质，size() 方法需要遍历所有元素才能统计出结点个数，在并发环境下，可能会出现 size() 方法执行期间，跳表被其他线程修改的情况，因此 size() 方法返回的结果并不精确。
ConcurrentSkipListMap 的批量操作比如 putAll、equals、toArray、containsValue、clear 等方法，都不保证执行是原子的。比如读线程在使用迭代器对 ConcurrentSkipListMap 进行遍历的同时，写线程通过 putAll 方法向跳表中插入了一系列元素，那么读线程可能只会看到部分新增加的元素。
ConcurrentSkipListMap 和其他并发类集合一样，不允许使用空键和空值（就是用 null作为键或者值），这是因为，在并发环境下，没有办法准确的区分 null 值与元素缺失。

2. ConcurrentSkipListMap 中的跳表

ConcurrentSkipListMap 实现了一个 tree-like two-dimensionally linked skip list 就是树状二维链式跳表，索引等级和数据由不同类型的结点来表示。跳表全称为跳跃链表，本质是一个多层链表，它允许以平均时间复杂度 O(logn) 对一个有序链表执行查询，插入和删除操作。快速查询是通过维护一个多层次的链表，最底层是元素链表，元素链表上层是索引链表，索引链表中的每两个结点，都对应着其下层链表一个区间的边界（图1是一个具有2级索引的跳表）。一开始时，算法在最上层进行搜索，找到需要查找的元素所在的区间，这时，算法将通过索引结点跳到下一层，重复刚才的搜索，直到找到需要查找的元素为止。图1是一个具有2级索引的跳跃表。

图1：具有2级索引的跳跃表的基本结构

图1：具有2级索引的跳跃表的基本结构
ConcurrentSkipListMap 采用一种基于HM有序集合链表的算法来作为基本的链表实现，并且对这种算法进行了改进，因此 ConcurrentSkipListMap 采用的无锁链表算法比HM有序集合链表更加高效并且节省存储空间。

HM有序集合链表

HM有序集合链表是一种无锁的非阻塞式链表，其基本思想就是为了消除无锁链表删除结点时对其他线程并发访问链表的影响，从而引入了标记域，在删除结点时，先修改标记域为删除标记，然后再修改后继引用域，而标记域和引用域需要原子的进行修改，因此使用 java.util.concurrent.atomic.AtomicMarkableReference 将标记域和后继引用域封装在一起，实现对这两个变量的原子修改。所以HM有序集合链表算法的主要问题有两个：