多線程筆記（三）

1. 同步容器與併發容器

同步容器

通過synchronized關鍵字實現線程安全的容器；或通過Collections這個工具類的synchronizedXXX方法創建的容器，都稱為同步容器

例如Vector, Stack, Hashtable

Vector是list介面的線程安全實現

Stack是Vector的子類，是一個先進後出的棧，入棧和出棧都是同步的

Hashtable是Map介面的線程安全實現

併發容器

同步容器一次只能允許一個線程去使用，因此性能較差。

允許多線程同時使用容器，並能保證線程安全的容器都是併發容器。

併發容器有兩個介面，分別為ConcurrentMap和BlockingQueue

主要的實現

• CopyOnWrite容器
  • CopyOnWriteArrayList
  • CopyOnWriteArraySet
• ConcurrentMap的實現類
  • ConcurrentHashMap
  • ConcurrentSkipListMap（支持排序）
• 阻塞隊列的實現
  • ArrayBlockingQueue：使用數組實現的有界阻塞隊列
  • LinkedBlockingQueue：使用鏈表實現的有界阻塞隊列
  • PriorityBlockingQueue：支持優先順序的無界阻塞隊列
  • DelayQueue：支持延時獲取元素的無界阻塞隊列
  • SyncronousQueue：不存儲元素的阻塞隊列
  • LinkedTransferQueue：使用鏈表實現的無界阻塞隊列
  • LinkedBlockingDeque：使用鏈表實現的雙向阻塞隊列
• 非阻塞隊列的實現：
  • ConcurrentLinkedQueue：使用鏈表實現的無界非阻塞隊列
  • ConcurrentLinkedDeque：使用鏈表實現的雙向非阻塞隊列

2. CopyOnWriteArrayList

CopyOnWriteArrayList是一個允許多線程使用，能夠保證線程安全，底層使用數組實現的併發容器。

基本設計思想：

​ 內部還是使用數組來存放數據，CopyOnWrite指的是寫時複製，一個數組在讀的時候使用原數組，寫的時候，假如添加一個元素進來，先copy原來的數組，添加一個元素的位置，然後把新的元素放進來。這時記憶體裡面同時存在兩個數組，原數組支持讀請求，新數組支持讀請求。同時將指向原數組的變數改為指向新數組。

缺點：

​ 每次寫的時候，都去cpoy一份數據出來，如果數據比較大的話，比較耗費記憶體

​ 只能保證數據最終一致，不能保證實時一致，當數據在修改的時候，讀取到的數據是”舊“的值。

適用場景：讀多寫少，對實時性要求不是特別高。

3. ConcurrentHashMap

概述

ConcurrentHashMap是一個實現Map功能的併發容器，也可以認為是一個線程安全的HashMap

不同JDK版本裡面的實現機制不一樣的。JDK1.8之前是數組加鏈表，JDK1.8及其之後是數組加鏈表/紅黑樹。

ConcurrentHashMap繼承了AbstractMap，實現了ConcurrentMap介面

AbstractMap實現了Map介面，提供了Map介面的骨幹實現，如果我們自己想要實現一個Map，可以繼承AbstractMap，這樣可以最大限度的減少自己實現Map這類數據結構所需要的工作量。

ConcurrentMap主要提供了一些針對Map的原子操作

內部結構

使用Node<K, V>[]（Node類型的數組）來存放數據

Node節點類型

Node:

用來存放k-v數據的node，如果發生了哈希衝突，那麼就使用鏈表法解決

TreeBin：

它是一個指向紅黑樹的代理節點，用來存放數據，樹上的節點是TreeNode，TreeNode繼承了Node節點。TreeBin的作用是方便對紅黑樹的操作（左旋，右旋，刪除，平衡等等），TreeBin還包含了加鎖解鎖等操作。

ForwardingNode

是一種臨時節點，擴容的時候才會使用。不存儲數據。

ReservationNode

保留節點，給ConcurrentHashMap中的一些特殊方法使用，不存儲數據。只在computeIfAbsent和compute這兩個方法裡面使用。

擴容和數據遷移的思路

擴容：

1. 數組擴容：創建一個新數組，通常長度為原來的兩倍

2. 數據遷移：把舊的數組裡的數據拷貝到新的數組裡面

擴容部分大家可以看看這一篇 https://blog.csdn.net/zzu_seu/article/details/106698150

4. BlockingQueue

阻塞隊列（BlockingQueue）：在併發環境下，調用隊列的過程中，會根據情況去阻塞調用線程，實現這樣帶阻塞功能的隊列，就是阻塞隊列。

阻塞隊列是通過“鎖”?來實現的，主要用在生產者-消費者模式，用於線程間的數據交換和系統解耦。

阻塞隊列的作用：

• 如果線程向隊列插入元素，而這個時候隊列滿了，就會阻塞這個線程，直到隊列有空閑。
• 如果線程從隊列中獲取元素，而這個時候，隊列為空，就會阻塞這個線程，直到隊列裡面有數據

BlockingQueue介面中的一些方法

操作成功返回true， 如果操作失敗拋異常：add(E e), remove(Object o)

操作成功返回true，操作失敗返回false：offer(E e)

隊列滿了阻塞調用線程：put(E e), take()

阻塞+超時：offer(E e, long timeout, TimeUnit unit), poll(long timeout, TimeUnit unit)

阻塞隊列的特點：

• 不能包含null元素
• 實現這個介面的類都必須是線程安全的
• 可以限定容量大小

5. ArrayBlockingQueue

ArrayBlockingQueue是BlockingQueue介面的典型實現。

ArrayBlockingQueue是基於數組來實現的，有界的阻塞隊列

ArrayBlockingQueue特點：

• 隊列容量在創建的時候指定，之後不可更改
• 插入元素在隊尾，刪除元素在隊首
• 隊列滿了，對阻塞插入元素的線程，隊列為空，會阻塞刪除元素的線程
• 支持公平/非公平的冊羅，預設是非公平的
• 加的鎖是全局鎖，如果在處理出隊的時候，是處理不了入隊的，反之同理。在超高併發環境下，可能會有性能問題

6. LinkedBlockingQueue

LinkedBlockingQueue是BlockingQueue介面的典型實現。

LinkedBlockingQueue是基於鏈表實現的，一種近似有界阻塞隊列。

LinkedBlockingQueue特點：

• 與ArrayBlockingQueue的全局鎖不同的是，LinkedBlockingQueue有兩把鎖，一把是控制入隊的putLock，一把是控制出隊的takeLock。
• 與ArrayBlockingQueue初始必須指定隊列大小不同的是，其可以在初始化時指定隊列的容量，如果不指定，容量大小預設為Integer的最大值。
• 與ArrayBlockingQueue可以指定公平/非公平策略不同的是，LinkedBlockingQueue不可以指定公平/非公平策略。

7. ConcurrentLinkedQueue

ConcurrentLinkedQueue是Queue介面的實現

ConcurrentLinkedQueue是基於鏈表實現的，無界的非阻塞隊列

與阻塞隊列最大的不同是，該隊列不再基於“鎖”來保證隊列的併發安全性，而是通過自旋+CAS的方式來保證