1. 并发容器

1：ConcurrentHashMap

线程安全的HashMap

2：CopyOnWriteArrayList:线程安全的List

3：BlockingQueue

这是一个接口，表示阻塞队列，适用于作为数据共享的通道。

4：ConcurrentLinkedQueue

高效的非阻塞并发队列，使用链表实现。可以看做一个线程安全的LinkedList

2. ConcurrentHashMap

1：结构图

1.7结构图

Java7中的ConcurrentHashMap最外层是多个segment,每个segment的底层数据结构与HashMap类似，仍然是数组和链表组成的拉链法。

每个segment独立上ReentrantLock锁，每个segment之间互不影响，提高并发效率。

默认有16个segment，最多可以同时支持16个线程并发写（操作分别分布在不同的Segment上）。这个默认值可以在初始化时设置，但一旦初始化以后，就不可以再扩容了。

 

1.8结构图

ConcurrentHashMap是一个存储 key/value 对的容器，并且是线程安全的。  

改进一： 取消segments字段，直接采用transient volatile HashEntry<K,V>[] table保存数据，采用table数组元素作为锁，从而实现了对每一行数据进行加锁，进一步减少并发冲突的概率。

改进二： 将原先table数组＋单向链表的数据结构，变更为table数组＋单向链表＋红黑树的结构。查询的时间复杂度可以降低到O(logN)

这是经典的数组加链表的形式。 并且在链表长度过长时转化为红黑树存储（ Java 8 的优化） ， 加快查找速度。

存储结构定义了容器的“形状”， 那容器内的东西按照什么规则来放呢？ 换句话讲， 某个 key 是按照什么逻辑放入容器的对应位置呢？

总结

1、 ConcurrentHashMap 采用数组+链表+红黑树的存储结构

2、 存入的Key值通过自己的 hashCode 映射到数组的相应位置

3、 ConcurrentHashMap 为保障查询效率， 在特定的时候会对数据增加长度， 这个操作叫做扩容

4、 当链表长度增加到 8 时， 可能会触发链表转为红黑树（数组长度如果小于 64， 优先扩容）

2：put方法

主线流程梳理如下图：

这个put的过程很清晰，对当前的table进行无条件自循环直到put成功，可以分成以下六步流程来概述：

1、如果没有初始化，就先调用initTable（）方法来进行初始化过程

2、如果没有hash冲突，就直接CAS插入

3、如果还在进行扩容操作，就先进行扩容

4、如果存在hash冲突，就加锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入，

5、最后，如果该链表的数量大于阈值8，就要先转换成黑红树的结构，break再一次进入循环

6、如果添加成功，就调用addCount（）方法统计size，并且检查是否需要扩容

3：spread方法

1：原理解释

哈希算法的逻辑， 决定 ConcurrentHashMap 保存和读取速度。 hash 算法是 hashmap 的核心算法， JDK 的实现十分巧妙， 值得我们学习

spreed方法源代码如下：

static final int spread(int h) {
return (h ^(h >>> 16)) & HASH_BITS;
}

传入的参数h为 key 对象的 hashCode， spreed 方法对 hashCode 进行了加工。 重新计算出 hash。 我们先暂不分析这一行代码的逻辑， 先继续往下看如何使用此 hash 值。

hash 值是用来映射该 key 值在哈希表中的位置。 取出哈希表中该 hash 值对应位置的代码如下。

tabAt(tab, i = (n - 1) & hash)

我们先看这一行代码的逻辑， 第一个参数为哈希表， 第二个参数是哈希表中的数组下标。 通过 (n - 1) & hash 计算下标。 n 为数组长度， 我们以默认大小 16 为例， 那么 n-1 = 15， 我们可以假设 hash 值为 100， 那么 15 & 100为多少呢？ & 把它左右数值转化为二进制， 按位进行与操作， 只有两个值都为 1 才为 1， 有一个为 0 则为 0。 那么我们把 15 和 100 转化为二进制来计算， java中 int 类型为 8 个字节， 一共 32 个bit位。

n的值15转为二进制：

0000 0000 0000 0000 0000 0000 0000 1111

hash的值100转为二进制：

0000 0000 0000 0000 0000 0000 0110 0100。

计算结果：

0000 0000 0000 0000 0000 0000 0000 0100

对应的十进制值为 4

是不是已经看出点什么了？ 15的二进制高位都为0， 低位都是1。 那么经过&计算后， hash值100的高位全部被清零， 低位则保持不变， 并且一定是小于（n-1） 的。 也就是说经过如此计算， 通过hash值得到的数组下标绝对不会越界。

2：数组大小必须为 2 的 n 次方

第一个问题的答案是数组大小必须为 2 的 n 次方， 也就是 16、 32、 64….不能为其他值。 因为如果不是 2 的 n 次方， 那么经过计算的数组下标会增大碰撞的几率， 例如数组长度为 21， 那么 n-1=20， 对应的二进制为：10100

那么hash值的二进制如果是 10000（十进制16） 、 10010（十进制18） 、 10001（十进制17） ， 和10100做&计算后， 都是10000， 也就是都被映射到数组16这个下标上。 这三个值会以链表的形式存储在数组16下标的位置。 这显然不是我们想要的结果。

