面试系列之-同步容器与高并发容器（JAVA基础）

‍线程安全的同步容器类：‍

除了提供对SortedSet进行同步包装的方法之外，java.util.Collections还提供了一系列对其他的基础容器进行同步包装的方法，如synchronizedList()方法将基础List包装成线程安全的列表容器，synchronizedMap()方法将基础Map容器包装成线程安全的容器，synchronizedCollection()方法将基础Collection容器包装成线程安全的Collection容器与同步包装方法相对应，java.util.Collections还提供了一系列同步包装类，这些包装类都是其内部类。这些同步包装类的实现逻辑很简单：实现了容器的操作接口，在操作接口上使用synchronized进行线程同步，然后在synchronized的临界区将实际的操作委托给被包装的基础容器。‍高并发容器：‍ JUC高并发容器是基于非阻塞算法（或者无锁编程算法）实现的容器类，无锁编程算法主要通过CAS（Compare And Swap）+Volatile组合实现，通过CAS保障操作的原子性，通过volatile保障变量内存的可见性。无锁编程算法的主要优点如下： （1）开销较小：不需要在内核态和用户态之间切换进程。 （2）读写不互斥：只有写操作需要使用基于CAS机制的乐观锁， 读读操作之间可以不用互斥。 JUC包中提供了List、Set、Queue、Map各种类型的高并发容器，如ConcurrentHashMap、ConcurrentSkipListMap、ConcurrentSkipListSet、CopyOnWriteArrayList和CopyOnWriteArraySet。在性能上，ConcurrentHashMap通常优于同步的HashMap，ConcurrentSkipListMap通常优于同步的TreeMap。当读取和遍历操作远远大于列表的更新操作时，CopyOnWriteArrayList优于同步的ArrayList。 List：JUC包中的高并发List主要有CopyOnWriteArrayList，对应的基础容器为ArrayList。CopyOnWriteArrayList相当于线程安全的ArrayList，它实现了List接口。在读多写少的场景中，其性能远远高于ArrayList的同步包装容器。 Set：·CopyOnWriteArraySet继承自AbstractSet类，对应的基础容器为HashSet。其内部组合了一个CopyOnWriteArrayList对象，它的核心操作是基于CopyOnWriteArrayList实现的。 ·ConcurrentSkipListSet是线程安全的有序集合，对应的基础容器为TreeSet。它继承自AbstractSet，并实现了NavigableSet接口。ConcurrentSkipListSet是通过ConcurrentSkipListMap实现的。 Map：·ConcurrentHashMap对应的基础容器为HashMap。JDK 6中的ConcurrentHashMap采用一种更加细粒度的“分段锁”加锁机制，JDK 8中采用CAS无锁算法。 ·ConcurrentSkipListMap对应的基础容器为TreeMap。其内部的SkipList（跳表）结构是一种可以代替平衡树的数据结构，默认是按照Key值升序的。 Queue：JUC包中的Queue的实现类包括三类：单向队列、双向队列和阻塞队列。 ·ConcurrentLinkedQueue是基于列表实现的单向队列，按照FIFO（先进先出）原则对元素进行排序。新元素从队列尾部插入，而获取队列元素则需要从队列头部获取。 ·ConcurrentLinkedDeque是基于链表的双向队列，但是该队列不允许null元素。ConcurrentLinkedDeque可以当作“栈”来使用，并且高效地支持并发环境。 ·ArrayBlockingQueue：基于数组实现的可阻塞的FIFO队列。 ·LinkedBlockingQueue：基于链表实现的可阻塞的FIFO队列。 ·PriorityBlockingQueue：按优先级排序的队列。 ·DelayQueue：按照元素的Delay时间进行排序的队列。 ·SynchronousQueue：无缓冲等待队列。

BlockingQueue重点讲解

阻塞队列与普通队列（ArrayDeque等）之间的最大不同点在于阻塞队列提供了阻塞式的添加和删除方法。

（1）阻塞添加

阻塞添加是指当阻塞队列元素已满时，队列会阻塞添加元素的线程，直到队列元素不满时，才重新唤醒线程执行元素添加操作。

（2）阻塞删除

阻塞删除是指在队列元素为空时，删除队列元素的线程将被阻塞，直到队列不为空时，才重新唤醒删除线程，再执行删除操作。

public interface BlockingQueue<E> extends Queue<E> {
//将指定的元素添加到此队列的尾部
//在成功时返回true，如果此队列已满，就抛出IllegalStateException
boolean add(E e);
//非阻塞式添加：将指定的元素添加到此队列的尾部（如果立即可行且不会超过该队列的容量）
//如果该队列已满，就直接返回
boolean offer(E e)
//限时阻塞式添加：将指定的元素添加到此队列的尾部
//如果该队列已满，那么在到达指定的等待时间之前，添加线程会阻塞，等待可用的空间，
//该方法可中断
boolean offer(E e, long timeout, TimeUnit unit)
throws InterruptedException;
//阻塞式添加：将指定的元素添加到此队列的尾部，如果该队列已满，就一直等待（阻塞）
void put(E e) throws InterruptedException;
//阻塞式删除：获取并移除此队列的头部，如果没有元素就等待（阻塞）
//直到有元素，将唤醒等待线程执行该操作
E take() throws InterruptedException;
//非阻塞式删除：获取并移除此队列的头部，如果没有元素就直接返回null（空）
E poll() throws InterruptedException;
//限时阻塞式删除:获取并移除此队列的头部，在指定的等待时间前一直等待获取元素，超过时间，
//方法将结束
E poll(long timeout, TimeUnit unit) throws InterruptedException;
//获取但不移除此队列的头元素，没有则抛出异常NoSuchElementException
E element();
//获取但不移除此队列的头元素，如果此队列为空，就返回null
E peek();
//从此队列中移除指定元素，返回删除是否成功
boolean remove(Object o);
}

