Java并發(fā)JUC——并發(fā)容器

引言

容器是Java基礎類庫中使用頻率最高的一部分，Java集合包中提供了大量的容器類來幫助我們簡化開發(fā)，我前面的文章中對Java集合包中的關鍵容器進行過一個系列的分析，但這些集合類都是非線程安全的，即在多線程的環(huán)境下，都需要其他額外的手段來保證數(shù)據(jù)的正確性，最簡單的就是通過synchronized關鍵字將所有使用到非線程安全的容器代碼全部同步執(zhí)行。這種方式雖然可以達到線程安全的目的，但存在幾個明顯的問題：首先編碼上存在一定的復雜性，相關的代碼段都需要添加鎖。其次這種一刀切的做法在高并發(fā)情況下性能并不理想，基本相當于串行執(zhí)行。JDK1.5中為我們提供了一系列的并發(fā)容器，集中在java.util.concurrent包下，用來解決這兩個問題.

并發(fā)容器是解決并發(fā)情況下的容器線程安全問題的。給多線程環(huán)境準備一個線程安全的容器對象。
線程安全的容器對象：Vector, Hashtable。線程安全容器對象，都是使用 synchronized 方法實現(xiàn)的。而concurrent 包中的同步容器，大多數(shù)是使用系統(tǒng)底層技術實現(xiàn)的線程安全。類似 native。 Java8 中使用 CAS。

容器概覽

List簡介

有序(存和取順序一致)，有索引，可以存儲重復，還有一個共性特點就是都可以操作下標。

Arraylist
內(nèi)部是數(shù)組數(shù)據(jù)結(jié)構(gòu)，是不同步的。替代了Vector。查詢的速度快。

LinkedList
內(nèi)部是鏈表數(shù)據(jù)結(jié)構(gòu)，是不同步的。增刪元素的速度很快，查詢鏈表兩端的元素也很快。

Vector
內(nèi)部是數(shù)組數(shù)據(jù)結(jié)構(gòu)，是同步的。增刪，查詢都很慢！

Set簡介

無序(存和取順序不一致)，無索引，不可以存儲重復


HashSet
內(nèi)部數(shù)據(jù)結(jié)構(gòu)是哈希表 ，是不同步的。

LinkedHashSet
Set集合里面比較獨特的一個集合：具有HashSet的查詢速度，且內(nèi)部使用鏈表維護元素的存取順序，所以存取有序

TreeSet
內(nèi)部數(shù)據(jù)結(jié)構(gòu)是二叉樹，可以對Set集合中的元素進行排序。是不同步的。

Map簡介

  • HashMap
  • Hashtable
  • LinkedHashMap
  • TreeMap

  • Properties


Hashtable
內(nèi)部結(jié)構(gòu)是哈希表，是同步的。不允許null作為鍵，null作為值。

Properties
用來存儲鍵值對型的配置文件的信息，可以和IO技術相結(jié)合

HashMap
內(nèi)部結(jié)構(gòu)是哈希表，不是同步的。允許null作為鍵，null作為值。

LinkedHashMap
用鏈表實現(xiàn)來擴展HashMap，可以實現(xiàn)存取有序

TreeMap
內(nèi)部結(jié)構(gòu)是二叉樹，不是同步的。可以用繼承Comparable類重寫comparTo()或?qū)崿F(xiàn)Comparator接口重寫compare()來對Map集合中的鍵進行排序。要求Key是不可變對象。

并發(fā)容器概覽

  • ConcurrentHashMap：線程安全的HashMap
  • CopyOnWriteArrayList：線程安全的List
  • BlockingQueue：這是一個接口，表示阻塞隊列，非常適合用于作為數(shù)據(jù)共享的通道
  • ConcurrentLinkedQueue：高效的非阻塞并發(fā)隊列，由鏈表實現(xiàn)，可以看成一個線程安全的LinkedList
  • ConcurrentSkipListMap：是一個Map，使用跳表的數(shù)據(jù)結(jié)構(gòu)進行快速查找

