线程不安全的HashMap
多线程环境下，使用HashMap进行put操作会导致程序死循环，导致CPU利用率接近100%，所以再并发情况下不能使用HashMap。
引起死循环的原因是多线程会导致HashMap的Entry链表形成环形数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，就会产生死循环获取Entry.
效率低下的HashTable
HashTable使用synchronized来保证线程安全，意味着当一个线程访问HashTable的同步方法，其他线程也访问这同步方法时，会进入阻塞或轮询状态，所以竞争激烈效率低。
ConcurrentHashMap的锁分段技术可有效提升并发访问率
锁分段技术：首先将数据分成一段一段地存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。
ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成（JDK1.7）。
Segment是一种可重入锁(ReentrantLock)，在ConcurrentHashMap扮演锁的角色。它的结构和HashMap类似，是一种数组和链表结构。一个Segment里包含一个HashEntry数组。
HashEntry用键值对存储数据。
第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。
该结构的优劣势
坏处是这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长。
好处是写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment，这样，在最理想的情况下，ConcurrentHashMap可以最高同时支持Segment数量大小的写操作（刚好这些写操作都非常平均地分布在所有的Segment上）。 所以，通过这一种结构，ConcurrentHashMap的并发能力可以大大的提高。
ConcurrentHashMap的三种操作
get
public V get(Object key){ int hash = hash(key.hashcode()); return segmentFor(hash).get(key,hash); }get操作的高效在于整个get过程不需要加锁，除非读到的值是空才会加锁重读。原因是get方法里里将要使用的共享变量都定义为volatile类型，能在线程间保持可见性，能被多线程同时读，但只能被单线程写，在get方法里只需要读不需要写共享变量count和value，所以不用加锁。
transient volatile int count; volatile V value;put
put方法需要对共享变量进行写入操作，在操作共享变量时需要加锁。插入操作需要经历两个步骤：
是否需要扩容
在插入元素前会先判断Segment里的HashEntry数组是否超过容量，如果超过阈值，则对数组进行扩容。
如何扩容
先创建一个容量是原来容量的两倍的数组，然后将原数组里的元素进行再散列后插入到新的数组里。为了高效，ConcurrentHashMap不会对整个容器进行扩容，而是对某个Segment扩容。
size
ConcurrentHashMap先尝试2次通过不锁住Segment的方式来统计各个Segment的大小，如果统计过程中，容器的count发生了变化，则在采用加锁的方式统计所有Segment的大小。这样做的母的是为了提高效率。
JDK8中ConcurrentHashMap参考了JDK8 HashMap的实现，采用了数组+链表+红黑树。
在JDK7的基础上改造了三点：
取消分段锁机制，进一步降低冲突概率。
引入红黑树结构，同一个哈希槽上的元素个数超过一定阈值后，单向链表改为红黑树结构
使用了更加优化的方式统计集合内的元素数量。
具体优化表现在：在put、resize、size方法中设计元素总数的更新和计算都避免了锁，使用CAS代替。
get方法同样不需要同步，put操作时如果没有出现哈希冲突，就使用CAS添加元素，佛欧泽使用synchronized加锁添加元素。
当某个槽内的元素大于8且table容量不小于64时，链表转为红黑树。当某个槽内的元素减少到6时，由红黑树重新转为链表。在转化过程中，使用同步代码块当前槽的首元素，防止其他线程对当前槽进行增删改操作，转化完成后利用CAS替换原有链表。由于TreeNode节点也存储了next引用，因此红黑树转为链表很简单，只需从first元素开始遍历所有节点，并把节点从TreeNode转为Node类型即可。当构造好新链表后同样用CAS替换红黑树。
在并发编程中需要使用线程安全的队列，实现这样的队列有两种方式：
使用阻塞算法——可以用一个锁(入队和出队用同一把锁)或两个锁(入队出队用不同的锁)非阻塞队列——使用循环CAS实现ConcurrentLinkedQueue是一个基于连接节点的无界线程安全队列，采用先进先出对节点进行排序。
结构由head节点和tail节点组成，是一张链表结构的队列
入队列就是将入队节点添加到队列的尾部。
将入队节点设置为当前队列尾节点的下一个节点
更新tail节点
出队列就是从队列里返回一个节点元素，并清空该节点对元素的引用。
**阻塞队列：**是一个支持两个附加操作的队列。
支持阻塞插入的方法：当队列满时，队列会阻塞插入元素的线程，直到队列不满。支持阻塞移除的方法：在队列为空时，获取队列的线程会等待队列变成非空。阻塞队列常用于生产者消费者的场景，阻塞队列就是生产者用来存放元素，消费者用来获取元素的容器。
插入和移除操作的4种处理方式
方法/处理方式抛出异常返回特殊值一直阻塞超时退出插入方法add(e)offer(e)put(e)offer(e,time,unit)移除方法remove()poll()take()poll(time,unit)检查方法element()peek()不可用不可用ArrayBlockingQueue：一个由数组结构组成的有界阻塞队列。按照FIFO原则对元素进行排序，默认情况下不保证线程公平的访问队列。
**LinkedBlockingQueue:**一个用链表实现的有界阻塞队列。按照FIFO原则对元素进行排序,默认和最大长度为Integer.MAX_VALUE.
**PriorityBlockingQueue:**一个支持优先级的无界阻塞队列。默认情况下元素采取自然的升序排列，可自定义类实现compareTo()方法来指定元素排序规则，或者初始化PriorityBlockingQueue时指定构造函数Comparator对元素进行排序。
**DelayQueue：**一个支持延时获取元素的无界阻塞队列。使用PriorityQueue实现。创建元素时可以指定多久才能从队列中获取当前元素，只有在延迟期满时才能从队列中提取元素。
**SynchronousQueue：**一个不存储元素的阻塞队列。每一个put操作必须等待一个take操作，否则不能继续添加元素。支持公平访问队列，默认采用非公平性策略访问队列。适用于传递性场景，吞吐量高。
**LinLinkedTransferDeque：**一个由链表结构组成的无界阻塞TransferQueue队列。相对于其他阻塞队列多了tryTransfer和transfer方法。
transfer：如果当前有消费者正在等待接收元素，可以把生产者传入的元素立即传输给消费者，否则将元素放在队列的尾节点并等到该元素被消费者消费才返回。tryTransfer：用来试探生产者传入的元素能否直接传给消费者，如果没有消费者等待接收元素则返回false，和transfer的区别是无论消费者是否消费都会立即返回。**LinLinkedBlockingDeque：**一个由链表组成的双向阻塞队列。可从队列的两端插入和移除元素，多线程同时入队时减少了竞争。
**使用通知模式实现。**就是当生产者往满的队列里添加元素时会阻塞住生产者，当消费者消费了一个队列中的元素后，会通知生产者当前队列可用。
是一个把大任务分割成若干个小任务，最终汇总每个小任务结果后得到最大任务结果的框架。
Fork就是把一个大任务切分为若干子任务并行的执行；
Join就是合并这些子任务的执行结果，最后得到最大任务结果。
工作窃取算法
指从某个线程从其他队列里窃取任务来执行。(有的线程先把自己的任务执行完，而其他线程里还有任务等待处理，执行完任务的线程不如去帮他们干活，则窃取他们的任务来执行。)
**优点：**充分利用线程运行并计算，减少了线程间的竞争。
[外链图片转存中…(img-BAniavlg-1602131963480)]
工作窃取算法
指从某个线程从其他队列里窃取任务来执行。(有的线程先把自己的任务执行完，而其他线程里还有任务等待处理，执行完任务的线程不如去帮他们干活，则窃取他们的任务来执行。)
**优点：**充分利用线程运行并计算，减少了线程间的竞争。
**缺点：**在某些情况下还是存在竞争，并且该算法消耗了更多的系统资源。
