第二部分：并发工具类20->并发容器：哪些坑要填

1.并发容器

容器4大类List,Map,Set,Queue
但不是所有的容器都是线程安全的

2.非线程安全的容器如何变为线程安全的容器

把非线程安全的容器封装在对象内部，控制好访问路径就可以了

3.ArrayList 变为线程安全的的列表

SafeArrayList

SafeArrayList<T>{
  //封装ArrayList
  List<T> c = new ArrayList<>();
  //控制访问路径
  synchronized
  T get(int idx){
    return c.get(idx);
  }

  synchronized
  void add(int idx, T t) {
    c.add(idx, t);
  }

  synchronized
  boolean addIfNotExist(T t){
    if(!c.contains(t)) {
      c.add(t);
      return true;
    }
    return false;
  }
}

4.所有非线程安全的类是不是都可以用这种包装方式来线程安全呢,同步容器

List list = Collections.synchronizedList(Lists.newArrayList());
Set set = Collections.synchronizedSet(Sets.newHashSet());
Map map = Collections.synchronizedMap(Maps.newHashMap());

5.组合操作需要注意竞态条件问题

即使每个操作都保证原子性，也不能吧奥正组合操作的原子性

6.用迭代器遍历容器

synchronized(list){
    Iterator i = list.iterator();
	while(i.hasNext()){
	    foo(i.next());
	}
}

7.java提供的同步容器还有Vector，Stack，Hashtable

这3个容器不是基于包装类实现的

8.并发容器注意事项

jdk1.5之前的同步容器，性能差，都用synchronized来保证互斥，串行度太高
jdk1.5之后提供了高性能更高的容器，并发容器

1. List
   CopyOnWriteArrayList，写的时候会将共享变量重新复制一份出来，读操作完全无锁
   原理是什么
   内部维护了一个数组,成员变量array指向内部数组,所有的读操作都是基于array进行,迭代遍历的也是数组
   

增加元素,怎么处理?将array复制一份,新复制的数组上执行添加元素操作,执行完之后,array指向新的数组

坑:读多写少的场景,可以容忍写的短暂不一致.写入的新元素不能立刻被遍历到.

2. Map
   ConcurrentHashMap和ConcurrentSkipListMap
   ConcurrentHashMap的key是无序的
   ConcurrentSkipListMap的key是有序的

key不能为null，否则抛出NullPointerException异常

ConcurrentSkipListMap里面的SkipList本身就是一种数据结构，中文一版称为跳表，时间复杂度O(log n),理论上和并发线程数没有关系

3. Set
   CopyOnWriteArraySet和ConcurrentSkipListSet

4. Queue
   阻塞，非阻塞

阻塞：当队列已满，入队操作阻塞，队列已空，出队操作阻塞；Blocking标识
单端，双端：单端只能是队尾入队，队首出队，Queue标识；双端队首对尾都可以入队出队，Deque标识；

4.1 单端阻塞队列
ArrayBlockQueue，LinkedBlockQueue，SynchronousQueue，LinkedTransferQueue，PriorityBlockingQueue和DelayQueue
内部队列，数组，甚至不持有队列
没有队列，生产线程的入队操作必须等待消费线程出队操作。

4.2 双端阻塞队列
LinkedBlockingDeque

4.3 单端非阻塞队列
ConcurrentLinkedQueue

4.4 双端非阻塞队列
ConcurrentLinkedDeque