並發容器

• 2021 年 6 月 20 日
• 筆記

並發容器。

一、小知識

1. hash

就是把任意長度的輸入（又叫做預映射， pre-image），通過散列演算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。常用 HASH 函數：直接取余法、乘法取整法、平方取中法。

hash衝突的處理辦法。

1、開放定址法。
2、再散列法。
3、鏈地址法(拉鏈法)常用 hash 演算法的介紹（1. MD4 2. MD5 3. SHA-1）。

HashMap解決衝突的辦法：鏈地址法。

2. 位運算

• 位與 & (1&1=1 0&0=0 1&0=0)
• 位或 | (1|1=1 0|0=0 1|0=1)
• 位非 ~ (~1=0 ~0=1)
• 位異或 ^ (1^1=0 1^0=1 0^0=0)
• 有符號右移>>(若正數,高位補 0,負數,高位補 1)
• 有符號左移<<
• 無符號右移>>>(不論正負,高位均補 0)

有趣的取模性質：

取模 a % (2^n) 等價於 a & (2^n – 1)，所以在 map 里的數組個數一定是 2 的乘方數，計算 key 值在哪個元素中的時候，就用位運算來快速定位，例如 a % 4 等價於 a & (2^2 -1)，但是後者速度更快。

二、ConcurrentHashMap（並發版HashMap）

HashMap 在多執行緒並發擴容時容易造成死循環，為了彌補這個不足，所以需要使用ConcurrentHashMap 。

底層依然是哈希表，但在JAVA8中有了不小的改變，而JAVA7和JAVA8都是用的比較多的版本，因此經常會將這兩個版本的實現方式做一些比較（比如面試中。。）

三、HashTable

HashTable 容器使用 synchronized 來保證執行緒安全，但在執行緒競爭激烈的情況下 HashTable 的效率非常低下。因為當一個執行緒訪問 HashTable 的同步方法，其他執行緒也訪問 HashTable 的同步方法時，會進入阻塞或輪詢狀態。如執行緒 1 使用 put 進行元素添加，執行緒 2 不但不能使用 put 方法添加元素，也不能使用 get方法來獲取元素，所以競爭越激烈效率越低。

四、ConcurrentSkipList 系列

• ConcurrentSkipListMap 有序 Map （並發版TreeMap）
• ConcurrentSkipListSet 有序 Set （並發版TreeSet）

TreeMap 和 TreeSet 使用紅黑樹按照 key 的順序（自然順序、自定義順序）來使得鍵值對有序存儲，但是只能在單執行緒下安全使用；多執行緒下想要使鍵值對按照 key 的順序來存儲，則需要使用 ConcurrentSkipListMap 和 ConcurrentSkipListSet，分別用以代替 TreeMap 和 TreeSet，存入的數據按 key 排序。在實現上，ConcurrentSkipListSet 本質上就是 ConcurrentSkipListMap 。

什麼是跳錶

跳錶其實也是一種通過「空間來換取時間」的一個演算法，令鏈表的每個結點不僅記錄 next 結點位置，還可以按照 level 層級分別記錄後繼第 level 個結點。此法使用的就是「先大步查找確定範圍，再逐漸縮小迫近」的思想進行的查找。

比如：

比如我們想查找 50，首先和 20 比較，大於 20 之後，在和 40 進行比較，然後在和 70 進行比較，發現 70 大於 50，說明查找的點在 40 和 50 之間，從這個過程中，我們可以看出，查找的時候跳過了 30。

五、寫時複製容器

CopyOnWriteArrayList 和 CopyOnWriteArraySet。

CopyOnWrite 容器即寫時複製的容器。通俗的理解是當我們往一個容器添加元素的時候，不直接往當前容器添加，而是先將當前容器進行Copy，複製出一個新的容器，然後新的容器里添加元素，添加完元素之後，再將原容器的引用指向新的容器。

這樣做的好處是我們可以對 CopyOnWrite 容器進行並發的讀，而不需要加鎖，因為當前容器不會添加任何元素。所以 CopyOnWrite 容器也是一種讀寫分離的思想，讀和寫不同的容器。如果讀的時候有多個執行緒正在向 CopyOnWriteArrayList 添加數據，讀還是會讀到舊的數據，因為寫的時候不會鎖住舊的 CopyOnWriteArrayList。

寫時複製容器的問題：

• 性能問題：每次修改都創建一個新數組，然後複製所有內容，如果數組比較大，修改操作又比較頻繁，可以想像，性能是很低的，而且記憶體開銷會很大。
• 數據的一致性問題：CopyOnWrite 容器只能保證數據的最終一致性，不能保證數據的實時一致性。所以如果你希望寫入的的數據，馬上能讀到，不要使用 CopyOnWrite 容器。

使用 CopyOnWriteMap 需要注意兩件事情：

1、減少擴容開銷。根據實際需要，初始化 CopyOnWriteMap 的大小，避免寫時 CopyOnWriteMap 擴容的開銷。
2、使用批量添加。因為每次添加，容器每次都會進行複製，所以減少添加次數，可以減少容器的複製次數。

六、BlockingQueue（阻塞隊列）

1. 隊列

隊列是一種特殊的線性表，特殊之處在於它只允許在表的前端（front）進行刪除操作，而在表的後端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。

在隊列中插入一個隊列元素稱為入隊，從隊列中刪除一個隊列元素稱為出隊。因為隊列只允許在一端插入，在另一端刪除，所以只有最早進入隊列的元素才能最先從隊列中刪除，故隊列又稱為先進先出（FIFO—first in first out）線性表。

2. 什麼是阻塞隊列

1、支援阻塞的插入方法：意思是當隊列滿時，隊列會阻塞插入元素的執行緒，直到隊列不滿。
2、支援阻塞的移除方法：意思是在隊列為空時，獲取元素的執行緒會等待隊列變為非空。

