Java并发编程--JUC并发容器

摘要

  • 本文介绍并发容器相关技术

  • 本文基于jdk1.8

并发容器

  • Java的集合容器框架中,主要有四大类别:ListSetQueueMap,大家熟知的这些集合类ArrayListLinkedListHashMap等这些容器都是非线程安全的。

  • 为了保证线程安全,所以java提供了同步容器,可以简单地理解为通过synchronized来实现同步的容器,比如VectorHashtable以及SynchronizedList等容器,这样做的代价是削弱了并发性,当多个线程共同竞争容器级的锁时,吞吐量就会降低。

  • 因此为了解决同步容器的性能问题,所以才有了并发容器java.util.concurrent包中提供了多种并发类容器:

并发容器 对应的非并发容器 代替的同步容器 实现原理 应用场景
CopyOnWriteArrayList ArrayList Vector、synchronizedList CopyOnWriteArrayList 内部使用了一种称为“写时复制”的机制。当需要进行写操作时,它会创建一个新的数组,并将原始数组的内容复制到新数组中,然后进行写操作。一旦修改完成,新的副本会替代原始数组,成为新的数据源。
因此,读操作不会被写操作阻塞,读操作返回的结果可能不是最新的,但是对于许多应用场景来说,这是可以接受的。此外,由于读操作不需要加锁,因此它可以支持更高的并发度。
需要注意的是,虽然副本会替代原始数组,但是这个替代并不是立即发生的。在修改操作期间,读操作仍然可能会访问原始数组。只有当修改完成后,才会将新的副本设置为源数组。
1. 读多写少的场景由于 CopyOnWriteArrayList 的读操作不需要加锁,因此它非常适合在读多写少的场景中使用。例如,一个读取频率比写入频率高得多的缓存,使用 CopyOnWriteArrayList 可以提高读取性能,并减少锁竞争的开销。
2. 不需要实时更新的数据由于 CopyOnWriteArrayList 读取的数据可能不是最新的,因此它适合于不需要实时更新的数据。例如,在日志应用中,为了保证应用的性能,日志记录的操作可能被缓冲,并不是实时写入文件系统,而是在某个时刻批量写入。这种情况下,使用 CopyOnWriteArrayList 可以避免多个线程之间的竞争,提高应用的性能。
注意:由于写操作的时候,需要拷贝数组,会消耗内存,如果原数组的内容比较多的情况下,可能导致 young gc 或者full gc,谨慎使用
CopyOnWriteArraySet HashSet synchronizedSet 基于CopyOnWriteArrayList实现,其唯一的不同是在add时调用的是CopyOnWriteArrayList的addIfAbsent方法,其遍历当前Object数组,如Object数组中已有了当前元素,则直接返回,如果没有则放入Object数组的尾部,并返回。 同CopyOnWriteArrayList
ConcurrentHashMap HashMap Hashtable、synchronizedMap 在JDK1.8之前,ConcurrentHashMap使用分段锁以在保证线程安全的同时获得更大的效率。
JDK1.8开始舍弃了分段锁,使用自旋+CAS+synchronized关键字来实现同步。
这样做的好处:
1.节省内存空间 ,分段锁需要更多的内存空间,而大多数情况下,并发粒度达不到设置的粒度,竞争概率较小,反而导致更新的长时间等待(因为锁定一段后整个段就无法更新了)
2.提高GC效率。
1.共享数据的线程安全:在多线程编程中,如果需要进行共享数据的读写,可以使用 ConcurrentHashMap 保证线程安全。
2. 缓存:ConcurrentHashMap 的高并发性能和线程安全能力,使其成为一种很好的缓存实现方案。在多线程环境下,使用 ConcurrentHashMap 作为缓存的数据结构,能够提高程序的并发性能,同时保证数据的一致性。
ConcurrentSkipListMap TreeMap synchronizedSortedMap(TreeMap) 基于Skip list(跳表)实现的有序映射(Map)数据结构,是一种可以代替平衡树的数据结构,默认是按照Key值升序的。 ConcurrentSkipListMap适用于需要高并发性能、支持有序性和区间查询的场景,能够有效地提高系统的性能和可扩展性。
ConcurrentLinkedQueue LinkedList LinkedBlockingQueue ConcurrentLinkedQueue 基于无锁算法和乐观并发策略,旨在提供高效的并发操作。它使用一个单向链表数据结构来存储元素,并且保持了先进先出(FIFO)的顺序。
ConcurrentLinkedQueue 是一个无界队列,它没有固定的容量限制。可以根据需要动态地增长或缩小链表的长度。
需要注意的是,ConcurrentLinkedQueue 并不适合在迭代过程中进行修改操作,因为它的结构在并发情况下可能会发生变化。
1.高并发环境:ConcurrentLinkedQueue 适用于需要高并发性能和线程安全的场景。由于它采用无锁算法和乐观并发策略,可以在高并发环境下提供较高的吞吐量。
2.生产者-消费者模式:ConcurrentLinkedQueue 在实现生产者-消费者模式时非常有用。生产者线程可以将元素添加到队列的尾部,而消费者线程可以从队列的头部获取元素,实现了解耦和并发处理。
3.任务调度:ConcurrentLinkedQueue 可以作为任务调度的数据结构,用于存储待执行的任务。多个线程可以从队列中获取任务并执行,从而实现任务的并发处理。
ConcurrentLinkedDeque LinkedList 与ConcurrentLinkedQueue 相比 ConcurrentLinkedDeque 是基于双向链表实现的并发双端队列。它支持在队头和队尾进行插入和移除操作,保持了元素的先进先出顺序。 ConcurrentLinkedDeque 适用于需要双端操作的并发场景,例如生产者-消费者模式中的多线程同时插入和移除元素的场景。

