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。
网友评论