线程安全的list+map
一、Vector和SynchronizedList
1.1回顾线程安全的Vector和SynchronizedList
我们知道ArrayList是用于替代Vector的，Vector是线程安全的容器。因为它几乎在每个方法声明处都加了synchronized关键字来使容器安全。
如果使用Collections.synchronizedList(new ArrayList())来使ArrayList变成是线程安全的话，也是几乎都是每个方法都加上synchronized关键字的，只不过它不是加在方法的声明处，而是方法的内部。
二、CopyOnWriteArrayList(Set)介绍
一般来说，我们会认为：CopyOnWriteArrayList是同步List的替代品，CopyOnWriteArraySet是同步Set的替代品。
无论是Hashtable-->ConcurrentHashMap，还是说Vector-->CopyOnWriteArrayList。JUC下支持并发的容器与老一代的线程安全类相比，总结起来就是加锁粒度的问题
Hashtable、Vector加锁的粒度大(直接在方法声明处使用synchronized)
ConcurrentHashMap、CopyOnWriteArrayList加锁粒度小(用各种的方式来实现线程安全，比如我们知道的ConcurrentHashMap用了cas锁、volatile等方式来实现线程安全..)
JUC下的线程安全容器在遍历的时候不会抛出ConcurrentModificationException异常
所以一般来说，我们都会使用JUC包下给我们提供的线程安全容器，而不是使用老一代的线程安全容器。
下面我们来看看CopyOnWriteArrayList是怎么实现的，为什么使用迭代器遍历的时候就不用额外加锁，也不会抛出ConcurrentModificationException异常。
2.1CopyOnWriteArrayList实现原理
我们还是先来回顾一下COW：
如果有多个调用者（callers）同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。优点是如果调用者没有修改该资源，就不会有副本（private copy）被建立，因此多个调用者只是读取操作时可以共享同一份资源。
参考自维基百科：zh.wikipedia.org/wiki/%E5%AF…
概括一下CopyOnWriteArrayList源码注释介绍了什么：
(1)0CopyOnWriteArrayList是线程安全容器(相对于ArrayList)，底层通过复制数组的方式来实现。
(2)CopyOnWriteArrayList在遍历的使用不会抛出ConcurrentModificationException异常，并且遍历的时候就不用额外加锁
(3)元素可以为null
2.1.1看一下CopyOnWriteArrayList基本的结构
看起来挺简单的，CopyOnWriteArrayList底层就是数组，加锁就交由ReentrantLock来完成。
2.1.2常见方法的实现
根据上面的分析我们知道如果遍历Vector/SynchronizedList是需要自己手动加锁的。
CopyOnWriteArrayList使用迭代器遍历时不需要显示加锁，看看add()、clear()、remove()与get()方法的实现可能就有点眉目了。
首先我们可以看看add()方法
通过代码我们可以知道：在添加的时候就上锁，并复制一个新数组，增加操作在新数组上完成，将array指向到新数组中，最后解锁。
再来看看size()方法：
再来看看get()方法：
那再来看看set()方法
了。
总结：
(1)在修改时，复制出一个新数组，修改的操作在新数组中完成，最后将新数组交由array变量指向。
(2)写加锁，读不加锁
2.1.3剖析为什么遍历时不用调用者显式加锁
常用的方法实现我们已经基本了解了，但还是不知道为啥能够在容器遍历的时候对其进行修改而不抛出异常。所以，来看一下他的迭代器吧：
到这里，我们应该就可以想明白了！CopyOnWriteArrayList在使用迭代器遍历的时候，操作的都是原数组！
2.1.4CopyOnWriteArrayList缺点
看了上面的实现源码，我们应该也大概能分析出CopyOnWriteArrayList的缺点了。
内存占用：如果CopyOnWriteArrayList经常要增删改里面的数据，经常要执行add()、set()、remove()的话，那是比较耗费内存的。
因为我们知道每次add()、set()、remove()这些增删改操作都要复制一个数组出来。
数据一致性：CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。
从上面的例子也可以看出来，比如线程A在迭代CopyOnWriteArrayList容器的数据。线程B在线程A迭代的间隙中将CopyOnWriteArrayList部分的数据修改了(已经调用setArray()了)。但是线程A迭代出来的是原有的数据。
2.1.5CopyOnWriteSet
CopyOnWriteArraySet的原理就是CopyOnWriteArrayList。
ConcurrentHashMap
数据结构
JDK 1.8中ConcurrentHashMap抛弃了分段锁技术的实现，直接采用CAS + synchronized保证并发更新的安全性，底层采用数组+链表+红黑树的存储结构。其包含核心静态内部类 Node。
首先通过一张图来看下数据结构吧：
数据结构图
说明：数据结构采用数组 + 链表 + 红黑树的方式实现。当链表中(bucket)的节点个数超过8个时，会转换成红黑树的数据结构存储，这样设计的目的是为了减少同一个链表冲突过大情况下的读取效率。
Java8中主要做了如下优化:
1.将Segment抛弃掉了，直接采用Node（继承自Map.Entry）作为table元素。
2.修改时，不再采用ReentrantLock加锁，直接用内置synchronized加锁，java8的内置锁比之前版本优化了很多，相较ReentrantLock，性能不并差。
3.size方法优化，增加了CounterCell内部类，用于并行计算每个bucket的元素数量。
内部类和继承关系
Java8中ConcurrentHashMap增加了很多内部类来支持一些操作和优化性能。下面介绍几个核心的内部类。
ConcurrentHashMap几个核心内部类关系图
（1）Node类：存放元素的key,value,hash值,next下一个链表节点的引用。用于bucket为链表时。
（2）TreeBin：内部属性有root，first节点，以及root节点的锁状态变量lockState，这是一个读写锁的状态。用于存放红黑树的root节点，并用读写锁lockState控制在写操作即将要调整树结构前，先让读线程完成读操作。从链表结构调整为红黑树时，table中索引下标存储的即为TreeBin。
（3）TreeNode：红黑树的节点，存放了父节点，左子节点，右子节点的引用，以及红黑节点标识。
（4）ForwardingNode：在调用transfer()方法期间，插入bucket头部的节点，主要用来标识在扩容时元素的移动状态，即是否在扩容时还有并发的插入节点，并保证该节点也能够移动到扩容后的表中。
（5）ReservationNode：占位节点，不存储任何信息，无实际用处，仅用于computeIfAbsent和compute方法中。
重要属性介绍
以上的一些属性，在初始化，扩容，链表转红黑树等方法中用到。属性众多，sizeCtl，counterCells都比较重要。
sizeCtl：即作为table初始化状态的标识，也用作扩容时的线程数标识，还用作初始和扩容后table的容量标识，用处很多，不同状态值代表的含义如下：
1、 -1：标识table正在初始化
2、- N：标识table正在进行扩容，并且有N - 1个线程一起在进行扩容
3、正数：初始化table的大小，如果值大于初始容量大小，则表示扩容后的table大小。
链接：https://juejin.im/post/5be23e6ef265da6135720d61 链接：https://www.jianshu.com/p/85d158455861