CopyOnWriteArrayList

方法 描述
int size() 返回列表中的元素数量。
boolean isEmpty() 检查列表是否为空。
boolean contains(Object o) 检查列表是否包含指定元素。
Iterator<E> iterator() 返回一个迭代器,用于遍历列表中的元素。
boolean add(E e) 将元素添加到列表末尾。
boolean remove(Object o) 从列表中移除指定元素的第一个匹配项。
boolean containsAll(Collection<?> c) 检查列表是否包含指定集合中的所有元素。
boolean addAll(Collection<? extends E> c) 将指定集合中的所有元素添加到列表末尾。
boolean addAll(int index, Collection<? extends E> c) 将指定集合中的所有元素插入到列表的指定位置。
boolean removeAll(Collection<?> c) 移除列表中与指定集合中的元素相匹配的所有元素。
boolean retainAll(Collection<?> c) 仅保留列表中与指定集合中的元素相匹配的元素,移除其他元素。
void clear() 清空列表中的所有元素。
E get(int index) 返回列表中指定位置的元素。
E set(int index, E element) 用指定元素替换列表中指定位置的元素,并返回原来的元素。
void add(int index, E element) 在列表的指定位置插入指定元素。
E remove(int index) 移除列表中指定位置的元素,并返回被移除的元素。
int indexOf(Object o) 返回指定元素在列表中首次出现的位置索引,如果不存在,则返回 -1。
int lastIndexOf(Object o) 返回指定元素在列表中最后一次出现的位置索引,如果不存在,则返回 -1。

小贴士

迭代器的 fail-fast 与 fail-safe 机制

  • 在 Java 中,迭代器(Iterator)在迭代的过程中,如果底层的集合被修改(添加或删除元素),不同的迭代器对此的表现行为是不一样的,可分为两类:Fail-Fast(快速失败)和 Fail-Safe(安全失败)。

