Java併發 -- 併發容器

同步容器

1. Java 1.5之前提供的同步容器雖然也能保證線程安全，但性能很差
2. Java中的容器主要分為四大類，分別為List、Map、Set和Queue，並不是所有的Java容器都是線程安全的
3. 將非線程安全的容器變成線程安全的容器的簡單方案：synchronized把非線程安全的容器封裝在對象內部，然後控制好訪問路徑即可

線程安全的ArrayList

複製

<code>public class SafeArrayList {
    private List 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;
    }
}/<code>

Collections.synchronized

複製

<code>Collections.synchronizedList(new ArrayList());
Collections.synchronizedSet(new HashSet());
Collections.synchronizedMap(new HashMap());/<code>

組合操作存在竟態條件問題

1. 上面的addIfNotExist就包含組合操作
2. 組合操作往往隱藏著竟態條件問題，即便每個操作都能保證原子性，也不能保證組合操作的原子性
3. 用迭代器遍歷同步容器也存在竟態條件問題，因為組合操作不具備原子性

複製

<code>// 存在竟態條件問題
List list = Collections.synchronizedList(new ArrayList<>());
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
    process(iterator.next());
}

// 併發安全，先鎖住list再執行遍歷操作
List list = Collections.synchronizedList(new ArrayList<>());
synchronized (list) {
    Iterator iterator = list.iterator();
    while (iterator.hasNext()) {
        process(iterator.next());
    }
}/<code>

併發容器

1. Java在1.5之前所謂的線程安全容器，主要指的是同步容器
2. 同步容器最大的問題是性能差，所有方法都用synchronized來保證互斥，串行度太高
3. 在Java 1.5提供了性能更高的容器，稱為併發容器

分類

併發容器數量眾多，但依舊可以分成四大類：List、Map、Set和Queue

List

1. List裡面只有一個實現類就是CopyOnWriteArrayList
2. CopyOnWrite即在執行寫操作的時候會將共享變量重新複製一份出來，這樣的好處是讀操作是完全無鎖的
3. CopyOnWriteArrayList內部維護一個數組，成員變量array指向這個內部數組，所有的讀操作都是基於array進行的
4. 如果在遍歷array的同時，還有一個寫操作會將array複製一份，然後在新複製的數組上執行寫操作，執行完之後再將array指向這個新的數組
5. 因此讀寫是並行的， 遍歷操作一直都是基於原array執行的，而寫操作則是基於新array執行的
6. 應用場景：僅適用於寫操作非常少
   的場景，而且能夠容忍讀寫的短暫不一致
7. CopyOnWriteArrayList的迭代器是只讀的，不支持增刪改，因為對快照進行增刪改是沒有意義的

Map

1. Map接口的兩個實現：ConcurrentHashMap和ConcurrentSkipListMap
2. ConcurrentHashMap的key是無序的，而ConcurrentSkipListMap的key是有序的
3. ConcurrentSkipListMap裡面的SkipList本身是一種數據結構，翻譯成跳錶跳錶執行插入、刪除和查詢操作的平均複雜度為
   O(log n)理論上與併發線程數無關，適用於併發度非常高的情況（ConcurrentHashMap的性能也不能滿足要求）

集合類KeyValue線程安全HashMap允許為null允許為null否TreeMap不允許為null允許為null否HashTable不允許為null不允許為null是ConcurrentHashMap不允許為null不允許為null是ConcurrentSkipListMap不允許為null不允許為null是

Set

1. Set接口的兩個實現：CopyOnWriteArraySet和ConcurrentSkipListSet
2. 原理與CopyOnWriteArrayList和ConcurrentSkipListMap類似

Queue

1. JUC中的Queue類的併發容器是最複雜的，可以從兩個維度分類，阻塞/非阻塞、單端/雙端
2. 阻塞/非阻塞：阻塞指的是當隊列已滿時，入隊操作阻塞；當隊列已空時，出隊操作阻塞
3. 單端/雙端：單端指的是隻能隊尾入隊，隊首出隊；雙端指的是隊首隊尾皆可出隊入隊
4. 在JUC中，阻塞隊列用Blocking關鍵字標識，單端隊列用Queue標識，雙端隊列用Qeque標識

單端阻塞隊列

1. 其實現包括ArrayBlockingQueueLinkedBlockingQueueSynchronousQueueLinkedTransferQueuePriorityBlockingQueueDelayQueue
2. 內部一般都會持有一個隊列該隊列可以是數組（ArrayBlockingQueue）也可以是鏈表（LinkedBlockingQueue）甚至不持有隊列（SynchronousQueue），生產者線程的入隊操作必須等待消費者線程都出隊操作
3. LinkedTransferQueue融合了LinkedBlockingQueue和SynchronousQueue的功能，性能比LinkedBlockingQueue更好
4. PriorityBlockingQueue支持按優先級出隊
5. DelayQueue支持延時隊列

雙端阻塞隊列

其實現是LinkedBlockingDeque

單端非阻塞隊列

其實現是ConcurrentLinkedQueue

雙端非阻塞隊列

其實現是ConcurrentLinkedDeque

是否有界

1. 使用隊列時，要格外注意隊列是否支持有界
2. 實際工作中，一般不建議使用無界的隊列，因為有可能會導致OOM
3. 上面提到的Queue，只有ArrayBlockingQueue和LinkedBlockingQueue是支持有界的

來源：
http://zhongmingmao.me/2019/05/12/java-concurrent-concurrent-container/