但如果数组长度n为2的n次方， 2进制的数值为10， 100， 1000， 10000……n-1后对应二进制为1， 11， 111， 1111……这样和hash值低位&后， 会保留原来hash值的低位数值， 那么只要hash值的低位不一样， 就不会发生碰撞。

其实如果数组长度为 2 的 n 次方， 那么 (n - 1) & hash 等价于 hash%n。

如果为了保证不越界为什么不直接用 % 计算取余数？

3：为什么不直接用hash%n

按位的操作效率会更高， 经过我本地测试， & 计算速度大概是 % 操作的 50 倍左右。所以 JDK 为了性能， 而使用这种巧妙的算法， 在确保元素均匀分布的同时， 还保证了效率。

4：get方法

ConcurrentHashMap的get操作的流程很简单，可以分为三个步骤来描述

1、计算hash值，定位到该table索引位置，如果是首节点符合就返回

2、如果遇到扩容的时候，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回

3、以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null

3：CopyOnWriteArrayList

1：实现原理

CopyOnWrite 思想：是平时查询的时候，都不需要加锁，随便访问，只有在更新的时候，才会从原来的数据复制一个副本出来，然后修改这个副本，最后把原数据替换成当前的副本。修改操作的同时，读操作不会被阻塞，而是继续读取旧的数据。这点要跟读写锁区分一下。

collections/CopyOnWriteArrayListDemo.java

package collections.copyonwrite;
import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;
/*** 描述：     对比两个迭代器*/
public class CopyOnWriteArrayListDemo {public static void main(String[] args) throws InterruptedException {CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>(new Integer[]{1, 2, 3});System.out.println(list);Iterator<Integer> itr1 = list.iterator();list.remove(2);Thread.sleep(1000);System.out.println(list);Iterator<Integer> itr2 = list.iterator();itr1.forEachRemaining(System.out::println);itr2.forEachRemaining(System.out::println);}
}

2：优缺点

1：优点

对于一些读多写少的数据，写入时复制的做法就很不错，例如配置、黑名单、物流地址等变化非常少的数据，这是一种无锁的实现。可以帮我们实现程序更高的并发。

CopyOnWriteArrayList 并发安全且性能比 Vector 好。Vector 是增删改查方法都加了synchronized 来保证同步，但是每个方法执行的时候都要去获得锁，性能就会大大下降，而 CopyOnWriteArrayList 只是在增删改上加锁，但是读不加锁，在读方面的性能就好于 Vector。

2：缺点

数据一致性问题。这种实现只是保证数据的最终一致性，在添加到拷贝数据而还没进行替换的时候，读到的仍然是旧数据。

内存占用问题。如果对象比较大，频繁地进行替换会消耗内存，从而引发 Java 的 GC 问题，这个时候，我们应该考虑其他的容器，例如 ConcurrentHashMap。

4：并发队列

1：为什么要用队列

使用队列可以在线程间传递数据：生产消费者模式，银行转账。

队列中的读写等线程安全问题由队列负责处理。

2：常用并发队列

3：阻塞队列

阻塞队列的一端是给生产者放数据用，另一端给消费者拿数据用。阻塞队列是线程安全的，所以生产者和消费者都可以是多线程的。

take()方法获取并移除队列的头结点，一旦执行take时，队列里无数据则阻塞，直到队列里有数据。

put()方法是插入元素，但是如何队列已满，则无法继续插入，则阻塞，直到队列中有空闲空间。

是否有界（容量多大），这是非常重要的属性，无界队列Integer.MAX_VALUE，认为是无限容量。

4：ArrayBlockingQueue

有界，可以指定容量

公平：可以指定是否需要保证公平，如果想要保证公平，则等待最长时间的线程会被优先处理，不过会带来一定的性能损耗。

场景：有10个面试者，只有1个面试官，大厅有3个位子让面试者休息，每个人面试时间10秒，模拟所有人面试的场景。

collections/ArrayBlockingQueueDemo

package collections.queue;import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;public class ArrayBlockingQueueDemo {public static void main(String[] args) {ArrayBlockingQueue<String> queue = new ArrayBlockingQueue<String>(3);Interviewer r1 = new Interviewer(queue);Consumer r2 = new Consumer(queue);new Thread(r1).start();new Thread(r2).start();}
}class Interviewer implements Runnable {BlockingQueue<String> queue;public Interviewer(BlockingQueue queue) {this.queue = queue;}@Overridepublic void run() {System.out.println("10个候选人都来啦");for (int i = 0; i < 10; i++) {String candidate = "Candidate" + i;try {queue.put(candidate);System.out.println("安排好了" + candidate);} catch (InterruptedException e) {e.printStackTrace();}}try {queue.put("stop");} catch (InterruptedException e) {e.printStackTrace();}}
}class Consumer implements Runnable {BlockingQueue<String> queue;public Consumer(BlockingQueue queue) {this.queue = queue;}@Overridepublic void run() {try {Thread.sleep(1000);} catch (InterruptedException e) {e.printStackTrace();}String msg;try {while(!(msg = queue.take()).equals("stop")){System.out.println(msg + "到了");}System.out.println("所有候选人都结束了");} catch (InterruptedException e) {e.printStackTrace();}}
}