ConcurrentHashMap
HashMap：线程不安全，并发时可能死循环：多线程put时如果同时扩容导致Entry链表形成回路，get时next永远不为空造成死循环；
HashTable：线程安全，但效率低下：因为每个方法都加了syncronzied，所有线程竞争同一把锁；
ConcrrenthashMap：线程安全且高效：使用锁分段技术，将数据一段一段存储，每一段一把锁；
ConcrrenthashMap由Segment(继承重入锁)数组和HashEntry数组组成，一个Segment即一把锁，数组最大长度65535，默认长度16；
ConcrrenthashMap插入和获取元素需要通过Hash算法定位到Segment，使用对元素hashcode再散列的方式减少哈希冲突，使元素均匀分布；
get方法实现：
先使用hashcode再hash定位到segment，在使用该hash定位到Segment中的HashEntry数组，从而获取到HashEntry，获取HashEntry中的value，如果不为空则直接返回，如果为空则加锁获取再返回，双重保障；
get方法没有加锁，所以比HashTable高效，没有加锁是因为对Segment中的共享变量（count、HashEntry[]）使用了volatile；
put方法实现：
先使用hashcode再hash定位到segment，再加锁（Lock不是syncronzied）操作，先判断是否需要扩容，再定位到元素位置再添加元素；
扩容：ConcrrenthashMap不会对整个扩容，而是对每个Segment的HashEntry扩容，扩容后会对整个数组元素再hash插入，保证均匀；
size方法实现：
虽然每个segment中都有volatile的count，但不能累加求和，因为volatile只能保证单个元素的原子性，在各个元素相加时可能已经加过的元素发生了改变；也不能加锁相加这样效率低；
当前实现：通过2次不锁的累加求和，通过modCount（修改一次加1）判断中间是否有改变，如果有则再通过对所有Segment加锁求和的方式；
ConcurrentLinkedQueue
是一个基于链表节点的无界线程安全队列，采用wait-free算法（CAS）实现；由head和tail（volatile）节点组成，每个节点Node由节点元素和下一个节点next引用组成，默认head=tail为空；
offer方法实现：
入队做2件事情：将入队节点设置为当前尾节点的下一节点；和更新尾节点；从源码角度看入队做了2件事情：定位出尾节点；使用CAS将入队节点设置为为节点的next节点，如不成功则重试；采用不加锁不阻塞的CAS（循环判断加重试）实现；
poll方法实现：
获取头结点，判断是否为空，若不为空则使用CAS将头结点设置为null并直接返回头节点元素；若不为空则重新获取头结点；
阻塞队列
提供阻塞插入和阻塞获取元素的方法，队列满时阻塞插入，队列空时阻塞获取；（如果是无界队列，插入不会被阻塞）
add、remove：满或空时抛出异常；offer、poll：返回true/false、元素本身/null；put、take：阻塞操作，同时提供超时的方法；
ArrayBlockingQueue：数组实现、有界队列、默认使用不公平可重入锁，new时需指定大小，按先进先出排序；
LinkedBlockingQueue：链表实现、有界队列、大小为整形最大值，按先进先出排序；
PriorityBlockingQueue：优先队列(数组)实现，无界队列，默认按自然序升序排序，可自定义Comparator排序规则；
DelayedQueue：优先队列实现的延迟队列，元素需继承Delay接口，元素的延迟时间到了才从获取方法返回，使用Lock加锁和等待；
SynchronousQueue：不存储元素的阻塞队列，put一个元素必须等待take元素后才能继续put，相当于传球手，性能优于Array和Linked队列；
LinkedTransferQueue：链表实现无界队列，多了transfer方法，条件满足时可以直接将元素由生产者传输给消费者而不存入tail节点；
LinkedBlockingQeque：链表实现双向阻塞队列，对了一个操作入口，理论上少了一半竞争；
实现原理：使用Lock的Condition实现，采用通知模式实现，队列满时阻塞生产，消费时通知生产；
Fork/Join
并行执行任务框架，Fork将任务拆成若干小任务，Join汇总小任务结果成大任务结果；
工作窃取算法：大任务超分成若干小任务，一个任务对应一个队列对应一个线程，干完活的线程帮助其他线程干活，帮助线程从双端队列尾部获取元素，被帮助线程从头部获取元素；可以充分利用多线程并行，减少竞争；
使用：创建任务继承ForkJoinTask或其子类，实现compute方法，拆分子任务（可能递归）或者直接执行任务，该任务要完成子任务的拆分、判断、执行和合并，创建ForkJoinPool来提交任务并获取结果；异常可使用提供的API获取；
fork方法实现：创建线程将任务加入队列并立即返回，创建一个工作线程来执行任务；
join方法实现：阻塞当前线程并等待获取结果；
网友评论