fail-fast 机制

  • fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时,就可能会产生 fail-fast 事件。例如:当某一个线程A通过 iterator 去遍历某集合的过程中,若该集合的内容被其他线程所改变了;那么线程A访问集合时,就会抛出ConcurrentModificationException异常,产生 fail-fast 事件。
  • 在 java.util 包中的集合,如 ArrayList、HashMap 等,它们的迭代器默认都是采用 Fail-Fast 机制。
  • fail-fast解决方案
    • 方案一:在遍历过程中所有涉及到改变modCount 值的地方全部加上synchronized 或者直接使用Collection#synchronizedList,这样就可以解决问题,但是不推荐,因为增删造成的同步锁可能会阻塞遍历操作。
    • 方案二:使用CopyOnWriteArrayList 替换 ArrayList,推荐使用该方案(即fail-safe)。

fail-safe机制

  • 任何对集合结构的修改都会在一个复制的集合上进行,因此不会抛出ConcurrentModificationException。在 java.util.concurrent 包中的集合,如CopyOnWriteArrayList、ConcurrentHashMap 等,它们的迭代器一般都是采用 Fail-Safe 机制。
  • 缺点:
    • 采用 Fail-Safe 机制的集合类都是线程安全的,但是它们无法保证数据的实时一致性,它们只能保证数据的最终一致性。在迭代过程中,如果集合被修改了,可能读取到的仍然是旧的数据。
    • Fail-Safe 机制还存在另外一个问题,就是内存占用。由于这类集合一般都是通过复制来实现读写分离的,因此它们会创建出更多的对象,导致占用更多的内存,甚至可能引起频繁的垃圾回收,严重影响性能

CopyOnWriteArraySet

方法 描述
int size() 返回集合中的元素数量。
boolean isEmpty() 检查集合是否为空。
boolean contains(Object o) 检查集合是否包含指定的元素。
boolean add(E e) 将指定元素添加到集合中。
boolean remove(Object o) 从集合中移除指定元素。
void clear() 清空集合中的所有元素。
Iterator<E> iterator() 返回在集合上进行迭代的迭代器。
boolean containsAll(Collection<?> c) 检查集合是否包含指定集合中的所有元素。
boolean addAll(Collection<? extends E> c) 将指定集合中的所有元素添加到集合中。
boolean removeAll(Collection<?> c) 从集合中移除指定集合中包含的所有元素。
boolean retainAll(Collection<?> c) 仅保留集合中包含在指定集合中的元素,移除其他元素。

CopyOnWriteArraySet与CopyOnWriteArrayList的区别

  • 数据结构类型:CopyOnWriteArraySet 是一个基于数组的集合,而 CopyOnWriteArrayList 是一个基于数组的列表。

  • 元素的唯一性:CopyOnWriteArraySet 保证集合中的元素是唯一的,不允许重复元素的存在。而 CopyOnWriteArrayList 允许列表中存在重复元素。

  • 集合与列表的特性:CopyOnWriteArraySet 实现了 Set 接口,它是一个无序的集合,不保留插入顺序。CopyOnWriteArrayList 实现了 List 接口,它是一个有序的列表,保留插入顺序。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 创建 CopyOnWriteArraySet 实例
CopyOnWriteArraySet<String> set = new CopyOnWriteArraySet<>();

// 添加元素
set.add("Apple");
set.add("Banana");
set.add("Orange");
set.add("Grapes");

// 打印集合元素,可能得到的输出:[Apple, Banana, Grapes, Orange]
System.out.println("集合元素: " + set);

// 创建 CopyOnWriteArrayList 实例
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

// 添加元素
list.add("Apple");
list.add("Banana");
list.add("Orange");
list.add("Grapes");

// 打印列表元素,得到的输出:[Apple, Banana, Orange, Grapes]
System.out.println("列表元素: " + list);

ConcurrentHashMap