為了解決生產消費能力不均衡的問題，便有了生產者和消費者模式。生產者和消費者模式是通過一個容器來解決生產者和消費者的強耦合問題。生產者和消費者彼此之間不直接通訊，而是通過阻塞隊列來進行通訊，所以生產者生產完數據之後不用等待消費者處理，直接扔給阻塞隊列，消費者不找生產者要數據，而是直接從阻塞隊列里取，阻塞隊列就相當於一個緩衝區，平衡了生產者和消費者的處理能力。

3. 常見阻塞隊列

• ArrayBlockingQueue：一個由數組結構組成的有界阻塞隊列
• LinkedBlockingQueue：一個由鏈表結構組成的有界阻塞隊列
• PriorityBlockingQueue：一個支援優先順序排序的無界阻塞隊列
• DelayQueue：一個使用優先順序隊列實現的無界阻塞隊列
• SynchronousQueue：一個不存儲元素的阻塞隊列
• LinkedTransferQueue：一個由鏈表結構組成的無界阻塞隊列
• LinkedBlockingDeque：一個由雙向鏈表結構組成的有界阻塞隊列

以上的阻塞隊列都實現了 BlockingQueue 介面，也都是執行緒安全的。

有界無界

• 有限隊列就是長度有限，滿了以後生產者會阻塞。
• 無界隊列就是裡面能放無數的東西而不會因為隊列長度限制被阻塞，當然空間限制來源於系統資源的限制，如果處理不及時，導致隊列越來越大越來越大，超出一定的限制致使記憶體超限，就會導致OOM。所以，無界隊列需要謹慎使用。

ArrayBlockingQueue

是一個用數組實現的有界阻塞隊列。此隊列按照先進先出（FIFO）的原則對元素進行排序。

LinkedBlockingQueue

是一個用鏈表實現的有界阻塞隊列。此隊列的默認和最大長度為 Integer.MAX_VALUE。此隊列按照先進先出的原則對元素進行排序。

ArrayBlockingQueue 和 LinkedBlockingQueue對比

1、隊列中鎖的實現不同。

• ArrayBlockingQueue 實現的隊列中的鎖是沒有分離的，即生產和消費用的是同一個鎖
• LinkedBlockingQueue 實現的隊列中的鎖是分離的，即生產用的是 putLock，消費是 takeLock

2、在生產或消費時操作不同。

• ArrayBlockingQueue 實現的隊列中在生產和消費的時候，是直接將枚舉對象插入或移除的。
• LinkedBlockingQueue 實現的隊列中在生產和消費的時候，需要把枚舉對象轉換為 Node 進行插入或移除，會影響性能。

3、隊列大小初始化方式不同。

• ArrayBlockingQueue 實現的隊列中必須指定隊列的大小。
• LinkedBlockingQueue 實現的隊列中可以不指定隊列的大小，但是默認是Integer.MAX_VALUE。

PriorityBlockingQueue

PriorityBlockingQueue 是一個支援優先順序的無界阻塞隊列。默認情況下元素採取自然順序升序排列，也可以自定義類實現 compareTo()方法來指定元素排序規則。

DelayQueue

是一個支援延時獲取元素的無界阻塞隊列。隊列使用 PriorityQueue 來實現。隊列中的元素必須實現 Delayed 介面，在創建元素時可以指定多久才能從隊列中，獲取當前元素。只有在延遲期滿時才能從隊列中提取元素，應用場景常有訂單到期，限時支付等，但是有更好的解決方案，比如Redis。

SynchronousQueue

是一個不存儲元素的阻塞隊列。每一個 put 操作必須等待一個 take 操作，否則不能繼續添加元素。

LinkedTransferQueue

多了 tryTransfer 和 transfer 方法。

1、transfer 方法

如果當前有消費者正在等待接收元素（消費者使用 take()方法或帶時間限制的 poll()方法時），transfer 方法可以把生產者傳入的元素立刻 transfer（傳輸）給消費者。如果沒有消費者在等待接收元素，transfer 方法會將元素存放在隊列的 tail 節點，並等到該元素被消費者消費了才返回。

2、tryTransfer 方法

tryTransfer 方法是用來試探生產者傳入的元素是否能直接傳給消費者。如果沒有消費者等待接收元素，則返回 false。和 transfer 方法的區別是 tryTransfer 方法無論消費者是否接收，方法立即返回，而 transfer 方法是必須等到消費者消費了才返回。

LinkedBlockingDeque

LinkedBlockingDeque 是一個由鏈表結構組成的雙向阻塞隊列。所謂雙向隊列指的是可以從隊列的兩端插入和移出元素。雙向隊列因為多了一個操作隊列的入口，在多執行緒同時入隊時，也就減少了一半的競爭。

多了 addFirst、addLast、offerFirst、offerLast、peekFirst 和 peekLast 等方法，以 First 單詞結尾的方法，表示插入、獲取（peek）或移除雙端隊列的第一個元素。

4. 阻塞隊列的原理

使用了等待通知模式實現。所謂通知模式，就是當生產者往滿的隊列里添加元素時會阻塞住生產者，當消費者消費了一個隊列中的元素後，會通知生產者當前隊列可用。

通過查看 JDK 源碼發現 ArrayBlockingQueue 使用了 Lock + Condition 來實現。

都讀到這裡了，來個 點贊、評論、關注、收藏 吧！

文章作者：IT王小二
首發地址：//www.itwxe.com/posts/818b85a1/
版權聲明：文章內容遵循 署名-非商業性使用-禁止演繹 4.0 國際 進行許可，轉載請在文章頁面明顯位置給出作者與原文鏈接。