古老和過時的同步容器

  • Vector和Hashtable：在方法上加上synchronized解決線程安全問題，并發(fā)性能低

HashMap和ArrayList

  • 雖然這兩個類不是線程安全的，但可以用Collections.synchronizedList(new ArrayList<E>())和Collections.synchronizedMap(new HashMap<k,v>())使之變成線程安全的
  • 由源碼可以得知，這種方式是在方法里面使用同步代碼塊的方式解決線程安全問題，本質(zhì)上與Vector和Hashtable解決并發(fā)問題一樣，并沒有性能上的提升

ConcurrentHashMap和CopyOnWriteArrayList

  • 取代同步的HashMap和同步的ArrayList(時代的巨輪滾滾向前)
  • 絕大多數(shù)情況下，ConcurrentHashMap和CopyOnWriteArrayList的性能都更好

ConcurrentHashMap

為什么HashMap是線程不安全的

  • 同時put碰撞導致數(shù)據(jù)丟失
  • 同時put擴容導致數(shù)據(jù)丟失
  • 死循環(huán)造成的CPU100%
    • HashMap在高并發(fā)下的死循環(huán)(僅在JDK7以前存在)
    • 原因在于在多個線程同時擴容的時候，會造成鏈表的死循環(huán)，詳解：https://coolshell.cn/articles/9606.html

HashMap特點

  • 非線程安全
  • 迭代時不允許修改內(nèi)容
  • 只讀的并發(fā)是安全的
  • 如果一定要把HashMap用在并發(fā)環(huán)境，那么使用Collections.synchronizedMap(new HashMap<k,v>())

JDK1.7ConcurrentHashMap

  • concurrenthashMap是采用一個叫做分段鎖的機制。
  • 它可以看作是一個二重hashMap，首先concurrentHashMap是一個segment數(shù)組，每個segment都是一個繼承了ReentrantLock的類，這樣就可以方便地在各個segment里面加鎖所以每次需要加鎖的操作鎖住的是一個Segment，這樣只要保證每個Segment是線程安全的，也就實現(xiàn)了全局的線程安全。
  • 這個最外面的Segment[]數(shù)組，是不可以擴容的，默認有16個Segments，所以最多支持16個線程并發(fā)寫(操作分別分布在不同的Segment上)，這個默認值可以在初始化的時候設置為其他值，一旦初始化之后，是不可以更改的。
  • 然后進到Segment內(nèi)部，會發(fā)現(xiàn)，每個Segment可以看作一個HashMap。也就是在一個Segment里面，有個HashEntry[]數(shù)組，然后這個數(shù)組是一個個桶，桶里面是單向鏈表。

JDK1.8ConcurrentHashMap

  • Java8 對 ConcurrentHashMap 進行了比較大的改動，可以參考 Java8 中 HashMap 相對于 Java7 HashMap 的改動，對于 ConcurrentHashMap，Java8 也引入了紅黑樹。
  • Java8 ConcurrentHashMap 源碼真心不簡單，最難的在于擴容，數(shù)據(jù)遷移操作不容易看懂。
  • 結(jié)構(gòu)上和 Java8 的 HashMap 基本上一樣，不過它要保證線程安全性，所以在源碼上確實要復雜一些。

ConcurrentHashMap從JDK1.7該為JDK1.8

數(shù)據(jù)結(jié)構(gòu)的改變帶來并發(fā)處理能力的提升

  • 1.7中并發(fā)能力受限于Segment的個數(shù)，1.8中每個Node都是獨立的

