java-面试-Java并发容器大合集
概述
java.util包中的大部分容器都是非线程安全的，若要在多线程中使用容器，你可以使用Collections提供的包装函数：synchronizedXXX，将普通容器变成线程安全的容器。但该方法仅仅是简单地给容器使用同步，效率很低。因此并发大师Doug Lea提供了java.util.concurrent包，提供高效的并发容器。并且为了保持与普通的容器的接口一致性，仍然使用util包的接口，从而易于使用、易于理解。
PS：问题：synchronizedXXX究竟对容器做了什么从而能达到线程安全的目的？
类图
List和Set
- JUC包中List接口的实现类：CopyOnWriteArrayList
- CopyOnWriteArrayList是线程安全的ArrayList
- CopyOnWriteArrayList是线程安全的ArrayList
- JUC包中Set接口的实现类：CopyOnWriteArraySet、ConcurrentSkipListSet
- CopyOnWriteArraySet是线程安全的Set，它内部包含了一个CopyOnWriteArrayList，因此本质上是由CopyOnWriteArrayList实现的。
- ConcurrentSkipListSet相当于线程安全的TreeSet。它是有序的Set。它由ConcurrentSkipListMap实现。
- CopyOnWriteArraySet是线程安全的Set，它内部包含了一个CopyOnWriteArrayList，因此本质上是由CopyOnWriteArrayList实现的。
Map
- ConcurrentHashMap：线程安全的HashMap。采用分段锁实现高效并发。
- ConcurrentSkipListMap：线程安全的有序Map。使用跳表实现高效并发。
Queue
- ConcurrentLinkedQueue：线程安全的无界队列。底层采用单链表。支持FIFO。
- ConcurrentLinkedDeque：线程安全的无界双端队列。底层采用双向链表。支持FIFO和FILO。
- ArrayBlockingQueue：数组实现的阻塞队列。
- LinkedBlockingQueue：链表实现的阻塞队列。
- LinkedBlockingDeque：双向链表实现的双端阻塞队列。
CopyOnWrite容器（写时复制容器）
CopyOnWrite容器包括：CopyOnWriteArrayList和CopyOnWriteArraySet。
- PS：CopyOnWriteArraySet有CopyOnWriteArrayList实现。
特性
- 适用于读操作远远多于写操作，并且数据量较小的情况。
- 修改容器的代价是昂贵的，因此建议批量增加addAll、批量删除removeAll。
CopyOnWrite容器是如何实现线程安全的？
- 使用volatile修饰数组引用：确保数组引用的内存可见性。
- 对容器修改操作进行同步：从而确保同一时刻只能有一条线程修改容器（因为修改容器都会产生一个新的容器，增加同步可避免同一时刻复制生成多个容器，从而无法保证数组数据的一致性）
- 修改时复制容器：确保所有修改操作都作用在新数组上，原本的数组在创建过后就用不变化，从而其他线程可以放心地读。
新增方法
CopyOnWriteArrayList：
// 添加集合中不存在的元素
int addAllAbsent(Collection<? extends E> c)
// 该元素若不存在则添加
boolean addIfAbsent(E e)
CopyOnWriteArraySet：木有新增！
迭代
- CopyOnWriteArrayList拥有内部类：COWIterator，它是ListIterator的子类。
- 当调用iterator函数时返回的是COWIterator对象。
- COWIterator不允许修改容器，你若调用则会抛出UnsupportedOperationException。
优点
读操作无需加锁，从而高效。
缺点
- 数据一致性问题
- 由于迭代的是容器当前的快照，因此在迭代过程中容器发生的修改并不能实时被当前正在迭代的线程感知。
- 内存占用问题
- 由于修改容器都会复制数组，从而当数组超大时修改容器效率很低。
- PS：因此写时复制容器适合存储小容量数据。
ConcurrentHashMap
java.util包中提供了线程安全的HashTable，但这家伙只是通过简单的同步来实现线程安全，因此效率低。只要有一条线程获取了容器的锁之后，其他所有的线程访问同步函数都会被阻塞。因此同一时刻只能有一条线程访问同步函数。而ConcurrentHashMap采用了分段锁机制实现高效的并发访问。
分段锁原理
ConcurrentHashMap由多个Segment构成，每个Segment都包含一张哈希表。每次操作只将操作数据所属的Segment锁起来，从而避免将整个锁住。
数据结构
- ConcurrentHashMap内部包含了Segment数组，而每个Segment又继承自ReentrantLock，因此它是一把可重入的锁。
- Segment内部拥有一个HashEntry数组，它就是一张哈希表。HashEntry是单链表的一个节点，HashEntry数组存储单链表的表头节点。
新增API
V putIfAbsent(K key, V value)
ConcurrentSkipListMap
- 它是一个有序的Map，相当于TreeMap。
- TreeMap采用红黑树实现排序，而ConcurrentHashMap采用跳表实现有序。
跳表的由来
作用：存储有序序列，并且实现高效的查找与插入删除。
存储有序序列最简单的办法就是使用数组，从而查找可以采用二分搜索，但插入删除需要移动元素较为低效。
因此出现了二叉搜索树，用来解决插入删除移动元素的问题。但二叉搜索树在最坏情况下会退化成一条单链表，搜索的效率降为O(n)。
为了避免二叉搜索树的退化，出现了二叉平衡树，它在每次插入删除节点后都会重新调整树形，使得它仍然保持平衡，从而保证了搜索效率，也保证了插入删除的效率。
此外，根据平衡算法的不同，二叉平衡树又分为：B+树、B-树、红黑树。
但平衡算法过于复杂，因此出现跳表。
跳表介绍
跳表是条有序的单链表，它的每个节点都有多个指向后继节点的引用。
它有多个层次，上层都是下层的子集，从而能跳过不必要的节点，提升搜索速度。
它通过空间来换取时间。
如查找19的过程：
ConcurrentSkipListSet
- 它是一个有序的、线程安全的Set，相当于线程安全的TreeSet。
- 它内部拥有ConcurrentSkipListMap实例，本质上就是一个ConcurrentSkipListMap，只不过仅使用了Map中的key。
ArrayBlockingQueue
概要
- ArrayBlockingQueue是一个 数组实现的 线程安全的 有限 阻塞队列。
数据结构
- ArrayBlockingQueue继承自AbstractQueue，并实现了BlockingQueue接口。
- ArrayBlockingQueue内部由Object数组存储元素，构造时必须要指定队列容量。
- ArrayBlockingQueue由ReentrantLock实现队列的互斥访问，并由notEmpty、notFull这两个Condition分别实现队空、队满的阻塞。
- ReentrantLock分为公平锁和非公平锁，可以在构造ArrayBlockingQueue时指定。默认为非公平锁。
新增API
// 在队尾添加指定元素，若队已满则等待指定时间
boolean offer(E e, long timeout, TimeUnit unit)
// 获取并删除队首元素，若队为空则阻塞等待
E take()
// 添加指定元素，若队已满则一直等待
void put(E e)
// 获取队首元素，若队为空，则等待指定时间
E poll(long timeout, TimeUnit unit)
队满、队空阻塞唤醒的原理
- 队满阻塞：当添加元素时，若队满，则调用notFull.await()阻塞当前线程；当移除一个元素时调用notFull.signal()唤醒在notFull上等待的线程。
- 队空阻塞：当删除元素时，若队为空，则调用notEmpty.await()阻塞当前线程；当队首添加元素时，调用notEmpty.signal()唤醒在notEmpty上等待的线程。
LinkedBlockingQueue
概要
- LinkedBlockingQueue是一个 单链表实现的、线程安全的、无限 阻塞队列。
数据结构
- LinkedBlockingQueue继承自AbstractQueue，实现了BlockingQueue接口。
- LinkedBlockingQueue由单链表实现，因此是个无限队列。但为了方式无限膨胀，构造时可以加上容量加以限制。
- LinkedBlockingQueue分别采用读取锁和插入锁控制读取/删除 和 插入过程的并发访问，并采用notEmpty和notFull两个Condition实现队满队空的阻塞与唤醒。
队满队空阻塞唤醒的原理
- 队满阻塞：若要插入元素，首先需要获取putLock；在此基础上，若此时队满，则调用notFull.await()，阻塞当前线程；当移除一个元素后调用notFull.signal()唤醒在notFull上等待的线程；最后，当插入操作完成后释放putLock。
- 队空阻塞：若要删除/获取元素，首先要获取takeLock；在此基础上，若队为空，则调用notEmpty.await()，阻塞当前线程；当插入一个元素后调用notEmpty.signal()唤醒在notEmpty上等待的线程；最后，当删除操作完成后释放takeLock。
PS：API和ArrayBlockingQueue一样。
LinkedBlockingDeque
概要
- 它是一个 由双向链表实现的、线程安全的、 双端 无限 阻塞队列。
数据结构
ConcurrentLinkedQueue
概述
- 它是一个由单链表实现的、线程安全的、无限 队列。
数据结构
- 它仅仅继承了AbstractQueue，并未实现BlockingQueue接口，因此它不是阻塞队列，仅仅是个线程安全的普通队列。
特性
- head、tail、next、item均使用volatile修饰，保证其内存可见性，并未使用锁，从而提高并发效率。
- PS：它究竟是怎样在不使用锁的情况下实现线程安全的？