方法 描述
int size() 返回映射中的键值对数量。
boolean isEmpty() 检查映射是否为空。
boolean containsKey(Object key) 检查映射是否包含指定的键。
boolean containsValue(Object value) 检查映射是否包含指定的值。
V get(Object key) 获取与指定键关联的值。
V put(K key, V value) 将指定的键值对添加到映射中。
V remove(Object key) 从映射中移除指定键的映射关系,并返回对应的值。
void clear() 清空映射中的所有键值对。
Set<K> keySet() 返回映射中所有键的集合。
Collection<V> values() 返回映射中所有值的集合。
Set<Map.Entry<K, V>> entrySet() 返回映射中所有键值对的集合。
V putIfAbsent(K key, V value) 当指定的键尚未映射到值时,将指定的键值对添加到映射中。
boolean remove(Object key, Object value) 从映射中移除指定键值对。
boolean replace(K key, V oldValue, V newValue) 用新的值替换指定键的旧值,仅当当前值与指定的旧值相等时才替换。
V replace(K key, V value) 用指定值替换指定键的值。

JDK1.7 中的ConcurrentHashMap

在jdk1.7及其以下的版本中,结构是用Segments数组 + HashEntry数组 + 链表实现的

JDK1.8中的ConcurrentHashMap

jdk1.8抛弃了Segments分段锁的方案,而是改用了和HashMap一样的结构操作,也就是数组 + 链表+ 红黑树结构,比jdk1.7中的ConcurrentHashMap提高了效率,在并发方面,使用了cas +synchronized的方式保证数据的一致性

  • 链表转化为红黑树需要满足2个条件:

    • 1.链表的节点数量大于等于树化阈值8
    • 2.Node数组的长度大于等于最小树化容量值64

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentHashMapExample {
public static void main(String[] args) {
// 创建 ConcurrentHashMap 实例
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// 添加键值对
map.put("Apple", 3);
map.put("Banana", 1);
map.put("Orange", 2);
map.put("Grapes", 4);

// 打印映射内容,映射内容: {Banana=1, Grapes=4, Orange=2, Apple=3}
System.out.println("映射内容: " + map);

// 获取键值对数量
System.out.println("键值对数量: " + map.size());

// 检查是否包含指定键
System.out.println("是否包含键 'Orange': " + map.containsKey("Orange"));

// 获取指定键对应的值
System.out.println("键 'Apple' 对应的值: " + map.get("Apple"));

// 移除指定键的映射关系
map.remove("Banana");

// 打印映射内容
System.out.println("移除键 'Banana' 后的映射内容: " + map);
}
}

ConcurrentSkipListMap

ConcurrentSkipListMap 和 ConcurrentHashMap 是 Java 中用于并发访问的映射数据结构,它们之间有一些区别

  • 数据结构:ConcurrentSkipListMap 是基于跳表(Skip List)的数据结构实现,而 ConcurrentHashMap 是基于数组 + 链表+ 红黑树的数据结构实现。

  • 排序性:ConcurrentSkipListMap 是有序映射,按照键的自然顺序或自定义的比较器对键进行排序。而 ConcurrentHashMap 是无序映射,不保证键值对的顺序。

  • 并发访问性能:在高度并发的情况下,ConcurrentSkipListMap 在读取方面的性能较好,因为它支持并发读取操作,并且有序结构使得读取更高效。而 ConcurrentHashMap 在写入方面的性能较好,因为它使用cas +synchronized来支持并发写入操作。

  • 内存占用:通常情况下,ConcurrentSkipListMap 的内存占用比 ConcurrentHashMap 更高,因为它需要额外的存储空间来维护跳表结构。

  • 功能特性:由于有序性的特点,ConcurrentSkipListMap 提供了一些与顺序相关的方法,如 firstKey()lastKey()subMap() 等。

