1：ConcurrentHashMap的实现原理和使用

（1）先说一下HashMap?HashMap在并发执行put操作时会引起死循环，是以为多线程会导致它的Entry链表形成环形数据结构。一旦形成环形数据结构，Entry的next节点永远不为空。

HashTable：所有访问它的线程必须竞争同一把锁。

（2）ConcurrentHashMap使用锁分段技术。使用的锁为ReentrentLock.

（3）定位Segment：ConcurrentHashMap会使用Wang/Jenkins has的变种算法对元素的hasCode进行一次再散列。

（4）HashMap的初始化方法是通过initialCapacity,loadFactory和concurrentLevel等几个参数来初始化segment数组、段偏移量segmentShift、段掩码segmentMask和每个segment里的HashEntry数组来实现的。

（5）get操作：先经过一次再散列(使用key的hashCode)，然后使用这个散列值通过散列运算定位到Segment,在通过散列算法定位到元素。高效原因：整个过程不需要加锁。它的get方法将要使用的共享变量都定位成了valatile类型。如：用于统计当前Segement大小的count字段和用于存储值的HashEntry的value。由于使用了java的内存模型happen-before原则，能够保证validate字段的写入先于读。所以get操作使用能够读取到最新的值。

volatile替换锁的经典场景。

注意：定位segment使用的是元素的hashcode通过再散列后得到的值的高位，而定位HashEntry直接使用的是再散列后的值。

（6）put操作：第一步，判断是否需要对Segment里的HashEntry数组进行扩容；第二步，定位添加元素的位置，然后将其放在HashEntry数组里。

A: 怎么扩容？

创建一个容量是原来容量2倍的数组，然后将原数组里的元素进行再散列后插入到新的数组里。为了高效，只是对某个Segment进行扩容。

（7）size操作

ConcurrentHashMap的做法是先尝试2次通过不锁住Segment的方式来统计各个Segment大小。如果统计过程中，容器的count发生了变化，则采用加锁的方式来统计所有Segment的大小。

A：ConcurrentHashMap是如何判断在统计的时候容器是否发生变化呢？

使用modCount变量，在put、remove、clean方法里操作元素前都会将变量modeCount进行加1，那么在统计size前后比较modCount是否发生变化即可知道。

2：ConcurrentHashLinkedQueue

（1）类图

由head节点和tail节点组成。每个节点Node由节点元素item和指向下一个节点next的引用组成。默认情况下head节点存储的元素为空，tail节点等于head节点。

（2）入队实现原理：使用CAS算法来入队。入队过程干两件事：第一是定位出为尾节点；第二是使用CAS算法将入队节点设置成尾节点的next节点，如不成功则重试。tail节点不一定为尾节点。

注意：入队方法永远返回true，所以不要通过返回值判断入队是否成功。

（3）出队实现原理：

出队列就是从队列里返回一个节点元素，并清空该节点对元素的引用。

3：Java中的阻塞队列

（1）什么是阻塞队列？

BlockingQueue是一个支持两个附加操作的队列。

支持阻塞的插入方法：当队列满时，队列会阻塞插入元素的线程，直到队列不满。

支持阻塞的移除方法：在队列为空时，获取元素的线程会等待队列变为非空。

阻塞队列不可用时：插入和移除提供的4种处理方式。

注意：如果是无界阻塞队列，队列不可能会出现满的情况，所以使用put或offer方法永远不会被阻塞，而且使用offfer方法永远返回true.

（2）java里的阻塞队列

a: ArrayBlockingQueue:一个由数组结构组成的有界阻塞队列。默认情况下是不保证线程公平访问队列。构造函数new ArrayBlockingQueue(1000 , true),第二个参数为true，可以保证公平访问队列。底层实现方式为ReentrantLock.

b: LinkedBlockingQueue:一个由链表组成的有界阻塞队列。

c: PriorityBlockingQueue:一个支持优先级排序的无界阻塞队列。

d : DelayQueue:一个使用优先级队列实现的无界阻塞队列。

e : SynchronousQueue:一个不存储元素的阻塞队列。非常适合传递性场景，负责把生产者线程处理的数据直接传递给消费者线程。

f : LinkedTransferQueue:一个由链表结构组成的无界阻塞队列。其中的transfer方法可以把生产者传入的元素立刻传输给消费者。

g : LinkedBlockingDeque:一个由链表结构组成的双向阻塞队列。双向队列经典运用场景：工作窃取模式。

（3）阻塞队列的实现原理

如何设计阻塞队列？如何生产者和消费者进行高效的通信？（如果队列为空，消费者一直等待，当生产者添加元素时，消费者是如何知道当前队列里有元素呢？）

实现方式1：使用通知模式实现。即当生产者往满的队列里添加元素时会阻塞（例如：LockSupport.park(this)可以实现）住生产者，当消费者消费了一个队列中的元素后，会通知（例如：Condition可以实现）生产者当前队列可用。

4：Fork/Join框架

（1）工作原理

ForkJoinPool由ForkJoinTask数组和ForkJoinWorkerThread数组组成，ForkJoinTask数组负责将存放程序提交给ForkJoinPool的任务，而ForkJoinWorkerThread数组负责执行这些任务。

A：ForkJoinTask的fork方法实现原理

当调用ForkJoinTasks的fork方法时，程序会调用ForkJoinWorkThread的pushTask方法异步地执行这个任务，然后立即返回结果。

ForkJoinWorkThread的pushTask方法把当前任务存放在ForkJoinTask数组队列里。然后再调用ForkJoinPool的signalWork方法唤醒或创建一个工作线程来执行任务。

B：ForkJoinTask的join方法实现原理

join方法的主要作用是阻塞当前线程并等待获取结果。

（2）Fork/Join框架是Java7提供的一个用于并行执行任务的框架，是一个把大任务分割成若干个小任务，最终汇总每个小任务结果后得到大任务结果的框架。

（3）工作窃取算法（work-stealing）是指某个线程从其他队列里窃取任务来执行。

工作窃取的运行流程入下图所示：

通常做法：使用双端队列。被窃取任务的线程永远从双端队列的头部拿任务执行，而窃取任务的线程永远从双端队列的尾部拿任务执行。

优点：充分利用线程进行并行计算，减少线程间的竞争。

缺点：双端队列里只有一个任务时，还是存在竞争。该算法会消耗更多的系统资源，比如创建多个线程和多个双端队列。

（4）Fork/Join框架的核心：

a:  ForkJoinTask：首先创建一个ForkJoin任务。它提供在任务中执行fork和join操作的机制。通常继承它的2个子类：

RecursiveAction：用于没有返回结果的任务。

RecursiveTask：用于有返回结果的任务。

b:  ForkJoinPool：ForkJoinTask需要通过ForkJoinPool来执行。

任务分割出的子任务会添加到当前工作线程所维护的双端队列中，进入队列的头部。当一个工作线程的队列里暂时没有任务时，它会随机从其他工作线程的队列的尾部获取一个任务。

（5）Fork/Join框架的异常处理

提供isCompletedAbnormally方法来检查任务是否已经抛出异常或者已经被取消了。并且可以通过ForkJoinTask的getException方法获取异常，它返回Throwable对象，如果任务取消了则返回CancellationException。如果任务没有完成或者没有抛出异常则返回null。