概述
java.util包中的大部分容器都是非線程安全的,若要在多線程中使用容器,你可以使用Collections提供的包裝函數:synchronizedXXX,將普通容器變成線程安全的容器。但該方法僅僅是簡單地給容器使用同步,效率很低。因此併發大師Doug Lea提供了java.util.concurrent包,提供高效的併發容器。並且為了保持與普通的容器的接口一致性,仍然使用util包的接口,從而易於使用、易於理解。PS:問題:synchronizedXXX究竟對容器做了什麼從而能達到線程安全的目的?
類圖
List和Set
![Java併發容器大合集](http://p2.ttnews.xyz/loading.gif)
JUC包中List接口的實現類:
- CopyOnWriteArrayListCopyOnWriteArrayList是線程安全的ArrayList
JUC包中Set接口的實現類:CopyOnWriteArraySet、
- ConcurrentSkipListSetCopyOnWriteArraySet是線程安全的Set,它內部包含了一個CopyOnWriteArrayList,因此本質上是由CopyOnWriteArrayList實現的。
- ConcurrentSkipListSet相當於線程安全的TreeSet。它是有序的Set。它由ConcurrentSkipListMap實現。
![Java併發容器大合集](http://p2.ttnews.xyz/loading.gif)
CopyOnWrite容器(寫時複製容器)
CopyOnWrite容器包括:CopyOnWriteArrayList和CopyOnWriteArraySet。
PS:CopyOnWriteArraySet有CopyOnWriteArrayList實現。
特性
- 適用於讀操作遠遠多於寫操作,並且數據量較小的情況。
- 修改容器的代價是昂貴的,因此建議批量增加addAll、批量刪除removeAll。
CopyOnWrite容器是如何實現線程安全的?
1.使用volatile修飾數組引用:確保數組引用的內存可見性。
2.對容器修改操作進行同步:從而確保同一時刻只能有一條線程修改容器(因為修改容器都會產生一個新的容器,增加同步可避免同一時刻複製生成多個容器,從而無法保證數組數據的一致性)
3.修改時複製容器:確保所有修改操作都作用在新數組上,原本的數組在創建過後就永不變化,從而其他線程可以放心地讀。
新增方法
CopyOnWriteArrayList:
<code>// 添加集合中不存在的元素
int addAllAbsent(Collection extends E> c)
// 該元素若不存在則添加
boolean addIfAbsent(E e)/<code>
CopyOnWriteArraySet:木有新增!
迭代
- CopyOnWriteArrayList擁有內部類:COWIterator,它是ListIterator的子類。
- 當調用iterator函數時返回的是COWIterator對象。
- COWIterator不允許修改容器,你若調用則會拋出UnsupportedOperationException。
優點
讀操作無需加鎖,從而高效。
缺點
- 數據一致性問題
- 由於迭代的是容器當前的快照,因此在迭代過程中容器發生的修改並不能實時被當前正在迭代的線程感知。
- 內存佔用問題
- 由於修改容器都會複製數組,從而當數組超大時修改容器效率很低。
- PS:因此寫時複製容器適合存儲小容量數據。
ConcurrentHashMap
java.util包中提供了線程安全的HashTable,但這傢伙只是通過簡單的同步來實現線程安全,因此效率低。只要有一條線程獲取了容器的鎖之後,其他所有的線程訪問同步函數都會被阻塞。因此同一時刻只能有一條線程訪問同步函數。而ConcurrentHashMap採用了分段鎖機制實現高效的併發訪問。
分段鎖原理
ConcurrentHashMap由多個Segment構成,每個Segment都包含一張哈希表。每次操作只將操作數據所屬的Segment鎖起來,從而避免將整個鎖住。
數據結構
ConcurrentHashMap內部包含了Segment數組,而每個Segment又繼承自ReentrantLock,因此它是一把可重入的鎖。Segment內部擁有一個HashEntry數組,它就是一張哈希表。HashEntry是單鏈表的一個節點,HashEntry數組存儲單鏈表的表頭節點。
新增API
<code>V putIfAbsent(K key, V value)/<code>
ConcurrentSkipListMap
- 它是一個有序的Map,相當於TreeMap。
- TreeMap採用紅黑樹實現排序,而ConcurrentHashMap採用跳錶實現有序。
跳錶的由來
作用:存儲有序序列,並且實現高效的查找與插入刪除。
存儲有序序列最簡單的辦法就是使用數組,從而查找可以採用二分搜索,但插入刪除需要移動元素較為低效。
因此出現了二叉搜索樹,用來解決插入刪除移動元素的問題。但二叉搜索樹在最壞情況下會退化成一條單鏈表,搜索的效率降為O(n)。
為了避免二叉搜索樹的退化,出現了二叉平衡樹,它在每次插入刪除節點後都會重新調整樹形,使得它仍然保持平衡,從而保證了搜索效率,也保證了插入刪除的效率。
此外,根據平衡算法的不同,二叉平衡樹又分為:B+樹、B-樹、紅黑樹。但平衡算法過於複雜,因此出現跳錶。
跳錶介紹
跳錶是條有序的單鏈表,它的每個節點都有多個指向後繼節點的引用。它有多個層次,上層都是下層的子集,從而能跳過不必要的節點,提升搜索速度。它通過空間來換取時間。
ConcurrentSkipListSet
- 它是一個有序的、線程安全的Set,相當於線程安全的TreeSet。
- 它內部擁有ConcurrentSkipListMap實例,本質上就是一個ConcurrentSkipListMap,只不過僅使用了Map中的key。
ArrayBlockingQueue
概要
- ArrayBlockingQueue是一個 數組實現的 線程安全的 有限 阻塞隊列。
新增API
<code>// 在隊尾添加指定元素,若隊已滿則等待指定時間boolean offer(E e, long timeout, TimeUnit unit)
// 獲取並刪除隊首元素,若隊為空則阻塞等待E take()// 添加指定元素,若隊已滿則一直等待void put(E e)// 獲取隊首元素,若隊為空,則等待指定時間E poll(long timeout, TimeUnit unit)/<code>
隊滿、隊空阻塞喚醒的原理隊滿阻塞:
- 當添加元素時,若隊滿,則調用notFull.await()阻塞當前線程;
- 當移除一個元素時調用notFull.signal()喚醒在notFull上等待的線程。
隊空阻塞:
- 當刪除元素時,若隊為空,則調用notEmpty.await()阻塞當前線程;
- 當隊首添加元素時,調用notEmpty.signal()喚醒在notEmpty上等待的線程。
LinkedBlockingQueue
概要
- LinkedBlockingQueue是一個 單鏈表實現的、線程安全的、無限 阻塞隊列。
隊滿隊空阻塞喚醒的原理
- 隊滿阻塞:若要插入元素,首先需要獲取putLock;在此基礎上,若此時隊滿,則調用notFull.await(),阻塞當前線程;當移除一個元素後調用notFull.signal()喚醒在notFull上等待的線程;最後,當插入操作完成後釋放putLock。
- 隊空阻塞:若要刪除/獲取元素,首先要獲取takeLock;在此基礎上,若隊為空,則調用notEmpty.await(),阻塞當前線程;當插入一個元素後調用notEmpty.signal()喚醒在notEmpty上等待的線程;最後,當刪除操作完成後釋放takeLock。PS:API和ArrayBlockingQueue一樣。
LinkedBlockingDeque
概要
- 它是一個 由雙向鏈表實現的、線程安全的、 雙端 無限 阻塞隊列。
數據結構
ConcurrentLinkedQueue概述
- 它是一個由單鏈表實現的、線程安全的、無限 隊列。
數據結構
特性
- head、tail、next、item均使用volatile修飾,保證其內存可見性,並未使用鎖,從而提高併發效率。
- PS:它究竟是怎樣在不使用鎖的情況下實現線程安全的?
JAVA進階架構程序員福利:我這裡還總結整理了比較全面的JAVA相關的面試資料,都已經整理成了
PDF版,這些都可以分享給大家,關注私信我:【806】,免費領取!
閱讀更多 欣然1013 的文章