方法 描述
K firstKey() 返回映射中的第一个键。
K lastKey() 返回映射中的最后一个键。
ConcurrentNavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) 返回一个视图,该视图包含映射中键的子范围。
ConcurrentNavigableMap<K, V> headMap(K toKey, boolean inclusive) 返回一个视图,该视图包含映射中小于(或小于等于)给定键的部分。
ConcurrentNavigableMap<K, V> tailMap(K fromKey, boolean inclusive) 返回一个视图,该视图包含映射中大于(或大于等于)给定键的部分。
ConcurrentNavigableMap<K, V> descendingMap() 返回与此映射相反的顺序的视图。
ConcurrentNavigableSet<K> navigableKeySet() 返回包含映射中所有键的并发可导航集合。
ConcurrentNavigableSet<K> descendingKeySet() 返回与此映射中的键相反顺序对应的并发可导航集合。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.concurrent.ConcurrentSkipListMap;

public class ConcurrentSkipListMapExample {
public static void main(String[] args) {
// 创建 ConcurrentSkipListMap 实例
ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();

// 添加键值对
map.put(3, "Apple");
map.put(1, "Banana");
map.put(2, "Orange");
map.put(4, "Grapes");

// 打印映射内容,映射内容: {1=Banana, 2=Orange, 3=Apple, 4=Grapes}
System.out.println("映射内容: " + map);

// 获取键值对数量
System.out.println("键值对数量: " + map.size());

// 检查是否包含指定键
System.out.println("是否包含键 2: " + map.containsKey(2));

// 获取指定键对应的值
System.out.println("键 3 对应的值: " + map.get(3));

// 移除指定键的映射关系
map.remove(1);

// 打印映射内容
System.out.println("移除键 1 后的映射内容: " + map);

// 获取最小的键
System.out.println("最小的键: " + map.firstKey());

// 获取最大的键
System.out.println("最大的键: " + map.lastKey());

// 获取键小于等于 3 的子映射
ConcurrentSkipListMap<Integer, String> subMap = map.headMap(3, true);
System.out.println("键小于等于 3 的子映射: " + subMap);
}
}

小贴士

跳表

跳表(Skip List)是一种用于实现有序集合的数据结构,它的设计灵感来自于平衡树。跳表通过使用多层链表结构,每一层链表按照升序排列,并且每一层链表都是前一层链表的子集。这样的结构允许在搜索、插入和删除元素时具有较高的效率。

跳表的核心思想是通过建立索引层来加快搜索的速度。最底层是原始链表,每个节点都包含一个元素。而上层的链表是通过原始链表中的一部分节点创建的。在每一层中,节点以一定的概率被提升到更高层,从而形成了跨越多个层级的链接。

跳表的主要优点是在具有合理的设计和维护下,可以在平均情况下以 O(log n) 的时间复杂度执行搜索、插入和删除操作。这是因为每一层的节点数量是下一层的节点数量的一半,从而形成了一种对数级别的分布。

以下是跳表的主要操作:

  • 搜索:从顶层开始,沿着每一层的链表进行比较,如果目标元素大于当前节点的值,则在当前层继续向右移动;如果目标元素小于当前节点的值,则退回到下一层继续比较。直到找到目标元素或者无法再继续向右或下移动。

  • 插入:通过搜索找到插入位置后,在每一层链表中插入新节点,并更新相应的索引层。

  • 删除:通过搜索找到要删除的节点位置后,在每一层链表中删除节点,并更新相应的索引层。

跳表的实现相对简单,它提供了在有序集合中进行快速搜索和更新的高效方式。然而,它的空间复杂度相对于平衡树较高,因为需要维护额外的索引层。跳表在并发环境下也需要考虑同步的问题,以确保数据的一致性和线程安全性。

总结而言,跳表通过建立多层索引结构,在有序集合中实现了较快的搜索、插入和删除操作。它是一种简单而高效的数据结构,在一些场景中可以作为替代平衡树的选择。

ConcurrentLinkedQueue

