并发容器

并发容器

ConcurrentHashMap

如何保证并发安全

ConcurrentHashMap 在 JDK8 的时候将 put() 方法中的分段锁 Segment 移除，转而采用一种 CAS 锁和 synchronized 来实现插入方法的线程安全
由于每一个 Node 的首节点都会被 synchronized 修饰，从而将一个元素的新增转化为一个原子操作，同时 Node 的 value 和 next 都是由 volatile 关键字进行修饰，从而可以保证可见性

Hash 碰撞

JDK8 是直接采用数组+链表+红黑树来实现，时间复杂度在 O(1) 和 O(n) 之间，如果链表转化为红黑树了，那么就是 O(1) 到 O(nlogn)，在这里值得一提的是，ConcurrentHashMap 会判断 tabAt(tab, i = (n - 1) & hash) 是不是 null，是的话就直接采用 CAS 进行插入，而如果不为空的话，则是 synchronized 锁住当前 Node 的首节点，这是因为当该 Node 不为空的时候，证明了此时出现了 Hash 碰撞，就会涉及到链表的尾节点新增或者红黑树的节点新增以及红黑树的平衡，这些操作自然都是非原子性的，从而导致无法使用 CAS，当 Node 的当前下标为 null 的时候，由于只是涉及数组的新增，所以用 CAS 即可

为什么链表长度超过 8 会转为红黑树

默认是链表结构而不是红黑树，因为链表所占用的空间更少
链表长度想要达到 8 很困难，概率只有千万分之 6，如果极端情况发生，那么可以保证在这种极端情况下的查询效率

CopyOnWriteArrayList

写时复制容器：向容器添加一个元素时，先将当前的容器进行复制，生成一个新的容器，然后在向新的容器添加元素，之后再将原容器的引用指向新的容器，这保证了多线程下的并发性和一致性，但是当数据量比较大的时候，就需要考虑效率问题

适用场景

适用于读多写少的并发场景

读写规则

读取是完全不用加锁的，写入也不会阻塞读取操作，只有写入和写入之间需要进行同步等待

缺点

• 数据一致性问题：CopyOnWrite 容器只能保证数据的最终一致性，不能保证数据的实时一致性，所以如果你希望写入的数据能马上读取到，那么请不要使用 CopyOnWrite 容器
• 内存占用问题：因为 CopyOnWrite 容器的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存

写入时复制思想

写入时复制（CopyOnWrite，简称 COW）思想是计算机程序设计领域中的一种优化策略，其核心思想是，如果有多个调用者同时要求相同的资源（如内存或者是磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者视图修改资源内容时，系统才会真正复制一份专用副本给该调用者，而其他调用者所见到的最初的资源仍然保持不变，这过程对其他的调用者都是透明的，此做法主要的优点是如果调用者没有修改资源，就不会有副本被创建，因此多个调用者只是读取操作时可以共享同一份资源

阻塞队列

	抛出异常	特殊值	阻塞	超时
插入	add(e)	offer(e)	put(e)	offer(e,time,unit)
移出	remove()	poll()	task()	poll(time,unit)
检查	element()	peek()	-	-

当队列是空的时，从队列中获取元素的操作将会被阻塞，试图从空的阻塞队列中获取元素的线程将会被阻塞，直到其他的线程往空的队列插入新的元素
当队列是满时，往队列里添加元素的操作会被阻塞，试图往已满的阻塞队列中添加新元素的线程同样也会被阻塞，直到其他的线程使队列重新变得空闲起来

ArrayBlockingQueue

一个有边界的阻塞队列，它的内部实现是一个数组，有边界的意思是它的容量是有限的，我们必须在其初始化的时候指定它的容量大小，容量大小一旦指定就不可改变，创建的时候可以指定是否公平，默认非公平，如果保证公平的话，那么等待了最长时间的线程会被优先处理，不过这会同时带来一定的性能损耗

LinkedBlockingQueue

阻塞队列大小的配置是可选的，如果我们初始化时指定一个大小，它就是有边界的，如果不指定，它就是无边界的，说是无边界，其实是采用了默认大小为 Integer.MAX_VALUE 的容量，它的内部实现是一个链表

PriorityBlockingQueue

一个没有边界的队列（有界，快满时自动扩容，看似无界），它的排序规则和 java.util.PriorityQueue 一样，需要注意，PriorityBlockingQueue 中允许插入 null 对象，所有插入 PriorityBlockingQueue 的对象必须实现 java.lang.Comparable 接口，队列优先级的排序规则就是按照我们对这个接口的实现来定义的，另外，我们可以从 PriorityBlockingQueue 获得一个迭代器 Iterator，但这个迭代器并不保证按照优先级顺序进行迭代

SynchronousQueue

没有容量，是无缓冲等待队列，是一个不存储元素的阻塞队列，会直接将任务交给消费者，必须等队列中的添加元素被消费后才能继续添加新的元素，拥有公平（FIFO）和非公平（LIFO）策略，非公平策略会导致一些数据永远无法被消费的情况

DelayQueue

延迟队列，根据延迟时间排序，元素需要实现 Delayed 接口，规定排序规则

非阻塞队列

ConcurrentLinkedQueue

一个适用于高并发场景下的队列，通过无锁的方式，实现了高并发状态下的高性能，通常 ConcurrentLinkedQueue 性能好于 BlockingQueue，它是一个基于链接节点的无界线程安全队列，使用 CAS 非阻塞算法来实现线程安全(不具备阻塞功能），该队列的元素遵循先进先出的原则，头是最先加入的，尾是最近加入的，该队列不允许 null 元素