Hash碰撞

  • 1.8是直接采用數(shù)組+鏈表+紅黑樹來實現(xiàn)，時間復雜度在O(1)和O(n)之間，如果鏈表轉(zhuǎn)化為紅黑樹了，那么就是O(1)到O(nlogn)。
  • 在這里值得一提的是，ConcurrentHashMap會判斷tabAt(tab, i = (n - 1) & hash)是不是 null，是的話就直接采用CAS進行插入，而如果不為空的話，則是synchronized鎖住當前Node的首節(jié)點，這是因為當該Node不為空的時候，證明了此時出現(xiàn)了Hash碰撞，就會涉及到鏈表的尾節(jié)點新增或者紅黑樹的節(jié)點新增以及紅黑樹的平衡，這些操作自然都是非原子性的。
  • 從而導致無法使用CAS，當Node的當前下標為null的時候，由于只是涉及數(shù)組的新增，所以用CAS即可。

保證并發(fā)安全

  • ConcurrentHashMap在JDK1.8的時候?qū)ut()方法中的分段鎖Segment移除，轉(zhuǎn)而采用一種CAS鎖和synchronized來實現(xiàn)插入方法的線程安全。
  • 由于每一個Node的首節(jié)點都會被synchronized修飾，從而將一個元素的新增轉(zhuǎn)化為一個原子操作，同時Node的value和next都是由volatile關鍵字進行修飾，從而可以保證可見性。

為什么ConcurrentHashMap的鏈表長度超過8會轉(zhuǎn)為紅黑樹

  • 默認是鏈表結(jié)構(gòu)而不是紅黑樹，因為鏈表所占用的空間更少
  • 鏈表長度想要達到8很困難，概率只有千萬分之6，如果極端情況發(fā)生，那么可以保證在這種極端情況下的查詢效率

ConcurrentHashMap不正確的使用方式會導致線程安全問題的發(fā)生

/**
 * @Description: ConcurrentHashMap組合操作，并不保證線程安全
 */
public class ConcurrentHashMapDemo implements Runnable {

    public static ConcurrentHashMap<String,Integer> concurrentHashMap = new ConcurrentHashMap();

    public static void main(String[] args) throws InterruptedException {
        concurrentHashMap.put("小明",0);
        Thread thread1 = new Thread(new ConcurrentHashMapDemo());
        Thread thread2 = new Thread(new ConcurrentHashMapDemo());
        thread1.start();
        thread2.start();
        thread1.join();
        thread2.join();
        System.out.println(concurrentHashMap);
    }

    @Override
    public void run() {
        for (int i = 0; i < 1000; i++) {
            Integer score = concurrentHashMap.get("小明");
            int newScore = score + 1;
            concurrentHashMap.put("小明",newScore);
        }
    }
}

針對上面的正確使用方法

public class ConcurrentHashMapDemo implements Runnable {

    public static ConcurrentHashMap<String,Integer> concurrentHashMap = new ConcurrentHashMap();

    public static void main(String[] args) throws InterruptedException {
        concurrentHashMap.put("小明",0);
        Thread thread1 = new Thread(new ConcurrentHashMapDemo());
        Thread thread2 = new Thread(new ConcurrentHashMapDemo());
        thread1.start();
        thread2.start();
        thread1.join();
        thread2.join();
        System.out.println(concurrentHashMap);
    }

    @Override
    public void run() {
        for (int i = 0; i < 1000; i++) {
            while (true){
                Integer score = concurrentHashMap.get("小明");
                int newScore = score + 1;
                
                boolean replace = concurrentHashMap.replace("小明", score, newScore);
                if(replace){
                    break;
                }
            }
        }
    }
}

public V putIfAbsent(K key, V value)

  • 傳統(tǒng)的put方法，只要key存在，value值就會被覆蓋,注意put方法返回的是put之前的值，如果無put之前的值返回null
  • putIfAbsent方法，只有在key不存在或者key為null的時候，value值才會被覆蓋

CopyOnWriteArrayList

  • CopyOnWriteArrayList用于代替Vector和SynchronizedList，就和ConcurrentHashMap用于代替SynchronizedMap一樣
  • Vector和SynchronizedList的鎖的粒度太大，并發(fā)效率相對較低，并且迭代時無法編輯
  • Copy-On-Write并發(fā)容器還包括CopyOnWriteArraySet，用來替代同步Set

