极客们，请收下2021 微软 x 英特尔黑客松大赛英雄帖！>>>
摘要
为什么没见人用<code>vector</code>和<code>hashtable</code>了？<code>hashmap</code>它又线程不安全在哪里？
<code>concurrenthashmap</code>的进化与骚操作有哪些？
copy-on-write是个啥思想？有哪些例子？
为什么需要并发队列？又有哪些我们视而不见的并发的队列？
当我们想控制线程的先来后到时该咋办？一个个去讲道理吗？
并发容器
先总览一下这些并发容器都在整什么幺蛾子
很简单，别想太多，就是因为性能不好。
我们先看一看<code>vector</code>的<code>get</code>方法：
look, look, 这个 <code>synchronized</code>是直接修饰在方法上的，如果你上下翻翻，就可以发现基本上这个类的所有方法都是 <code>synchronized</code>修饰的。
那有人可能问了，为什么锁方法就性能差？因为这个锁粒度是实例对象呀
<code>hashtable</code>也是如此。
同时put碰撞导致数据丢失
比如两个线程都放数据，使用同样的key，那么它们计算出来的hash值是一样的并放在同一位置，这必然会导致一个数据丢失
同时put扩容导致数据丢失
同时扩容时，只会保留一个扩容的数组。
死循环造成cpu100%
多线程同时扩容，可能会造成循环链表导致cpu100%。但是这个问题本身追究并无意义（sun官方也是这么认为的，他觉得你就不应该用hashmap来解决并发场景，这本身就有问题不是吗？）。如果着实有兴趣可以瞅瞅这个 coolshell.cn/articles/96…
数据结构
1.7时的结构（segment + hashentry + unsafe）：
1.8时的结构（移除segment，使锁的粒度更小，synchronized + cas + node + unsafe）：
hash碰撞
将原本的拉链法变为如果节点数超过8个以后就变换为红黑树。
这里有一个小问题，为什么超过8就转为红黑树？为什么是8？为什么不一开始就使用红黑树？
红黑树每个节点占用空间是链表的两倍。
作者用泊松分布的概率计算，到8的时候概率也就是极小了。
保证并发安全
1.7使用分段锁segment(extends reentreenlock)来保证16个段的安全（段不可动态增加）；1.8使用<code>cas</code> + <code>synchronized</code>来保证，粒度为每个node。
查询复杂度
当冲突超过8个时也能保证查询效率，由原来的拉链法的<code>o(n)</code>变为红黑树的<code>o(logn)</code>
显然，<code>concurrenthashmap</code>是保证了同时put的并发安全性，但是并没有说，你同时执行<code>a++</code>时也是线程安全的：
那让我们来想想，咋解决这个问题呢？
把这段用<code>synchronized</code>包起来吗？
那使用<code>concurrenthashmap</code>还有什么意义呢？我们来看看这样一个方法：replace
再看一个组合操作，用于解决相同key的put覆盖问题：<code>putifabsent</code>
用来代替<code>vector</code>和<code>synchronizedlist</code>，就和<code>concurrenthashmap</code>代替<code>synchronizedmap</code>的原因一样
<code>vector</code>和<code>synchronizedlist</code>的锁的粒度太大，并发效率相比较低，并且在遍历时无法修改。
copy-on-write容器还包括<code>copyonwritearrayset</code>，用于替代同步的<code>set</code>
读多写少
读操作需要尽可能的快，而写操作哪怕慢一些也无伤大雅，例如：黑名单场景。
写入实时性要求不高
就是说，我的修改不是说非得立即生效，哪怕是有那么一小会，还是在读之前的数据，也没关系。
读读同步、读写同步、写写互斥
看起来是不是和读写锁的规则贼像？但是不一样哦。这里有一个升级，就是你即便在写，我也是可以读的。
我们来看一下写入的时候
上来先锁住，然后整一个新的数组出来，把新元素怼进去，再改一下原地址，解锁，一气呵成。
读取的时候呢？
啥保护措施都没有的，读就完事了。
copyonwrite原理：写入时会先搞一个副本出来，写好以后改地址
“不变性”原理：每个list都相当于一个不可变的集合，没有修改操作在上面进行
数据一致性：只能保证最终数据的一致性，不能保证实时一致性。
内存占用：副本可是占用一倍的内存的哦。
就是保证了并发安全的队列，分为阻塞队列（如下图）和非阻塞队列，阻塞与非阻塞的区别就是，你放入（或者取出）元素时，在队列已满（或者已空）的情况下会不会阻塞。
阻塞队列最典型的应用就是生产者消费者。
那上图的这些队列有何特点呢？我们一一道来
<code>arrayblockingqueue</code>: 有界、可指定容量、底层由数组实现、可设置公平与否
我们可以看到在放入元素那一步使用了可重入锁的锁住（可打断）的方法。
<code>priorityblockingqueue</code>: 支持优先级设置（依据对象的自然排序顺序或者是构造函数所带的comparator）、队列的出入顺序是设置的顺序（不是先进先出）、无界队列、<code>priorityqueue</code>的线程安全版本。
<code>linkedblockingqueue</code>: 默认无界(容量为integer.max_value，容量可指定）、内部结构为一个node数组+两把锁、一般情况下性能优于<code>arrayblockingqueue</code>（锁粒度更小）
这里使用的是<code>condition</code> + <code>reentrantlock</code>，其实就相当于 <code>synchronized</code> + <code>object.wait()</code> + <code>object.notify()</code>，这是一个适用于生产者消费者的绝佳队列，如果想看原生实现可以瞅瞅我在并发原理中利用 wait + notify 实现的生产者消费者。
我们看这个放入元素的方法就可以理解到：如果队列已满，则阻塞，否则就放一个元素，如果还可以继续放，则唤醒在notfull中等待的线程，如果放之前队列为空，则唤醒在notempty上等待的线程。
<code>synchronousqueue</code>: 容量为0不是1、线程池<code>executors.newcachethreadpool()</code>使用的阻塞队列
它没有实际的容量，任意线程（生产者线程或者消费者线程，生产类型的操作比如put，offer，消费类型的操作比如poll，take）都会等待知道获得数据或者交付完成数据才会返回，一个生产者线程的使命是将线程附着着的数据交付给一个消费者线程，而一个消费者线程则是等待一个生产者线程的数据。
<code>concurrentlinkedqueue</code>: 并发包中唯一一个非阻塞的队列，内部由链表实现、核心思想也是cas。
<code>delayqueue</code>: 延迟队列（根据延迟时间排序）、元素需实现<code>delayed</code>接口（规定排序规则）
控制并发流程
先瞅瞅都有哪些可以控制并发流程
一个线程等多个线程执行完成
在媒体处理中，拼接命令需要等所有待拼接的任务下载完成后才执行。
多个线程等一个线程执行完
压测场景下，所有线程等一声令下立马向服务器施加压力，而不是还去慢悠悠的创建线程。
多等多
下面举一个小栗子，模拟运动员跑步的场景，所有运动员等枪响后开跑，待运动员都到达终点后裁判才宣布比赛结束。
这个类不能重用，即不可以重新计数。如果需要重用，考虑cyclicbarrier和建新的实例。
需要控制并发的线程数时。
例如：在媒体处理的场景中，一台机器的cpu性能是有限的，我们最多只能允许3个转码任务同时进行，这个时候就需要控制执行转码的线程数量了。
我们用一张图来理解一下：
接下来看一个小demo
注意点：
获取和释放的数量必须一致（比如你请求的是3个，但是你却每次只释放2个，那这个许可证岂不是就越用越少了，这玩意并没有在类的层面进行限制，所以需要编码时候注意）。
公平性一般设置为true比较合理（因为信号量一般用在控制慢服务，如果你还设置不公平，就很容易导致饥饿）。
并不是必须由请求的线程去释放，也可以由其他线程去释放（可以是线程a获取了2个，线程b没有获取，只去释放2个）。
作用不同：<code>cyclicbarrier</code>需要等待固定数量的线程到达栅栏后才能继续执行，而<code>countdownlatch</code>只需要计数到0即可。也就是说，<code>countdownlatch</code>用于事件，<code>cyclicbarrier</code>用于线程。
来看一个<code>cyclicbarrier</code>的demo：
可重用性不同：<code>new cyclicbarrier(5)</code>等5个线程到了后执行<code>run</code>，还可以继续等接下来的5个线程到。
总结
呼呼，总算说完了花里胡哨的并发容器，现在知道了可以用copyonwrite去解决读多写少的场景；用阻塞队列去实现生产者消费者模型；用<code>countdownlatch</code>来驯服一个个溜得贼快的线程。
下一章我们搞个大事情，并发界的总统山：<code>aqs</code>。尝试着利用<code>aqs</code>去实现一个我们自己的并发工具。