方法 描述
boolean add(E e) 将指定元素添加到队列的尾部。
boolean offer(E e) 将指定元素添加到队列的尾部。
E poll() 获取并移除队列的头部元素。
E peek() 获取队列的头部元素,但不移除。
int size() 返回队列中的元素数量。
boolean isEmpty() 检查队列是否为空。
boolean contains(Object o) 检查队列是否包含指定元素。
boolean remove(Object o) 从队列中移除指定元素的第一个匹配项。
void clear() 移除队列中的所有元素。
boolean containsAll(Collection<?> c) 检查队列是否包含指定集合中的所有元素。
boolean addAll(Collection<? extends E> c) 将指定集合中的所有元素添加到队列的尾部。
boolean removeAll(Collection<?> c) 从队列中移除包含在指定集合中的所有元素。
boolean retainAll(Collection<?> c) 仅保留队列中包含在指定集合中的元素,移除其他元素。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.concurrent.ConcurrentLinkedQueue;

public class ConcurrentLinkedQueueExample {
public static void main(String[] args) {
// 创建 ConcurrentLinkedQueue 实例
ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<>();

// 添加元素到队列
queue.add("Apple");
queue.add("Banana");
queue.add("Orange");

// 获取队列元素数量
System.out.println("队列元素数量: " + queue.size());

// 检查队列是否为空
System.out.println("队列是否为空: " + queue.isEmpty());

// 获取并移除队列头部元素
String head = queue.poll();
System.out.println("移除的队列头部元素: " + head);

// 获取队列头部元素
String newHead = queue.peek();
System.out.println("新的队列头部元素: " + newHead);

// 打印队列元素
System.out.println("队列元素: " + queue);
}
}

ConcurrentLinkedDeque

方法 描述
void addFirst(E e) 将指定元素插入到双端队列的开头。
void addLast(E e) 将指定元素插入到双端队列的末尾。
boolean offerFirst(E e) 将指定元素插入到双端队列的开头。如果成功则返回 true,否则返回 false
boolean offerLast(E e) 将指定元素插入到双端队列的末尾。如果成功则返回 true,否则返回 false
E pollFirst() 获取并移除双端队列的开头元素。
E pollLast() 获取并移除双端队列的末尾元素。
E peekFirst() 获取双端队列的开头元素,但不移除。
E peekLast() 获取双端队列的末尾元素,但不移除。
boolean removeFirstOccurrence(Object o) 从双端队列中移除首次出现的指定元素。
boolean removeLastOccurrence(Object o) 从双端队列中移除最后一次出现的指定元素。
void push(E e) 将元素推入双端队列的开头。
E pop() 从双端队列的开头弹出一个元素。
boolean remove(Object o) 从双端队列中移除指定元素的第一个匹配项。
boolean contains(Object o) 检查双端队列是否包含指定元素。
int size() 返回双端队列中的元素数量。
boolean isEmpty() 检查双端队列是否为空。
void clear() 移除双端队列中的所有元素。
boolean containsAll(Collection<?> c) 检查双端队列是否包含指定集合中的所有元素。
boolean addAll(Collection<? extends E> c) 将指定集合中的所有元素添加到双端队列的末尾。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.concurrent.ConcurrentLinkedDeque;

public class ConcurrentLinkedDequeExample {
public static void main(String[] args) {
// 创建 ConcurrentLinkedDeque 实例
ConcurrentLinkedDeque<String> deque = new ConcurrentLinkedDeque<>();

// 添加元素到双端队列
deque.addFirst("Apple");
deque.addLast("Banana");
deque.addLast("Orange");

// 获取双端队列元素数量
System.out.println("双端队列元素数量: " + deque.size());

// 检查双端队列是否为空
System.out.println("双端队列是否为空: " + deque.isEmpty());

// 获取并移除双端队列头部元素
String head = deque.pollFirst();
System.out.println("移除的双端队列头部元素: " + head);

// 获取双端队列头部元素
String newHead = deque.peekFirst();
System.out.println("新的双端队列头部元素: " + newHead);

// 获取双端队列尾部元素
String tail = deque.peekLast();
System.out.println("双端队列尾部元素: " + tail);

// 打印双端队列元素
System.out.println("双端队列元素: " + deque);
}
}