CopyOnWriteArrayList適用場景

  • 讀操作可以盡可能的快，而寫操作即使慢一些也沒有太大關系
  • 讀多寫少：黑名單，每日更新；監(jiān)聽器：迭代操作遠多于修改操作

CopyOnWriteArrayList讀寫規(guī)則

  • 回顧讀寫鎖：讀讀共享，其他都互斥(寫寫互斥、讀寫互斥)
  • 讀寫鎖規(guī)則的升級：讀取是完全不用加鎖的，并且更厲害的是，寫入也不會阻塞讀取操作，只有寫入和寫入之間需要進行同步等待

CopyOnWriteArrayList實現(xiàn)原理

寫入時復制（CopyOnWrite）思想
寫入時復制（CopyOnWrite，簡稱COW）思想是計算機程序設計領域中的一種優(yōu)化策略。其核心思想是，如果有多個調(diào)用者（Callers）同時要求相同的資源（如內(nèi)存或者是磁盤上的數(shù)據(jù)存儲），他們會共同獲取相同的指針指向相同的資源，直到某個調(diào)用者視圖修改資源內(nèi)容時，系統(tǒng)才會真正復制一份專用副本（private copy）給該調(diào)用者，而其他調(diào)用者所見到的最初的資源仍然保持不變。這過程對其他的調(diào)用者都是透明的（transparently）。此做法主要的優(yōu)點是如果調(diào)用者沒有修改資源，就不會有副本（private copy）被創(chuàng)建，因此多個調(diào)用者只是讀取操作時可以共享同一份資源。

CopyOnWriteArrayList這是一個ArrayList的線程安全的變體，其原理大概可以通俗的理解為:初始化的時候只有一個容器，很常一段時間，這個容器數(shù)據(jù)、數(shù)量等沒有發(fā)生變化的時候，大家(多個線程)，都是讀取(假設這段時間里只發(fā)生讀取的操作)同一個容器中的數(shù)據(jù)，所以這樣大家讀到的數(shù)據(jù)都是唯一、一致、安全的，但是后來有人往里面增加了一個數(shù)據(jù)，這個時候CopyOnWriteArrayList 底層實現(xiàn)添加的原理是先copy出一個容器(可以簡稱副本)，再往新的容器里添加這個新的數(shù)據(jù)，最后把新的容器的引用地址賦值給了之前那個舊的的容器地址，但是在添加這個數(shù)據(jù)的期間，其他線程如果要去讀取數(shù)據(jù)，仍然是讀取到舊的容器里的數(shù)據(jù)。

CopyOnWriteArrayList缺點

  • 數(shù)據(jù)一致性問題：CopyOnWrite容器只能保證數(shù)據(jù)的最終一致性，不能保證數(shù)據(jù)的實時一致性，所以如果你希望寫入的數(shù)據(jù)能馬上讀取到，那么請不要使用CopyOnWrite容器
  • 內(nèi)存占用問題：因為CopyOnWrite容器的寫是復制機制，所以在進行寫操作的時候，內(nèi)存里會同時駐扎兩個對象的內(nèi)存

并發(fā)隊列Queue

為什么要使用隊列

  • 用隊列可以在線程間傳遞數(shù)據(jù)：生產(chǎn)者消費者模式、銀行轉(zhuǎn)賬
  • 考慮鎖等線程安全問題的重任從“你”轉(zhuǎn)移到了“隊列上”

在并發(fā)隊列上JDK提供了兩套實現(xiàn)，

  • 一個是以ConcurrentLinkedQueue為代表的高性能隊列非阻塞，

  • 一個是以BlockingQueue接口為代表的阻塞隊列，無論哪種都繼承自Queue。


阻塞隊列與非阻塞隊

