并发容器
并发容器
作者：IT王小二
一、小知识
1. hash
就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。常用 HASH 函数：直接取余法、乘法取整法、平方取中法。
hash冲突的处理办法。
1、开放寻址法。 2、再散列法。 3、链地址法(拉链法)常用 hash 算法的介绍（1. MD4 2. MD5 3. SHA-1）。
HashMap解决冲突的办法：链地址法。
2. 位运算
- 位与 & (1&1=1 0&0=0 1&0=0)
- 位或 | (1|1=1 0|0=0 1|0=1)
- 位非 ~ (~1=0 ~0=1)
- 位异或 ^ (1^1=0 1^0=1 0^0=0)
- 有符号右移>>(若正数,高位补 0,负数,高位补 1)
- 有符号左移<<
- 无符号右移>>>(不论正负,高位均补 0)
有趣的取模性质：
取模 a % (2^n) 等价于 a & (2^n - 1)，所以在 map 里的数组个数一定是 2 的乘方数，计算 key 值在哪个元素中的时候，就用位运算来快速定位，例如 a % 4 等价于 a & (2^2 -1)，但是后者速度更快。
二、ConcurrentHashMap（并发版HashMap）
HashMap 在多线程并发扩容时容易造成死循环，为了弥补这个不足，所以需要使用ConcurrentHashMap 。
底层依然是哈希表，但在JAVA8中有了不小的改变，而JAVA7和JAVA8都是用的比较多的版本，因此经常会将这两个版本的实现方式做一些比较（比如面试中。。）
三、HashTable
HashTable 容器使用 synchronized 来保证线程安全，但在线程竞争激烈的情况下 HashTable 的效率非常低下。因为当一个线程访问 HashTable 的同步方法，其他线程也访问 HashTable 的同步方法时，会进入阻塞或轮询状态。如线程 1 使用 put 进行元素添加，线程 2 不但不能使用 put 方法添加元素，也不能使用 get方法来获取元素，所以竞争越激烈效率越低。
四、ConcurrentSkipList 系列
- ConcurrentSkipListMap 有序 Map （并发版TreeMap）
- ConcurrentSkipListSet 有序 Set （并发版TreeSet）
TreeMap 和 TreeSet 使用红黑树按照 key 的顺序（自然顺序、自定义顺序）来使得键值对有序存储，但是只能在单线程下安全使用；多线程下想要使键值对按照 key 的顺序来存储，则需要使用 ConcurrentSkipListMap 和 ConcurrentSkipListSet，分别用以代替 TreeMap 和 TreeSet，存入的数据按 key 排序。在实现上，ConcurrentSkipListSet 本质上就是 ConcurrentSkipListMap 。
什么是跳表
跳表其实也是一种通过“空间来换取时间”的一个算法，令链表的每个结点不仅记录 next 结点位置，还可以按照 level 层级分别记录后继第 level 个结点。此法使用的就是“先大步查找确定范围，再逐渐缩小迫近”的思想进行的查找。
比如：
比如我们想查找 50，首先和 20 比较，大于 20 之后，在和 40 进行比较，然后在和 70 进行比较，发现 70 大于 50，说明查找的点在 40 和 50 之间，从这个过程中，我们可以看出，查找的时候跳过了 30。
五、写时复制容器
CopyOnWriteArrayList 和 CopyOnWriteArraySet。
CopyOnWrite 容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。
这样做的好处是我们可以对 CopyOnWrite 容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以 CopyOnWrite 容器也是一种读写分离的思想，读和写不同的容器。如果读的时候有多个线程正在向 CopyOnWriteArrayList 添加数据，读还是会读到旧的数据，因为写的时候不会锁住旧的 CopyOnWriteArrayList。
写时复制容器的问题：
- 性能问题：每次修改都创建一个新数组，然后复制所有内容，如果数组比较大，修改操作又比较频繁，可以想象，性能是很低的，而且内存开销会很大。
- 数据的一致性问题：CopyOnWrite 容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，不要使用 CopyOnWrite 容器。
使用 CopyOnWriteMap 需要注意两件事情：
1、减少扩容开销。根据实际需要，初始化 CopyOnWriteMap 的大小，避免写时 CopyOnWriteMap 扩容的开销。 2、使用批量添加。因为每次添加，容器每次都会进行复制，所以减少添加次数，可以减少容器的复制次数。
六、BlockingQueue（阻塞队列）
1. 队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
2. 什么是阻塞队列
1、支持阻塞的插入方法：意思是当队列满时，队列会阻塞插入元素的线程，直到队列不满。 2、支持阻塞的移除方法：意思是在队列为空时，获取元素的线程会等待队列变为非空。
为了解决生产消费能力不均衡的问题，便有了生产者和消费者模式。生产者和消费者模式是通过一个容器来解决生产者和消费者的强耦合问题。生产者和消费者彼此之间不直接通信，而是通过阻塞队列来进行通信，所以生产者生产完数据之后不用等待消费者处理，直接扔给阻塞队列，消费者不找生产者要数据，而是直接从阻塞队列里取，阻塞队列就相当于一个缓冲区，平衡了生产者和消费者的处理能力。
3. 常见阻塞队列
- ArrayBlockingQueue：一个由数组结构组成的有界阻塞队列
- LinkedBlockingQueue：一个由链表结构组成的有界阻塞队列
- PriorityBlockingQueue：一个支持优先级排序的无界阻塞队列
- DelayQueue：一个使用优先级队列实现的无界阻塞队列
- SynchronousQueue：一个不存储元素的阻塞队列
- LinkedTransferQueue：一个由链表结构组成的无界阻塞队列
- LinkedBlockingDeque：一个由双向链表结构组成的有界阻塞队列
以上的阻塞队列都实现了 BlockingQueue 接口，也都是线程安全的。
有界无界
- 有限队列就是长度有限，满了以后生产者会阻塞。
- 无界队列就是里面能放无数的东西而不会因为队列长度限制被阻塞，当然空间限制来源于系统资源的限制，如果处理不及时，导致队列越来越大越来越大，超出一定的限制致使内存超限，就会导致OOM。所以，无界队列需要谨慎使用。
ArrayBlockingQueue
是一个用数组实现的有界阻塞队列。此队列按照先进先出（FIFO）的原则对元素进行排序。
LinkedBlockingQueue
是一个用链表实现的有界阻塞队列。此队列的默认和最大长度为 Integer.MAX_VALUE。此队列按照先进先出的原则对元素进行排序。
ArrayBlockingQueue 和 LinkedBlockingQueue对比
1、队列中锁的实现不同。
- ArrayBlockingQueue 实现的队列中的锁是没有分离的，即生产和消费用的是同一个锁
- LinkedBlockingQueue 实现的队列中的锁是分离的，即生产用的是 putLock，消费是 takeLock
2、在生产或消费时操作不同。
- ArrayBlockingQueue 实现的队列中在生产和消费的时候，是直接将枚举对象插入或移除的。
- LinkedBlockingQueue 实现的队列中在生产和消费的时候，需要把枚举对象转换为
Node<E>进行插入或移除，会影响性能。
3、队列大小初始化方式不同。
- ArrayBlockingQueue 实现的队列中必须指定队列的大小。
- LinkedBlockingQueue 实现的队列中可以不指定队列的大小，但是默认是Integer.MAX_VALUE。
PriorityBlockingQueue
PriorityBlockingQueue 是一个支持优先级的无界阻塞队列。默认情况下元素采取自然顺序升序排列，也可以自定义类实现 compareTo()方法来指定元素排序规则。
DelayQueue
是一个支持延时获取元素的无界阻塞队列。队列使用 PriorityQueue 来实现。队列中的元素必须实现 Delayed 接口，在创建元素时可以指定多久才能从队列中，获取当前元素。只有在延迟期满时才能从队列中提取元素，应用场景常有订单到期，限时支付等，但是有更好的解决方案，比如Redis。
SynchronousQueue
是一个不存储元素的阻塞队列。每一个 put 操作必须等待一个 take 操作，否则不能继续添加元素。
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）或移除双端队列的第一个元素。
4. 阻塞队列的原理
使用了等待通知模式实现。所谓通知模式，就是当生产者往满的队列里添加元素时会阻塞住生产者，当消费者消费了一个队列中的元素后，会通知生产者当前队列可用。
通过查看 JDK 源码发现 ArrayBlockingQueue 使用了 Lock + Condition 来实现。