Java并发编程 ConcurrentLinkedQueue 无界非阻塞队列 以及 写时复制容器

ConcurrentLinkedQueue

linkedList的并发版本，无界非阻塞队列，它是一个基于链表的无界线程安全队列。该队列的元素 遵循先进先出的原则。头是最先加入的，尾是最近加入的。插入元素是追加到
尾上。提取一个元素是从头提取。

大家可以看成是 LinkedList 的并发版本，常用方法：
concurrentLinkedQueue.add(“c”);
concurrentLinkedQueue.offer(“d”);//将指定元素插入到此队列的尾部。 concurrentLinkedQueue.peek();//检索并不移除此队列的头，如果此队列为空，则返回null。 concurrentLinkedQueue.poll();//检索并移除此队列的头，如果此队列为空， 则返回null。

写时复制容器

什么是写时复制容器

CopyOnWriteArrayList 和 CopyOnWriteArraySet

CopyOnWrite 容器即写时复制的容器。通俗的理解是当我们往一个容器添加 元素的时候，不直接往当前容器添加，而是先将当前容器进行
Copy，复制出一 个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指 向新的容器。

这样做的好处是我们可以对 CopyOnWrite 容器进行并发的读，而不需要加锁， 因为当前容器不会添加任何元素。所以
CopyOnWrite 容器也是一种读写分离的思 想，读和写不同的容器。如果读的时候有多个线程正在向
CopyOnWriteArrayList 添加数据，读还是会读到旧的数据，因为写的时候不会锁住旧的
CopyOnWriteArrayList。

CopyOnWrite 并发容器用于对于绝大部分访问都是读，且只是偶尔写的并发
场景。比如白名单，黑名单，商品类目的访问和更新场景，假如我们有一个搜索
网站，用户在这个网站的搜索框中，输入关键字搜索内容，但是某些关键字不允
许被搜索。这些不能被搜索的关键字会被放在一个黑名单当中，黑名单每天晚上
更新一次。当用户搜索时，会检查当前关键字在不在黑名单当中，如果在，则提 示不能搜索。

使用 CopyOnWriteMap 需要注意两件事情：

1. 减少扩容开销。根据实际需要，初始化 CopyOnWriteMap 的大小， 避免写时 CopyOnWriteMap 扩容的开销。
2. 使用批量添加。因为每次添加，容器每次都会进行复制，所以减少添加 次数，可以减少容器的复制次数。

写时复制容器的问题

性能问题
每次修改都创建一个新数组，然后复制所有内容，如果数组比较大，修改操 作又比较频繁，可以想象，性能是很低的，而且内存开销会很大。
数据一致性问题
CopyOnWrite 容器只能保证数据的最终一致性，不能保证数据的实时一致性。 所以如果你希望写入的的数据，马上能读到，不要使用 CopyOnWrite 容器。

阻塞队列BlockingQueue

队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。 因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能
最先从队列中删除，故队列又称为先进先出（FIFO—firstinfirstout）线性表。

什么是阻塞队列

1）支持阻塞的插入方法：意思是当队列满时，队列会阻塞插入元素的线程， 直到队列不满。
2）支持阻塞的移除方法：意思是在队列为空时，获取元素的线程会等待队 列变为非空。

在并发编程中使用生产者和消费者模式能够解决绝大多数并发问题。该模式 通过平衡生产线程和消费线程的工作能力来提高程序整体处理数据的速度。

在线程世界里，生产者就是生产数据的线程，消费者就是消费数据的线程。 在多线程开发中，如果生产者处理速度很快，而消费者处理速度很慢，那么生产 者就必须等待消费者处理完，才能继续生产数据。同样的道理，如果消费者的处 理能力大于生产者，那么消费者就必须等待生产者。

为了解决这种生产消费能力不均衡的问题，便有了生产者和消费者模式。生 产者和消费者模式是通过一个容器来解决生产者和消费者的强耦合问题。生产者 和消费者彼此之间不直接通信，而是通过阻塞队列来进行通信，所以生产者生产 完数据之后不用等待消费者处理，直接扔给阻塞队列，消费者不找生产者要数据， 而是直接从阻塞队列里取，阻塞队列就相当于一个缓冲区，平衡了生产者和消费 者的处理能力。

阻塞队列常用于生产者和消费者的场景，生产者是向队列里添加元素的线程， 消费者是从队列里取元素的线程。阻塞队列就是生产者用来存放元素、消费者用 来获取元素的容器。

• 抛出异常：当队列满时，如果再往队列里插入元素，会抛出 IllegalStateException（“Queuefull”）异常。当队列空时，从队列里获取元素会抛 出 NoSuchElementException 异常。
• 返回特殊值：当往队列插入元素时，会返回元素是否插入成功，成功返回 true。如果是移除方法，则是从队列里取出一个元素，如果没有则返回 null。
• 一直阻塞：当阻塞队列满时，如果生产者线程往队列里 put 元素，队列会 一直阻塞生产者线程，直到队列可用或者响应中断退出。当队列空时，如果消费 者线程从队列里 take 元素，队列会阻塞住消费者线程，直到队列不为空。
• 超时退出：当阻塞队列满时，如果生产者线程往队列里插入元素，队列会 阻塞生产者线程一段时间，如果超过了指定的时间，生产者线程就会退出。

常用阻塞队列

• ArrayBlockingQueue：一个由数组结构组成的有界阻塞队列。
• LinkedBlockingQueue：一个由链表结构组成的有界阻塞队列。
• PriorityBlockingQueue：一个支持优先级排序的无界阻塞队列。
• DelayQueue：一个使用优先级队列实现的无界阻塞队列。
• SynchronousQueue：一个不存储元素的阻塞队列。
• LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。
• LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列。