阻塞隊列與普通隊列的區(qū)別在于：
阻塞隊列：
當隊列是空的時，從隊列中獲取元素的操作將會被阻塞，試圖從空的阻塞隊列中獲取元素的線程將會被阻塞，直到其他的線程往空的隊列插入新的元素；
當隊列是滿時，往隊列里添加元素的操作會被阻塞。試圖往已滿的阻塞隊列中添加新元素的線程同樣也會被阻塞，直到其他的線程使隊列重新變得空閑起來，如從隊列中移除一個或者多個元素，或者完全清空隊列.

BlockingQueue

阻塞隊列（BlockingQueue）是一個支持兩個附加操作的隊列。這兩個附加的操作是：

  • 在隊列為空時，獲取元素的線程會等待隊列變?yōu)榉强铡?/li>
  • 當隊列滿時，存儲元素的線程會等待隊列可用。

在Java中，BlockingQueue的接口位于java.util.concurrent 包中(在Java5版本開始提供)，由上面介紹的阻塞隊列的特性可知，阻塞隊列是線程安全的。

  • 阻塞功能：最有特色的兩個帶有阻塞功能的方法是
  • take()：獲取并移除隊列的頭結(jié)點，一旦如果執(zhí)行take()的時候，隊列里無數(shù)據(jù)則阻塞，直到隊列里有數(shù)據(jù)
  • put()：插入元素，但是如果隊列已滿，那么就無法繼續(xù)插入，則阻塞，直到隊列里有了空閑空間
  • 是否有界(容量有多大)：這是一個非常重要的屬性，無界隊列意味著里面可以容納非常多(Integer.MAX_VALUE)
  • 阻塞隊列和線程池的關系：阻塞隊列是線程池的重要組成部分

BlockingQueue主要方法

  • put()、take()：最重要的方法，并且會阻塞住
  • add()、remove()、element()：
    • add：在添加元素的時候，若超出了隊列的長度會直接拋出異常
    • remove：若隊列為空，拋出NoSuchElementException異常
  • offer()、poll()、peek()：
    • offer：在添加元素時，如果發(fā)現(xiàn)隊列已滿無法添加的話，會直接返回false。
    • poll：若隊列為空，返回null。
ArrayBlockingQueue

ArrayBlockingQueue是一個有邊界的阻塞隊列，它的內(nèi)部實現(xiàn)是一個數(shù)組。有邊界的意思是它的容量是有限的，我們必須在其初始化的時候指定它的容量大小，容量大小一旦指定就不可改變。

  • 公平：還可以指定是否需要保證公平，如果想保證公平的話，那么等待了最長時間的線程會被優(yōu)先處理，不過這會同時帶來一定的性能損耗

ArrayBlockingQueue是以先進先出的方式存儲數(shù)據(jù)，最新插入的對象是尾部，最新移出的對象是頭部。

ArrayBlockingQueue<String> arrays = new ArrayBlockingQueue<String>(3);
arrays.offer("張三");
arrays.offer("李四");
arrays.offer("王五");
arrays.offer("666", 3, TimeUnit.SECONDS); // 隊列滿了，阻塞3秒后向下執(zhí)行
System.out.println(arrays.poll()); // 張三
System.out.println(arrays.poll()); // 李四
System.out.println(arrays.poll()); // 王五
System.out.println(arrays.poll(3, TimeUnit.SECONDS)); //隊列為空，阻塞3秒后結(jié)束

LinkedBlockingQueue

LinkedBlockingQueue阻塞隊列大小的配置是可選的，如果我們初始化時指定一個大小，它就是有邊界的，如果不指定，它就是無邊界的。說是無邊界，其實是采用了默認大小為Integer.MAX_VALUE的容量 。它的內(nèi)部實現(xiàn)是一個鏈表。

和ArrayBlockingQueue一樣，LinkedBlockingQueue 也是以先進先出的方式存儲數(shù)據(jù)，最新插入的對象是尾部，最新移出的對象是頭部。下面是一個初始化和使LinkedBlockingQueue的例子：

