昆明 网站设计,wordpress类开源网站,小蝌蚪视频网络科技有限公司,怎么加速网页1 JUC包下的并发容器Java 基础集合#xff08;如 ArrayList、LinkedList、HashMap#xff09;非线程安全。为了解决线程安全问题#xff0c;Java 最初提供了同步容器#xff08;如 Vector、Hashtable、SynchronizedList#xff09;#xff0c;但它们通过 synchronized 实…1 JUC包下的并发容器Java 基础集合如 ArrayList、LinkedList、HashMap非线程安全。为了解决线程安全问题Java 最初提供了同步容器如 Vector、Hashtable、SynchronizedList但它们通过 synchronized 实现全局锁多线程竞争时会“串行化”执行并发性能差。为了兼顾线程安全和并发性能JUCjava.util.concurrent包提供了并发容器通过更精细的锁机制或无锁算法大幅提升多线程场景下的吞吐量根据集合的类别List、Set、Map、Queue并发容器可分为以下几类集合类别并发容器代表MapConcurrentHashMap、ConcurrentSkipListMapListCopyOnWriteArrayListSetCopyOnWriteArraySet、ConcurrentSkipListSetQueueBlockingQueue含多种实现、ConcurrentLinkedQueue、BlockingDeque 等以下是几种典型并发容器的设计逻辑CopyOnWriteArrayList对应非并发容器 ArrayList目标替代 Vector、SynchronizedList解决读多写少场景下的并发性能问题原理利用写时复制策略——读操作不加锁写操作时先复制一份新的数组在新数组上修改再将新数组赋值给原引用同时通过 volatile 保证数组的可见性写操作本身加锁保证原子性CopyOnWriteArraySet对应非并发容器 HashSet目标替代 SynchronizedSet实现线程安全的集合元素不重复原理基于 CopyOnWriteArrayList 实现核心是在 add 操作时调用 CopyOnWriteArrayList 的 addIfAbsent 方法——遍历数组若元素已存在则直接返回否则添加到数组尾部以此保证元素不重复ConcurrentHashMap对应非并发容器 HashMap目标替代 Hashtable、SynchronizedMap支持高效的复合操作如先检查后操作原理
JDK6 采用分段锁Segment将哈希表分成多个 Segment每个 Segment 是一个小的哈希表锁只针对单个 Segment大幅降低锁竞争JDK8 采用CAS 无锁算法 synchronized 轻量级锁摒弃分段锁通过 CAS 保证节点操作的原子性结合 synchronized 对链表/红黑树的节点加锁进一步提升并发效率ConcurrentSkipListMap对应非并发容器 TreeMap目标替代 SynchronizedSortedMap即加锁的 TreeMap实现“线程安全的有序 Map”。原理基于 跳表Skip List 实现——跳表是一种可替代平衡树的数据结构通过多层索引加速查找默认按 Key 升序排列并发时通过原子操作保证线程安全并发队列Queue 类。JUC 提供了多种并发队列典型的如 BlockingQueue 系列ArrayBlockingQueue基于数组的有界阻塞队列创建时需指定容量LinkedBlockingQueue基于链表的阻塞队列可指定容量默认无界SynchronousQueue同步队列不存储元素生产者和消费者直接交互PriorityBlockingQueue支持优先级的无界阻塞队列DelayQueue支持“延迟获取”的队列元素需实现延迟接口还有 ConcurrentLinkedQueue非阻塞、基于链表的并发队列、BlockingDeque阻塞双端队列如 LinkedBlockingDeque等满足不同场景的队列操作需求。2 CopyOnWriteArrayList
2.1 概述CopyOnWriteArrayList 是 Java 中线程安全的 List 实现属于 JUC 并发容器。它是可变数组结构支持多线程下的并发读、写操作核心是通过写时复制策略保证线程安全和并发一致性它的核心逻辑是读操作不加锁写操作时复制一份新数组在新数组上完成修改后再将原数组引用指向新数组。同时通过 volatile 关键字保证数组引用的可见性写操作过程中加锁保证原子性工作流程写入未完成时的读取原有数组元素 [1,2,3,4]是当前有效数据读操作直接访问原有数组此时若有写操作如添加元素 5会复制一份新数组在新数组上完成写入新数组变为 [1,2,3,4,5]写入完成后的读取写操作完成后原数组引用被切换为新数组原有数组被丢弃回收后续读操作都访问写入完成的新数组元素[1,2,3,4,5]2.2 应用场景场景 1读多写少的场景特点系统中对集合的读取操作频率远高于写入操作如高频读取的缓存列表如系统配置项列表、字典表数据等解释CopyOnWriteArrayList 读操作不加锁能充分利用 CPU 资源并行处理读请求写操作虽有复制数组的开销但因写入频率低整体性能优势明显同时避免了锁竞争带来的性能损耗场景 2不需要实时更新的数据特点业务对数据的实时一致性要求不高允许读取到“稍旧”的数据如日志系统日志先暂存于 CopyOnWriteArrayList批量写入文件而非实时写入、统计类数据如非实时的访问量统计列表解释CopyOnWriteArrayList 写操作是复制新数组后切换引用读操作可能在写切换完成前访问旧数组因此不保证实时最新数据。但这种最终一致性恰好适配了无需实时更新的业务场景同时还能保证读操作的高并发性能。2.3 使用
2.3.1 基本使用CopyOnWriteArrayList 的创建和操作流程与 ArrayList 高度一致我们可以像使用 ArrayList 一样快速上手首先通过 new CopyOnWriteArrayList() 创建实例然后调用 add、set、get、remove 等方法完成增、改、查、删操作还可以通过 clear、isEmpty、contains、size 等方法进行集合的状态判断和管理// 创建一个 CopyOnWriteArrayList 对象
CopyOnWriteArrayList phaser new CopyOnWriteArrayList();
// 新增
copyOnWriteArrayList.add(1);
// 修改指定下标的元素值
copyOnWriteArrayList.set(0, 2);
// 查询
copyOnWriteArrayList.get(0);
// 删除
copyOnWriteArrayList.remove(0);
// 清空
copyOnWriteArrayList.clear();
// 是否为空
copyOnWriteArrayList.isEmpty();
// 是否包含
copyOnWriteArrayList.contains(1);
// 获取元素个数
copyOnWriteArrayList.size();方法功能描述add(元素)向集合中新增一个元素set(下标, 新元素)修改指定下标的元素值get(下标)获取指定下标的元素值remove(下标)删除指定下标的元素clear()清空集合中所有元素isEmpty()判断集合是否为空返回 booleancontains(元素)判断集合是否包含某个元素返回 booleansize()获取集合中元素的个数2.3.2 IP 黑名单判定IP 黑名单的业务特点是读多写少大量请求需要读黑名单来判断是否需要拦截但黑名单更新写操作频率低且对黑名单更新的实时性要求不高新 IP 加入黑名单后后续请求拦截即可无需要求所有请求立即感知。这完全契合 CopyOnWriteArrayList “读多写少、最终一致性”的适用场景代码示例
public class CopyOnWriteArrayListDemo {private static CopyOnWriteArrayListString copyOnWriteArrayList new CopyOnWriteArrayList();// 模拟初始化的黑名单数据static {// 向 CopyOnWriteArrayList 中添加初始的黑名单 IPcopyOnWriteArrayList.add(ipAddr0);copyOnWriteArrayList.add(ipAddr1);copyOnWriteArrayList.add(ipAddr2);}public static void main(String[] args) throws InterruptedException {// 启动多个线程模拟外部请求Runnable task new Runnable() {public void run() {// 模拟接入用时try {Thread.sleep(new Random().nextInt(5000));} catch (Exception e) {}// 每个线程随机生成一个 IPString currentIP ipAddr new Random().nextInt(6);// 判断是否命中黑名单if (copyOnWriteArrayList.contains(currentIP)) {// 若命中打印 “拒绝接入”System.out.println(Thread.currentThread().getName() IP currentIP 命中黑名单拒绝接入处理);return;}// 若未命中打印 “接入处理”System.out.println(Thread.currentThread().getName() IP currentIP 接入处理...);}};new Thread(task, 请求1).start();new Thread(task, 请求2).start();new Thread(task, 请求3).start();// 启动 “IP 黑名单更新” 线程休眠一段时间后向 CopyOnWriteArrayList 中添加新的黑名单 IPnew Thread(new Runnable() {public void run() {// 模拟用时try {Thread.sleep(new Random().nextInt(2000));} catch (Exception e) {}String newBlackIP ipAddr3;// 写操作时会复制新数组完成添加后切换引用// 写操作过程中加锁保证原子性但不阻塞读操作读操作仍可访问旧数组保证了读并发不被写阻塞copyOnWriteArrayList.add(newBlackIP);System.out.println(Thread.currentThread().getName() 添加了新的非法IP newBlackIP);}}, IP黑名单更新).start();Thread.sleep(1000000);}
}2.4 原理CopyOnWriteArrayList 针对读多写少的并发场景设计核心逻辑是读操作无锁并发执行写操作时复制一份新数组在新数组上完成修改后再将原数组引用指向新数组执行流程读操作则全程无锁直接访问当前数组写操作切换引用前读的是旧数组切换后读的是新数组写操作的执行分为四步同时结合 volatile 和锁保证线程安全
加锁写操作前加锁保证同一时间只有一个线程执行写操作复制新数组从原数组如 [1,2,3,4]复制出一份新数组新数组上执行写操作在新数组上完成修改如添加元素 5新数组变为 [1,2,3,4,5]解锁 切换引用解锁后将原数组的引用volatile 修饰指向新数组volatile 保证其他读线程能立即感知到数组引用的变化整个过程的线程安全保障由锁 数组拷贝 volatile来保障锁写操作加锁保证写操作的原子性同一时间只有一个线程能写数组拷贝写操作在新拷贝的数组上执行避免了多线程对原数组的直接修改冲突volatile底层数组 array 被 volatile 修饰private transient volatile Object[] array;保证数组引用的可见性——写操作切换数组引用后所有读线程能立即看到新数组优点读性能极高读操作无锁多线程可并发执行尤其适合读多写少的场景遍历安全因读写分离读旧数组、写新数组遍历过程中不会抛出ConcurrentModificationException与ArrayList遍历修改抛异常的行为不同缺点内存开销大每次写操作都要复制数组若数组元素多会消耗大量内存甚至引发频繁 GC实时性不足读操作可能访问旧数组无法保证读取到最新数据仅满足最终一致性。2.5 扩展知识迭代器的fail-fast与fail-safe机制在 Java 中迭代器Iterator在迭代的过程中如果底层的集合被修改添加或删除元素不同的迭代器对此的表现行为是不一样的可分为两类Fail-Fast快速失败和 Fail-Safe安全失败fail-fast快速失败机制当多个线程或单线程在遍历中修改集合结构时迭代器会立即抛出 ConcurrentModificationException 异常以此快速失败来提示并发修改问题;典型案例ArrayList、HashMap 等 java.util 包下的集合其迭代器默认采用该机制。例如线程 A 遍历迭代 ArrayList 时若其他线程或自身后续代码修改了集合的元素数量就会抛出 ConcurrentModificationException解决方案方案一加锁即在遍历过程中所有涉及到改变modCount的地方全部加上synchronized或者直接使用Collection#synchronizedList但会阻塞遍历性能差不推荐modCount 记录集合结构被修改的次数如添加、删除元素等操作会触发 modCount 递增。当迭代器遍历集合时会比对自身记录的 expectedModCount 和集合的 modCount
若两者一致说明遍历过程中集合结构未被修改若不一致说明有其他线程或当前线程后续代码修改了集合结构此时迭代器会立即抛出 ConcurrentModificationException即 fail-fast异常方案二用 CopyOnWriteArrayList 替换 ArrayList即采用fail-safe机制推荐fail-safe安全失败机制集合结构修改时会在复制的新集合上进行因此迭代器遍历原集合时不会抛出 ConcurrentModificationException典型案例CopyOnWriteArrayList、ConcurrentHashMap 等 java.util.concurrent 包下的并发集合缺点
数据实时性不足遍历中若集合被修改可能读取到旧数据仅保证最终一致性内存开销大修改时复制集合会创建额外对象可能引发频繁 GC两者核心区别维度fail-fast快速失败fail-safe安全失败异常抛出遍历中修改集合会抛 ConcurrentModificationException不会抛该异常集合实现基于 java.util 包如 ArrayList基于 java.util.concurrent 包如 CopyOnWriteArrayList数据一致性保证实时一致性但并发修改会抛异常仅保证最终一致性可能读取旧数据内存开销低无额外复制高修改时复制集合
3 ConcurrentHashMap
3.1 概述ConcurrentHashMap 是 Java 中线程安全的哈希表实现支持高并发下的读写操作是 HashMap非线程安全和 Hashtable全局锁、并发性能差的替代方案专为多线程场景优化ConcurrentHashMap 的实现机制在 JDK1.8 前后有显著变化
JDK1.8 之前采用分段锁Segment 机制。将哈希表分割为多个Segment 段每个 Segment 是一个小的哈希表锁仅作用于单个 Segment。这样大幅降低了锁竞争提升了并发度JDK1.8 及之后摒弃分段锁采用自旋 CAS synchronized 关键字 实现同步。具体来说对哈希表的链表/红黑树节点加 synchronized 锁结合 CAS 操作保证节点修改的原子性进一步提升并发效率JDK1.8 为何弃用分段锁官方给出了三点核心原因
节省内存空间分段锁需要为每个 Segment 维护额外的锁结构JDK1.8 的新实现减少了这部分内存开销避免锁竞争导致的性能瓶颈分段锁的并发度由 Segment 数量决定若实际并发度达不到设置的粒度会导致锁定一段后整个段无法更新反而引发长时间等待。新实现的节点级锁更精细竞争概率更低提升 GC 效率分段锁的结构复杂GC 回收时开销更大新实现的结构更简洁有助于 GC 高效回收内存。3.2 应用场景场景 1共享数据的线程安全。在多线程编程中若多个线程需要对同一份哈希表数据进行并发读写操作ConcurrentHashMap 可保证线程安全。它避免了 HashMap 非线程安全导致的脏数据问题也解决了 Hashtable 全局锁带来的并发性能瓶颈让多线程共享数据时既能保证一致性又能维持高并发效率场景 2缓存实现。由于 ConcurrentHashMap 兼具高并发性能和线程安全非常适合作为缓存的数据结构。在多线程环境下大量请求可以并发读写缓存比如查询用户信息缓存、配置项缓存等既能保证缓存数据的一致性又能通过高并发特性提升程序整体的响应速度。3.3 使用
3.3.1 基本用法ConcurrentHashMap 的基础 API 设计和 HashMap 非常相似
// 创建一个 ConcurrentHashMap 对象
ConcurrentHashMapObject, Object concurrentHashMap new ConcurrentHashMap();
// 添加键值对
concurrentHashMap.put(key, value);
// 批量添加键值对
concurrentHashMap.putAll(new HashMap());
// 根据键取值
concurrentHashMap.get(key);
// 判定是否为空
concurrentHashMap.isEmpty();
// 获取键值对数量
concurrentHashMap.size();
// 获取所有键的集合
concurrentHashMap.keys();
// 获取所有值的集合
concurrentHashMap.values();
// 清空所有键值对
concurrentHashMap.clear();ConcurrentHashMap 还提供了一些针对并发场景优化的扩展方法满足线程安全的复合操作需求方法功能描述putIfAbsent(K key, V value)仅当 key 对应的 value 不存在时才放入键值对若已存在返回原有 value不做修改remove(Object key, Object value)仅当 key 对应的值是 value 时才移除该键值对保证“删除操作”的条件原子性replace(K key, V oldValue, V newValue)仅当 key 当前值是 oldValue 时才替换为 newValue保证“替换操作”的条件原子性computeIfAbsent(key, Function)若 key 不存在用 Function 计算的值作为 value 放入若存在直接返回原有 valuemerge(key, value, BiFunction)若 key 不存在直接放入 value若存在用 BiFunction 处理原有 value 和新 value将结果作为新 value
3.3.2 *统计文件中英文字母出现的总次数需求生成测试数据26个英文字母每个循环200次共5200个单词乱序后存入26个文件每个文件200个单词统计需求启动26个线程分别读取26个文件统计每个字母的出现次数最终每个字母应恰好出现200次生成测试文件
/*** 生成测试文件* throws IOException*/
public void produceData() throws IOException {// 定义26个字母的字符串String dataabcdefghijklmnopqrstuvwxyz;ListString listnew ArrayList();// 循环遍历26个字母每个字母循环200次最后将5200个字母放入集合for (int i 0; i data.length(); i) {for (int j 0; j 200; j) {list.add(String.valueOf(data.charAt(i)));}}// 打乱集合顺序保证数据随机Collections.shuffle(list);// 遍历 26 次每次取 200 个元素以换行符 \n 拼接后写入一个文件共 26 个文件如 1.txt、2.txt…26.txtfor (int i 0; i 26; i) {try(FileWriter fwnew FileWriter((i1).txt)){fw.write(list.subList(i*200,(i1)*200).stream().collect(Collectors.joining(\n)));}}
}读取文件
/*** 定义读文件的方法*/
private static void read(List list, int i) {try (// 创建输入缓冲字符流BufferedReader bf new BufferedReader(new FileReader((i 1) .txt))) {String data;// 按行读取单个文件的内容判断是否为空不为空则存入线程本地的 Listwhile ((data bf.readLine()) ! null) {list.add(data);}} catch (FileNotFoundException e) {e.printStackTrace();} catch (IOException e) {e.printStackTrace();}
}生成线程操作每个文件对应的list存放到线程共享的map
/*** 定义26个线程读26个文件并将结果放入map。map由函数式接口作为参数提供放入map由Consumer函数式接口处理* param supplier 提供者提供map集合存放单词计数* param consumer 消费者对list第二个参数进行计数并存入map第一个参数中*/
private static T void deal(SupplierMapString, T supplier, BiConsumerMapString, T, ListString consumer) {//获得map集合用于存放单词计数MapString, T map supplier.get();// 利用闭锁保证26个线程都执行完任务即等待所有线程执行完毕后输出结果CountDownLatch count new CountDownLatch(26);// 循环创建26个线程每个线程读取一个文件的内容再对内容进行计数for (int i 0; i 26; i) {int j i;new Thread(() - {ListString list new ArrayList();//读取文件read(list, j);consumer.accept(map, list);count.countDown();}).start();}try {count.await();} catch (InterruptedException e) {e.printStackTrace();}System.out.println(map);
}Consumer 是 Java 8 引入的函数式接口位于 java.util.function 包代表“消费一个输入参数但不返回结果”的操作
consumer.accept(map, list); 表示
调用 BiConsumer 实例 consumer 中定义的 accept 方法传入两个参数mapConcurrentHashMap集合和 list文件读取的内容列表执行 consumer 中预先定义的操作将 list 中的数据统计到 map 中
通过这种方式实现了“数据读取”与“统计逻辑”的解耦让代码更灵活、可复用。
简言之consumer.accept(map, list); 是通过函数式接口将 list 中的数据按预设逻辑“消费”到 map 中的操作是 Java 中“行为参数化”的典型应用我们要做的是给deal()方法传入两个参数
一是提供一个map集合用来存放每个单词的计数结果key为单词value为计数二是提供一组操作保证计数的安全性会传递map集合以及单词的List正确输出结果应该如下
{a200, b200, c200, d200, e200, f200, g200, h200, i200, j200, k200, l200, m200, n200, o200, p200, q200, r200, s200, t200, u200, v200, w200, x200, y200, z200}测试代码
// 错误实现用HashMapHashMap非线程安全多线程并发put会导致计数错误
deal(() - new HashMapString, Integer(), (map, words) - {for (String word : words) {Integer counter map.get(word);int newValue counter null ? 1 : counter 1;map.put(word, newValue);}
});// 正确实现 1ConcurrentHashMap LongAdder
// 用 computeIfAbsent 保证“若 key 不存在则创建 LongAdder 实例”的原子性
// 调用 LongAdder.increment() 进行线程安全的计数LongAdder 是专门为高并发计数优化的类
deal(() - new ConcurrentHashMapString, LongAdder(), (map, list) - {// 遍历集合内容list.forEach(str - {map.computeIfAbsent(str, (key) - new LongAdder()).increment();});});// 正确实现 2ConcurrentHashMap merge 方法
// merge 方法接收“键、初始值、合并函数”若键不存在则存入初始值若存在则用合并函数处理旧值和新值
// 这里 merge(str, 1, Integer::sum) 表示若 str 不存在则存 1若存在则将旧值 1保证了计数的原子性
deal(() - new ConcurrentHashMapString, Integer(), (map, list) - {// 遍历集合内容list.forEach(str - {map.merge(str, 1, Integer::sum);});});3.4 数据结构
3.4.1 HashTable的数据结构HashTable 底层采用数组 链表的组合结构数组作为哈希表的“桶”每个桶对应一个数组下标如上图中的 0、1、2…64链表当多个键的哈希值映射到同一数组下标时会以链表的形式存储在该桶下如下标 1 的桶中链表长度达到 8 个节点为了保证线程安全HashTable 对所有公共方法如 put、get、remove、clear 等都添加了 synchronized 关键字实现全局锁任何线程执行这些方法时都会锁定整个 HashTable 实例同一时间只有一个线程能操作 HashTable从而避免了多线程下的竞态问题HashTable 的全局锁设计导致了并发性能瓶颈即使多个线程操作 HashTable 中不同的“桶”数组下标也会因为全局锁的存在而串行执行这使得 HashTable 在高并发场景下的吞吐量极低无法充分利用多线程的性能优势。这也是后来 ConcurrentHashMap 被设计出来的核心原因——ConcurrentHashMap 通过分段锁JDK1.8 前或节点级锁 CASJDK1.8 后实现更细粒度的锁大幅提升了并发性能。3.4.2 JDK1.7 中的ConcurrentHashMapJDK 1.7 的ConcurrentHashMap采用分段式的三层结构Segments 数组是最外层的分段锁载体每个 Segment 本质上是一个独立的小哈希表且继承自 ReentrantLock可重入锁。默认 Segment 数量为 16也可通过构造函数修改HashEntry 数组 链表每个 Segment 内部维护一个数组 链表的结构与 HashMap 类似用于存储具体的键值对与 HashTable 的全局锁不同ConcurrentHashMap 通过分段锁实现更细粒度的并发控制当线程执行 put、get 等操作时会先通过哈希计算定位到具体的 Segment然后只对该 Segment 加锁ReentrantLock其他 Segment 仍可被其他线程并发访问这种分段锁设计的核心优势是提升并发度不同 Segment 之间的操作完全隔离比如线程 A 操作 Segment 0线程 B 操作 Segment 1两者互不干扰可并行执行相比 HashTable 的全局锁分段锁大幅减少了锁竞争从而在高并发场景下显著提升吞吐量。3.4.3 JDK1.8 中的ConcurrentHashMapJDK 1.8 的 ConcurrentHashMap 摒弃了 JDK 1.7 的Segments 分段设计采用与 HashMap 类似的三层结构数组作为哈希表的“桶”每个桶对应一个数组下标链表当多个键的哈希值映射到同一数组下标时初始以链表形式存储红黑树当链表的节点数量≥树化阈值 8且数组长度≥最小树化容量 64时链表会转化为红黑树以提升查询效率红黑树的查询时间复杂度为 O(log n)远优于链表的 O(n)为保证线程安全JDK 1.8 采用无锁 轻量级锁的组合CASCompare-And-Swap用于数组节点的初始化、元素插入等操作通过原子性的“比较-交换”保证操作的原子性避免了锁的开销synchronized 关键字对链表或红黑树的节点加锁而非全局锁或分段锁只有操作同一节点的线程会竞争锁进一步减小了锁粒度提升并发度相比 JDK 1.7JDK 1.8 的设计在性能上有两大升级
结构更高效红黑树的引入解决了链表过长时的查询性能瓶颈同时去掉 Segments 数组减少了内存开销锁粒度更细由分段锁进化为节点级 synchronized 锁结合 CAS 无锁操作在高并发场景下的吞吐量更高资源利用率更优。4 ConcurrentSkipListMap
4.1 概述ConcurrentSkipListMap 是 Java 中线程安全的有序映射Map底层基于跳表Skip List 实现。跳表是一种可替代平衡树如红黑树的数据结构能在保证有序性的同时支持高效的并发读写它是 TreeMap 的并发版本。TreeMap 是基于红黑树的有序 Map但非线程安全ConcurrentSkipListMap 则在保证有序性的基础上实现了线程安全支持高并发读写操作适用于需要高并发性能、有序性、区间查询的场景高并发性能跳表的并发控制机制使其在多线程下的读写效率优于加锁的 TreeMap有序性能像 TreeMap 一样按 Key 排序区间查询支持类似“获取 Key 介于 A 和 B 之间的所有元素”的区间操作且并发下仍能高效执行。4.2 跳表
4.2.1 简介跳表是一种基于有序链表的高级数据结构支持快速的插入、删除、查找操作时间复杂度为O(log n)远高于普通链表的 O(n)是平衡树如红黑树的高效替代方案之一跳表的结构是通过多层索引链表实现的普通有序链表元素按顺序 1→2→3→…→12 串联查找元素时需逐个遍历时间复杂度 O(n)初步的跳表雏形在普通链表上增加一层稀疏索引链表如 1→3→5→9→12。查找时先通过索引层快速跳过无效元素再在底层链表精确查找减少了遍历次数完整的跳表结构包含多层索引Level3、Level2、Level1。最底层Level1包含所有元素上层索引层逐渐稀疏每个元素可能出现在多个层级的链表中层级越高元素越稀疏跳表的设计遵循以下规则
多层结构由多个层级的有序链表组成有序性每一层的链表都是有序的默认升序也可自定义排序底层全量最底层Level1包含所有元素层级包含性若一个元素出现在 LevelNN1的链表中它必定也出现在下一层LevelN-1的链表中节点双指针每个节点包含两个指针——一个指向同层下一个元素一个指向下层的相同元素跳表通过多层索引实现了类似二分查找的效果使得插入、删除、查找的时间复杂度降至 O(log n)查找时从最上层索引开始“跳跃式”缩小范围最终在底层链表找到目标元素插入/删除时只需调整对应层级的链表指针无需像平衡树那样进行复杂的旋转操作实现更简单且并发友好。4.2.2 跳表的查找步骤1从最上层Level3开始比较初始位置在 Level3 的头节点 1要查找元素 11比较 11 和 Level3 下一个节点 511 5继续向右移动比较 11 和 Level3 后续节点 1211 12因此向下层Level2寻找步骤2在 Level2 中继续查找来到 Level2 的 5 节点比较 11 和下一个节点 911 9继续向右移动比较 11 和 Level2 后续节点 1211 12因此向下层Level1寻找步骤3在 Level1底层全量链表中精确查找
来到 Level1 的 9 节点向右依次比较1011 10→ 11找到目标元素。4.2.3 跳表的插入跳表插入数据分为三步
确定插入层级 K通过随机方式确定元素要插入的层级。若 K 大于跳表现有总层级则开辟新的层级否则在对应层级插入申请新节点为要插入的元素如案例中的 13创建节点调整指针在对应层级的链表中调整前后节点的指针将新节点接入跳表跳表的层级是随机生成的这一设计保证了跳表的“平衡性”避免出现某一层级过密或过疏的情况案例1插入元素13原有的层级是3级假设K4即插入到第 4 级原有跳表层级为 3 级Level1~Level3因 K4需开辟新的 Level4新元素 13 会在 Level4、Level3、Level2、Level1 这 4 个层级中插入保持各层级的有序性K2小于原有3级即插入到第 2 级原有跳表层级为 3 级因 K2仅在 Level2、Level1 这 2 个层级中插入 13Level3 保持不变插入新节点时需要调整对应层级中前驱节点和后继节点的指针前驱节点如12的【同层下一个元素指针】指向新节点指向13新节点如13的【同层下一个元素指针】指向后继节点此处指向null同时新节点如13的【下层相同元素指针】指向下一层的自身节点若存在多层插入。4.3 使用ConcurrentSkipListMap 的创建和操作流程与普通 Map 高度一致可以快速上手首先通过 new ConcurrentSkipListMap() 创建实例然后调用 put、get、remove 等方法完成增、查、删操作还可以通过 keySet() 遍历所有键进而获取对应的值方法功能描述put(键, 值)向 ConcurrentSkipListMap 中添加键值对且会自动按键的自然顺序或自定义比较器排序get(键)根据键获取对应的值若键不存在则返回 nullkeySet()获取所有键的集合集合中的键是有序的默认升序remove(键)根据键删除对应的键值对返回被删除的值若键不存在则返回 null
例
public class ConcurrentSkipListMapDemo {public static void main(String[] args) {ConcurrentSkipListMapInteger, String map new ConcurrentSkipListMap();// 添加元素map.put(1, a);map.put(3, c);map.put(2, b);map.put(4, d);// 获取元素String value1 map.get(2);System.out.println(value1); // 输出b// 遍历元素for (Integer key : map.keySet()) {String value map.get(key);System.out.println(key : value);}// 删除元素String value2 map.remove(3);System.out.println(value2); // 输出c}
}5 电商场景中并发容器的选择案例一电商活动商品售卖数量统计分析需频繁对商品 IDkey进行“get 读取次数 set 写入新次数”的操作商品 ID 数量稳定不频繁新增初级方案
用 HashMap 会因非线程安全导致数据丢失或不准确JDK1.7 前甚至会出现扩容死循环导致 CPU 飙升用 Hashtable 会因全局锁导致并发性能极差锁粒度太粗选型ConcurrentHashMap。它通过细粒度锁JDK1.8 后为节点级 synchronized CAS保证线程安全同时维持高并发性能完美适配“频繁读写、key 数量稳定”的场景案例二用户浏览商品历史与次数统计分析用户数量极多key 数量大且需频繁读写更新浏览次数初级方案ConcurrentHashMap 在数据量大时会将链表转为红黑树但红黑树的平衡操作在高并发下会涉及大量节点锁竞争成本高性能下降选型ConcurrentSkipListMap。它基于跳表实现增删改查的时间复杂度为 O(log n)且跳表的分层索引设计在高并发下的锁竞争远低于红黑树更适合“数据量极大、频繁增删改”的场景案例三活动冻结用户列表冻结后不允许再下单采购但是可以浏览低频写、高频读分析冻结用户数量少写操作低频但非冻结用户每次抢购都要读取列表判断读操作高频初级方案
ArrayList 线程不安全高并发下会出现数据错乱。Vector 虽线程安全但因全局锁导致读操作也被阻塞并发性能差。选型CopyOnWriteArrayList。它的写时复制机制让读操作无锁、并发性能极高写操作虽有内存开销但因写频率低整体成本可接受完美适配“低频写、高频读”的场景总结并发容器选型策略业务需求推荐容器核心原因高并发下的哈希表key 数量稳定、频繁读写ConcurrentHashMap细粒度锁保证线程安全高并发性能优高并发下的有序映射数据量大、频繁增删改ConcurrentSkipListMap跳表结构在高并发下的锁竞争更低增删改查效率稳定低频写、高频读的列表场景CopyOnWriteArrayList读操作无锁并发写操作复制数组保证安全适配“读多写少”场景强一致性要求极少场景Hashtable全局锁保证强一致性但并发性能差仅在极端场景下使用