有界无界 ？

有限队列就是长度有限，满了以后生产者会阻塞，无界队列就是里面能放 无数的东西而不会因为队列长度限制被阻塞，当然空间限制来源于系统资源的限制，如果处理不及时，导致队列越来越大越来越大，超出一定的限制致使内存超 限，操作系统或者 JVM 帮你解决烦恼，直接把你 OOMkill省事了。

ArrayBlockingQueue

是一个用数组实现的有界阻塞队列。此队列按照先进先出（FIFO）的原则对元素进行排序。默认情况下不保证线程公平的访问队列，所谓公平访问队列是指阻塞的线程，可以按照阻塞的先后顺序访问队列，即先阻塞线程先访问队列。非公平性是对先等待的线程是非公平的，当队列可用时，阻塞的线程都可以争夺访问队列的资格，有可能先阻塞的线程最后才访问队列。初始化时有参数可以设置

LinkedBlockingQueue

是一个用链表实现的有界阻塞队列。此队列的默认和最大长度为 Integer.MAX_VALUE。此队列按照先进先出的原则对元素进行排序。

Array实现 和 Linked实现的区别

1. 队列中锁的实现不同
   ArrayBlockingQueue 实现的队列中的锁是没有分离的，即生产和消费用的是同一个锁；
   LinkedBlockingQueue 实现的队列中的锁是分离的，即生产用的是 putLock， 消费是 takeLock
2. 在生产或消费时操作不同
   ArrayBlockingQueue 实现的队列中在生产和消费的时候，是直接将枚举对象 插入或移除的；
   LinkedBlockingQueue 实现的队列中在生产和消费的时候，需要把枚举对象转 换为 Node进行插入或移除，会影响性能
3. 队列大小初始化方式不同
   ArrayBlockingQueue 实现的队列中必须指定队列的大小；
   LinkedBlockingQueue 实现的队列中可以不指定队列的大小，但是默认是 Integer.MAX_VALUE

PriorityBlockingQueue

PriorityBlockingQueue 是一个支持优先级的无界阻塞队列。默认情况下元素 采取自然顺序升序排列。也可以自定义类实现compareTo()方法来指定元素排序 规则，或者初始化 PriorityBlockingQueue 时，指定构造参数Comparator 来对元素 进行排序。需要注意的是不能保证同优先级元素的顺序。

DelayQueue

是一个支持延时获取元素的无界阻塞队列。队列使用 PriorityQueue 来实现。 队列中的元素必须实现 Delayed接口，在创建元素时可以指定多久才能从队列中 获取当前元素。只有在延迟期满时才能从队列中提取元素。

DelayQueue 非常有用，可以将 DelayQueue 运用在以下应用场景。

缓存系统的设计：可以用 DelayQueue 保存缓存元素的有效期，使用一个线 程循环查询 DelayQueue，一旦能从 DelayQueue 中获取元素时，表示缓存有效期 到了。还有订单到期，限时支付等等

SynchronousQueue 是一个不存储元素

是一个不存储元素的阻塞队列。每一个 put 操作必须等待一个 take 操作， 否则不能继续添加元素。SynchronousQueue可以看成是一个传球手，负责把生 产者线程处理的数据直接传递给消费者线程。队列本身并不存储任何元素，非常适合传递性场景。SynchronousQueue 的吞吐量高于 LinkedBlockingQueue 和ArrayBlockingQueue。

LinkedTransferQueue

多了 tryTransfer 和 transfer 方法;

(1)transfer 方法

如果当前有消费者正在等待接收元素（消费者使用 take()方法或带时间限制 的 poll()方法时），transfer方法可以把生产者传入的元素立刻 transfer（传输） 给消费者。如果没有消费者在等待接收元素，transfer 方法会将元素存放在队列 的 tail 节点，并等到该元素被消费者消费了才返回。

(2)tryTransfer 方法

tryTransfer 方法是用来试探生产者传入的元素是否能直接传给消费者。如果 没有消费者等待接收元素，则返回 false。和transfer 方法的区别是 tryTransfer 方 法无论消费者是否接收，方法立即返回，而 transfer方法是必须等到消费者消费 了才返回。

LinkedBlockingDeque

LinkedBlockingDeque 是一个由链表结构组成的双向阻塞队列。所谓双向队列指的是可以从队列的两端插入和移出元素。双向队列因为多了一个操作队列的入 口，在多线程同时入队时，也就减少了一半的竞争。

多了 addFirst、addLast、offerFirst、offerLast、peekFirst 和 peekLast 等方法， 以First 单词结尾的方法，表示插入、获取（peek）或移除双端队列的第一个元 素。以 Last 单词结尾的方法，表示插入、获取或移除双端队列的最后一个元素。 另外，插入方法 add 等同于 addLast，移除方法 remove 等效于 removeFirst。但 是take方法却等同于 takeFirst， 不知道是不是JDK的 bug，使用时还是用带有First 和 Last 后缀的方法更清楚。在初始化 LinkedBlockingDeque 时可以设置容量防止其过度膨胀。另外，双向阻塞队列可以运用在“工作窃取”模式中。

了解阻塞队列的实现原理

使用了等待通知模式实现。所谓通知模式，就是当生产者往满的队列里添加 元素时会阻塞住生产者，当消费者消费了一个队列中的元素后，会通知生产者当前队列可用。通过查看 JDK 源码发现 ArrayBlockingQueue 使用了 Condition 来实 现。其余队列的实现，大家可以自行查看，队列的实现的代码总体来说，并不复杂。