PriorityBlockingQueue（有界，快滿時自動擴容，看似無界）

  • PriorityBlockingQueue是一個沒有邊界的隊列，它的排序規(guī)則和 java.util.PriorityQueue一樣。需要注意，PriorityBlockingQueue中允許插入null對象。
  • 所有插入PriorityBlockingQueue的對象必須實現(xiàn) java.lang.Comparable接口，隊列優(yōu)先級的排序規(guī)則就是按照我們對這個接口的實現(xiàn)來定義的。
  • 另外，我們可以從PriorityBlockingQueue獲得一個迭代器Iterator，但這個迭代器并不保證按照優(yōu)先級順序進行迭代。

SynchronousQueue

  • SynchronousQueue沒有容量，是無緩沖等待隊列，是一個不存儲元素的阻塞隊列，會直接將任務交給消費者，必須等隊列中的添加元素被消費后才能繼續(xù)添加新的元素。
  • 擁有公平（FIFO）和非公平(LIFO)策略，非公平側(cè)羅會導致一些數(shù)據(jù)永遠無法被消費的情況？

  • 線程池使用SynchronousQueue阻塞隊列一般要求maximumPoolSizes為無界，避免線程拒絕執(zhí)行操作。


SynchronousQueue注意點
  • SynchronousQueue沒有peek等函數(shù)，因為peek的含義是取出頭結(jié)點，但是SynchronousQueue的容量為0，所以連頭結(jié)點都沒有，那么也就沒有peek方法，同理也沒有iterator相關方法
  • 是一個極好的用來直接傳遞的并發(fā)數(shù)據(jù)結(jié)構(gòu)
  • SynchronousQueue是線程池Executors.newCacheThreadPool()使用的阻塞隊列

DelayQueue

  • 延遲隊列，根據(jù)延遲時間排序
  • 元素需要實現(xiàn)Delayed接口，規(guī)定排序規(guī)則

ConcurrentLinkedQueue

ConcurrentLinkedQueue : 是一個適用于高并發(fā)場景下的隊列，通過無鎖的方式，實現(xiàn)
了高并發(fā)狀態(tài)下的高性能，通常ConcurrentLinkedQueue性能好于BlockingQueue.它
是一個基于鏈接節(jié)點的無界線程安全隊列，使用CAS非阻塞算法來實現(xiàn)線程安全(不具備阻塞功能)。該隊列的元素遵循先進先出的原則。頭是最先
加入的，尾是最近加入的，該隊列不允許null元素。

// 非阻塞式隊列，無界隊列
ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
q.offer("張三");
q.offer("李四");
q.offer("王五");
//從頭獲取元素,刪除該元素
System.out.println(q.poll());
//從頭獲取元素,不刪除該元素
System.out.println(q.peek());
//獲取總長度
System.out.println(q.size());

如何選擇合適的隊列

  • 邊界
  • 空間
  • 吞吐量

隊列匯總

  • ArrayDeque, （數(shù)組雙端隊列）
  • PriorityQueue, （優(yōu)先級隊列）
  • ConcurrentLinkedQueue, （基于鏈表的并發(fā)隊列）
  • DelayQueue, （延期阻塞隊列）（阻塞隊列實現(xiàn)了BlockingQueue接口）
  • ArrayBlockingQueue, 常用（基于數(shù)組的并發(fā)阻塞隊列）
  • LinkedBlockingQueue, 常用（基于鏈表的FIFO阻塞隊列）
  • LinkedBlockingDeque, （基于鏈表的FIFO雙端阻塞隊列）
  • PriorityBlockingQueue,常用 （帶優(yōu)先級的無界阻塞隊列，）
  • SynchronousQueue常用 （并發(fā)同步阻塞隊列）

參考：
https://www.cnblogs.com/wangshen31/p/10464488.html

http://itxm.cn/post/13192.html

https://blog.csdn.net/yb223731/article/details/89928207

https://www.cnblogs.com/myseries/p/10877420.html

https://www.cnblogs.com/codeobj/p/11667737.html

https://www.cnblogs.com/keiyoumi520/p/10800290.html

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內(nèi)容