常见的BlockingQueue：

1.ArrayBlockingQueue

ArrayBlockingQueue是一个常用的阻塞队列，是基于数组实现的，其内部使用一个定长数组来存储元素。除了一个定长数组外，ArrayBlockingQueue内部还保存着两个整型变量，分别标识着队列的头部和尾部在数组中的位置。

ArrayBlockingQueue的添加和删除操作共用同一个锁对象，由此意味着添加和删除无法并行运行，这点不同于LinkedBlockingQueue。ArrayBlockingQueue完全可以将添加和删除的锁分离，从而添加和删除操作完全并行。

为什么ArrayBlockingQueue比LinkedBlockingQueue更加常用？前者在添加或删除元素时不会产生或销毁任何额外的Node（节点）实例，而后者会生成一个额外的Node实例。在长时间、高并发处理大批量数据的场景中，LinkedBlockingQueue产生的额外Node实例会加大系统的GC压力。

虽然LinkedBlockingQueue并发程度较高，但是入队需要新增节点，创建节点对象。而ArrayBlockingQueue可以重用队列存放数组。

DelayQueue：

DelayQueue中的元素只有当其指定的延迟时间到了，才能够从队列中获取该元素。DelayQueue是一个没有大小限制的队列，因此往队列中添加数据的操作（生产者）永远不会被阻塞，而只有获取数据的操作（消费者）才会被阻塞。

DelayQueue的使用场景较少，但是相当巧妙，常见的例子是使用DelayQueue来管理一个超时未响应的连接队列。

SynchronousQueue：

一种无缓冲的等待队列，类似于无中介的直接交易，有点像原始社会中的生产者和消费者，生产者拿着产品去集市销售给产品的最终消费者，而消费者必须亲自去集市找到所要商品的直接生产者，如果一方没有找到合适的目标，那么大家都在集市等待。相对于有缓冲的阻塞队列（如LinkedBlockingQueue）来说，SynchronousQueue少了中间缓冲区（如仓库）的环节。如果有仓库，生产者直接把产品批发给仓库，不需要关心仓库最终会将这些产品发给哪些消费者，由于仓库可以中转部分商品，总体来说有仓库进行生产和消费的吞吐量高一些。反过来说，又因为仓库的引入，使得产品从生产者到消费者中间增加了额外的交易环节，单个产品的及时响应性能可能会降低，所以对单个消息的响应要求高的场景可以使用SynchronousQueue。

声明一个SynchronousQueue有两种不同的方式：公平模式和非公平模式。公平模式的SynchronousQueue会采用公平锁，并配合一个FIFO队列来阻塞多余的生产者和消费者，从而体现出整体的公平特征。非公平模式（默认情况）的SynchronousQueue采用非公平锁，同时配合一个LIFO堆栈（TransferStack内部实例）来管理多余的生产者和消费者。对于后一种模式，如果生产者和消费者的处理速度有差距，就很容易出现线程饥渴的情况，即可能出现某些生产者或者消费者的数据永远都得不到处理。

ArrayBlockingQueue：

ArrayBlockingQueue中的元素访问存在公平访问与非公平访问两种方式，所以ArrayBlockingQueue可以分别作为公平队列和非公平队列使用：

（1）对于公平队列，被阻塞的线程可以按照阻塞的先后顺序访问队列，即先阻塞的线程先访问队列。

（2）对于非公平队列，当队列可用时，阻塞的线程将进入争夺访问资源的竞争中，也就是说谁先抢到谁就执行，没有固定的先后顺序。

//默认非公平阻塞队列
ArrayBlockingQueue queue = new ArrayBlockingQueue(capacity);
//公平阻塞队列
ArrayBlockingQueue queue1 = new ArrayBlockingQueue(capacity,true);

//只带一个capacity参数的构造器
public ArrayBlockingQueue(int capacity) {
this(capacity, false);
}
//带两个参数的构造器
public ArrayBlockingQueue(int capacity, boolean fair) {
if (capacity <= 0)
throw new IllegalArgumentException();
this.items = new Object[capacity];
lock = new ReentrantLock(fair); //根据fair参数构造公平锁/获取非公平锁
    notEmpty = lock.newCondition(); //有元素加入，队列为非空
    notFull = lock.newCondition(); //有元素被取出，队列为未满
}

public class ArrayBlockingQueue<E> extends AbstractQueue<E>
implements BlockingQueue<E>, java.io.Serializable {
/** 存储数据的数组 */
    final Object[] items;
/**获取、删除元素的索引，主要用于take、poll、peek、remove方法 */
int takeIndex;
/**添加元素的索引，主要用于 put、offer、add方法*/
int putIndex;
/** 队列元素的个数 */
int count;
/** 控制并发访问的显式锁 */
    final ReentrantLock lock;
/**notEmpty条件对象，用于通知take线程（消费队列），可执行删除操作 */
private final Condition notEmpty;
/**notFull条件对象，用于通知put线程（生产队列），可执行添加操作 */
private final Condition notFull;
/**
    迭代器
    */
    transient Itrs itrs = null;
}

ArrayBlockingQueue内部是通过数组对象items来存储所有的数据的，通过ReentrantLock类型的成员lock控制添加线程与删除线程的并发访问。ArrayBlockingQueue使用等待条件对象notEmpty成员来存放或唤醒被阻塞的消费（take）线程，当数组对象items有元素时，告诉take线程可以执行删除操作。同理，ArrayBlockingQueue使用等待条件对象notFull成员来存放或唤醒被阻塞的生产（put）线程，当队列未满时，告诉put线程可以执行添加元素的操作。