转载

Java并发 -- 并发容器

Java 1.5之前提供的 同步容器 虽然也能保证 线程安全 ，但 性能很差
Java中的容器主要分为四大类，分别为List、Map、Set和Queue，并不是所有的Java容器都是线程安全的
将 非线程安全 的容器变成 线程安全 的容器的简单方案： synchronized
- 把非线程安全的容器封装在对象内部，然后控制好 访问路径 即可

线程安全的ArrayList

public class SafeArrayList<T> {
    private List<T> list = new ArrayList<>();

    public synchronized T get(int idx) {
        return list.get(idx);
    }

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

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

Collections.synchronized

Collections.synchronizedList(new ArrayList());
Collections.synchronizedSet(new HashSet());
Collections.synchronizedMap(new HashMap());

组合操作存在竟态条件问题

上面的addIfNotExist就包含 组合操作
组合操作往往隐藏着 竟态条件问题 ，即便每个操作都能保证原子性，也不能保证组合操作的原子性
用迭代器遍历同步容器也存在竟态条件问题，因为 组合操作不具备原子性

// 存在竟态条件问题
List<Object> list = Collections.synchronizedList(new ArrayList<>());
Iterator<Object> iterator = list.iterator();
while (iterator.hasNext()) {
    process(iterator.next());
}

// 并发安全，先锁住list再执行遍历操作
List<Object> list = Collections.synchronizedList(new ArrayList<>());
synchronized (list) {
    Iterator<Object> iterator = list.iterator();
    while (iterator.hasNext()) {
        process(iterator.next());
    }
}

并发容器

Java在1.5之前所谓的 线程安全 容器，主要指的是 同步容器
同步容器最大的问题是 性能差 ，所有方法都用 synchronized 来保证互斥， 串行度太高
在Java 1.5提供了性能更高的容器，称为 并发容器

分类

并发容器数量众多，但依旧可以分成四大类：List、Map、Set和Queue

List

List里面只有一个实现类就是 CopyOnWriteArrayList
CopyOnWrite即在执行 写操作 的时候会将共享变量 重新复制 一份出来，这样的好处是 读操作 是 完全无锁 的
CopyOnWriteArrayList内部维护一个数组，成员变量array指向这个内部数组，所有的读操作都是基于array进行的
如果在遍历array的同时，还有一个写操作
- 会将array复制一份，然后在新复制的数组上执行写操作，执行完之后再将array指向这个新的数组
因此读写是并行的，遍历操作一直都是基于原array执行的，而写操作则是基于新array执行的
应用场景：仅适用于 写操作非常少 的场景，而且能够容忍 读写的短暂不一致
CopyOnWriteArrayList的迭代器是只读的，不支持增删改，因为对快照进行增删改是没有意义的

Java并发 -- 并发容器

Map

Map接口的两个实现：ConcurrentHashMap和ConcurrentSkipListMap
ConcurrentHashMap的key是无序的，而ConcurrentSkipListMap的key是有序的
ConcurrentSkipListMap里面的SkipList本身是一种数据结构，翻译成跳表
- 跳表执行插入、删除和查询操作的平均复杂度为 O(log n)
- 理论上 与并发线程数无关 ，适用于 并发度非常高 的情况（ConcurrentHashMap的性能也不能满足要求）

集合类	Key	Value	线程安全
HashMap	允许为null	允许为null	否
TreeMap	不允许为null	允许为null	否
HashTable	不允许为null	不允许为null	是
ConcurrentHashMap	不允许为null	不允许为null	是
ConcurrentSkipListMap	不允许为null	不允许为null	是

Set

Set接口的两个实现：CopyOnWriteArraySet和ConcurrentSkipListSet
原理与CopyOnWriteArrayList和ConcurrentSkipListMap类似

Queue

JUC中的Queue类的并发容器是最复杂的，可以从两个维度分类， 阻塞/非阻塞 、 单端/双端
阻塞/非阻塞：阻塞指的是当队列已满时，入队操作阻塞；当队列已空时，出队操作阻塞
单端/双端：单端指的是只能队尾入队，队首出队；双端指的是队首队尾皆可出队入队
在JUC中，阻塞队列用 Blocking 关键字标识，单端队列用 Queue 标识，双端队列用 Qeque 标识

单端阻塞队列

其实现包括
- ArrayBlockingQueue
- LinkedBlockingQueue
- SynchronousQueue
- LinkedTransferQueue
- PriorityBlockingQueue
- DelayQueue
内部一般都会持有一个队列
- 该队列可以是数组（ArrayBlockingQueue）
- 也可以是链表（LinkedBlockingQueue）
- 甚至 不持有 队列（SynchronousQueue）， 生产者线程的入队操作必须等待消费者线程都出队操作
LinkedTransferQueue融合了LinkedBlockingQueue和SynchronousQueue的功能，性能比LinkedBlockingQueue更好
PriorityBlockingQueue支持按 优先级 出队
DelayQueue支持延时队列