1， java集合框架

collects interface.png

2, Iterable and Iterators

Iterator.png

Iterable.png

demo.png

3, 主要實(shí)現(xiàn)機(jī)制
3.1 數(shù)組：訪問快插入慢
Arrays are used in the Collections Framework as the backing structure for ArrayList, CopyOnWriteArrayList, EnumSet and EnumMap, and for many of the Queue and Deque implementations. They also form an important part of the mechanism for implementing hash tables.
3.2 鏈表：插入快查找慢
Linked lists are the primary backing structure used for the classes ConcurrentLinkedQueue, LinkedBlockingQueue, and LinkedList, and the new skip list collections ConcurrentSkipListSet and ConcurrentSkipListMap. They are also used in implementing HashSet and LinkedHashSet.
3.3 hash表：基于內(nèi)容查找比較快
Hash tables are the backing structure for many Set and Map implementations, including HashSet and LinkedHashSet together with the corresponding maps HashMap and LinkedHashMap, as well as WeakHashMap, IdentityHashMap and ConcurrentHashMap.
3.4 樹：有序結(jié)構(gòu)蛙吏，插入沒有鏈表快，查找沒有數(shù)組快
Trees are the backing structures for TreeSet and TreeMap. Priority heaps, used in the implementation of PriorityQueue and PriorityBlockingQueue, are treerelated structures.
4衩辟， 算法效率

算法效率.png

5绎晃， 并發(fā)
util.concurrent包下的集合比遺留的所有方法都加synchronized的集合吞吐量更高泊柬，因?yàn)殒i粒度更小椎镣。
并發(fā)實(shí)現(xiàn)機(jī)制：
5.1 copy on write
Classes that use copy-on-write store their values in an internal array, which is effectively immutable; any change to the value of the collection results in a new array being created to represent the new values. Synchronization is used by these
classes, though only briefly, during the creation of a new array; because read operations do not need to be synchronized, copy-on-write collections perform well in the situations for which they are designed—those in which reads greatly predominate over writes. Copy-on-write is used by the collection classes CopyOnWriteArrayList and CopyOnWriteArraySet.
5.2 compare-and-swap (CAS)
An algorithm based on CAS behaves differently: it makes a local copy of the variable and performs the calculation without getting exclusive access. Only when it is ready to update the variable does it call CAS, which in one atomic operation compares the variable’s value with its value at the start and, if they are the same, updates it with the new value. If they are not the same, the variable must have been modified by another thread; in this situation, the CAS thread can try the whole computation again using the new value, or give up, or—in some algorithms— continue, because the interference will have actually done its work for it! Collections using CAS include ConcurrentLinkedQueue and ConcurrentSkipListMap.
5.3 java.util.concurrent.locks.Lock
A Lock has the same basic behavior as classical synchronization, but a thread can also acquire it under special conditions: only if the lock is not currently held, or with a timeout, or if the thread is not interrupted. Unlike synchronized code, in which an
object lock is held while a code block or a method is executed, a Lock is held until its unlock method is called. Some of the collection classes in this group make use of these facilities to divide the collection into parts that can be separately locked, giving improved concurrency. For example, LinkedBlockingQueue has separate locks for the head and tail ends of the queue, so that elements can be added and removed in parallel. Other collections using these locks include ConcurrentHashMap and most of the implementations of BlockingQueue.

基于5.1和5.2實(shí)現(xiàn)的集合枚舉時(shí)不會(huì)拋出ConcurrentModificationException诈火∈蘖蓿基于5.3實(shí)現(xiàn)的集合使用fail-fast快速檢測并發(fā)修改并拋出ConcurrentModificationException。fail-fast的實(shí)現(xiàn)機(jī)制類似樂觀鎖冷守，每次修改版本號(hào)+1刀崖，如果枚舉時(shí)檢測到版本號(hào)變化，可以直接拋異常拍摇。

6亮钦，Collection

Collection.png

7，Set

Set.png

7.1 HashSet
實(shí)現(xiàn)機(jī)制：完全依賴內(nèi)部的HashMap的keySet實(shí)現(xiàn)
線程安全：線程不安全
適用范圍：通用
7.2 LinkedHashSet
實(shí)現(xiàn)機(jī)制：完全依賴內(nèi)部的LinkedHashMap的keySet實(shí)現(xiàn)充活，accessOrder默認(rèn)為false蜂莉，鏈表維護(hù)插入順序，枚舉時(shí)按插入順序返回混卵。
線程安全：線程不安全
適用范圍：需要保持插入順序時(shí)
7.3 CopyOnWriteArraySet
實(shí)現(xiàn)機(jī)制：完全依賴內(nèi)部的CopyOnWriteArrayList實(shí)現(xiàn)
線程安全：線程安全映穗。
適用范圍：適用于容量小且讀明顯比寫頻繁的情景。修改代價(jià)高幕随，所有元素復(fù)制一遍蚁滋。
7.4 EnumSet
實(shí)現(xiàn)機(jī)制：內(nèi)部根據(jù)枚舉類型枚舉值數(shù)量使用long或long數(shù)組存儲(chǔ)，bit位的位置對應(yīng)枚舉常量的聲明順序，1表示對應(yīng)的枚舉值存在辕录。
線程安全：線程不安全
適用范圍：只能存儲(chǔ)枚舉類型睦霎，且所有值屬于同一個(gè)枚舉類型。
7.5 SortedSet 和 NavigableSet

SortedSet.png

NavigableSet.png

查找最解決元素.png

7.5.1 TreeSet
實(shí)現(xiàn)機(jī)制：完全依賴內(nèi)部的TreeMap的keySet實(shí)現(xiàn)走诞。
線程安全：線程不安全
適用范圍：根據(jù)指定的Comparator或元素自然順序排序副女。
7.5.2 ConcurrentSkipListSet
實(shí)現(xiàn)機(jī)制：完全依賴內(nèi)部的ConcurrentSkipListMap的keySet實(shí)現(xiàn)。
線程安全：線程安全
適用范圍：元素有序速梗，并發(fā)吞吐量高肮塞。但是占用空間多，添加刪除要維護(hù)索引速度稍慢姻锁。
7.6 總結(jié)

性能.png

8枕赵， Queue

queue.png

add：加入隊(duì)列，有界隊(duì)列滿時(shí)拋出異常位隶。
offer：加入隊(duì)列拷窜，有界隊(duì)列滿時(shí)返回false。
element：取回但不刪除head涧黄，空隊(duì)列拋異常
removed：取回并刪除head篮昧，空隊(duì)列拋異常
peek：取回但不刪除head，空隊(duì)列返回null
poll：取回并刪除head笋妥，空隊(duì)列返回null

實(shí)現(xiàn)類.png

8.1 PriorityQueue
實(shí)現(xiàn)機(jī)制：基于優(yōu)先級(jí)堆(priority heaps)實(shí)現(xiàn)懊昨，按指定Comparator或自然順序排序。priority heaps是一顆滿足兩個(gè)條件的二叉樹：父節(jié)點(diǎn)大于兩個(gè)子節(jié)點(diǎn)春宣；除了葉子層酵颁，其他層次應(yīng)該是滿的，如果葉子層不滿月帝，全部靠左躏惋。

插入.png

刪除.png

狀態(tài).png

擴(kuò)容.png

插入-1.png

插入-2.png

刪除：

刪除-1.png

刪除-2.png

線程安全：線程不安全
適用范圍：無界般卑，線程不安全的優(yōu)先級(jí)隊(duì)列武鲁。
8.2 ConcurrentLinkedQueue
實(shí)現(xiàn)機(jī)制：無界隊(duì)列，按插入順序先進(jìn)先出蝠检，通過cas實(shí)現(xiàn)線程安全沐鼠，支持并發(fā)修改，所以枚舉和size等read操作不能返回精確結(jié)果叹谁。隊(duì)列以單鏈表存儲(chǔ)饲梭。
插入：

插入.png

刪除：

刪除.png

size.png

BlockingQueue.png

put：添加元素，如果隊(duì)列滿了茫死，一直等待跪但。
poll：取元素，如果隊(duì)列為空峦萎，等待直到超時(shí)
take：取元素屡久，如果隊(duì)列為空，一直等待骨杂。
加上從Queue繼承的方法：添加和取回都有4中方法涂身，空/滿時(shí)：拋異常雄卷；返回null/false搓蚪；阻塞直到超時(shí)；一直阻塞丁鹉。

method.png

狀態(tài).png

添加.png

刪除.png

線程安全：線程安全，生產(chǎn)和消費(fèi)使用不同的可重入鎖揣钦，并發(fā)度更好雳灾。

8.3.2 ArrayBlockingQueue：有界隊(duì)列
實(shí)現(xiàn)機(jī)制：利用可重入鎖的環(huán)形數(shù)組。

b圖為刪除時(shí).png

狀態(tài).png

插入：

插入-1.png

插入-2.png

刪除：

刪除-1.png

刪除-2.png

線程安全：線程安全冯凹，基于可重入鎖
適用范圍：

8.3.3 PriorityBlockingQueue
實(shí)現(xiàn)機(jī)制：線程安全版本的PriorityQueue谎亩，所有操作都使用可重入鎖。
線程安全：線程安全，基于可重入鎖匈庭。
8.3.4 DelayQueue：延遲隊(duì)列
實(shí)現(xiàn)機(jī)制：所有元素都實(shí)現(xiàn)Delayed接口夫凸，附加過期時(shí)間，所有元素按過期時(shí)間排序阱持，內(nèi)部依賴一個(gè)可重入鎖和一個(gè)PriorityQueue夭拌。
插入：

插入.png

刪除：

刪除.png

線程安全：線程安全，基于可重入鎖

8.4 Deque 雙向隊(duì)列

Deque.png

push/pop：插入和刪除都在head衷咽，就形成了stack結(jié)構(gòu)鸽扁。

8.4.1 ArrayDeque
實(shí)現(xiàn)機(jī)制：內(nèi)部使用環(huán)形數(shù)組結(jié)構(gòu)，首尾相遇時(shí)擴(kuò)容一倍镶骗。
線程安全：線程不安全

8.4.2 LinkedList：即實(shí)現(xiàn)Deque又實(shí)現(xiàn)List桶现，線程不安全。

8.4.3 ConcurrentLinkedDeque
實(shí)現(xiàn)機(jī)制：基于雙向鏈表存儲(chǔ)
線程安全：線程安全鼎姊，基于cas
插入：

插入.png

刪除：

刪除.png

8.5 BlockingDeque

BlockingDeque.png

8.5.1 LinkedBlockingDeque
實(shí)現(xiàn)機(jī)制：看名字就知道啦巩那。
線程安全：線程安全，生成和消費(fèi)各有一個(gè)可重入鎖此蜈。

8.6 算法效率總結(jié)

效率.png

9 List：基于索引讀寫

List.png

subList：只是返回一個(gè)視圖即横，返回的內(nèi)部類所有讀寫都委托給外部類。

實(shí)現(xiàn)類.png

9.1 ArrayList
實(shí)現(xiàn)機(jī)制：內(nèi)部基于數(shù)組存儲(chǔ)裆赵，簡單的數(shù)組操作
線程安全：線程不安全
擴(kuò)容：每次50%

擴(kuò)容.png

9.2 LinkedList
實(shí)現(xiàn)機(jī)制：基于雙鏈表存儲(chǔ)东囚，簡單的鏈表操作
線程安全：線程不安全

9.3 CopyOnWriteArrayList
實(shí)現(xiàn)機(jī)制：基于數(shù)組存儲(chǔ)，讀不加鎖战授，每次修改页藻，加鎖，產(chǎn)生新的數(shù)組植兰，復(fù)制元素份帐。
狀態(tài)：

狀態(tài).png

添加：

add.png

線程安全：線程安全，基于可重入鎖楣导。
適用范圍：集合元素少废境，且讀的頻率明顯高于寫。

9.4 Vector 和 Stack
實(shí)現(xiàn)機(jī)制：所有方法都加synchronized的ArrayList筒繁。
線程安全：線程安全噩凹，基于synchronized，吞吐量不如基于鎖的實(shí)現(xiàn)毡咏。
適用范圍：遺留集合驮宴，基本不用，Stack可以替換為LinkedBlockingDeque

9.5 性能比較

性能.png

10 Map：最復(fù)雜的結(jié)構(gòu)

map.png

實(shí)現(xiàn).png

10.1 HashMap
狀態(tài)：
transient Node<K,V>[] table：數(shù)組 + 單鏈表(單桶節(jié)點(diǎn)少于8)/紅黑樹(單桶節(jié)點(diǎn)大于8 樹中先按hash排序呕缭，hash相同的再按key排序)堵泽，每個(gè)元素根據(jù) hash(key) % size(table)分散到不同的hash桶修己。
transient int modCount：修改版本號(hào)，枚舉時(shí)快速檢測并發(fā)修改拋出異常迎罗。
threshold：size>size(table) * loadFactor時(shí)箩退，threshold和loadFactor都擴(kuò)大一倍。
loadFactor：hash表的hash桶使用率
紅黑樹的元素TreeNode一共有7個(gè)指針(＜亚４骼浴！)：
parent：樹形結(jié)構(gòu)父節(jié)點(diǎn)
left：左子樹
right：右子樹
parent钻蔑，left啥刻，right一起構(gòu)成紅黑樹結(jié)構(gòu)

next：指向雙鏈表的下一個(gè)節(jié)點(diǎn)
prev：指向雙鏈表的上一個(gè)節(jié)點(diǎn)
next，prev構(gòu)成雙鏈表咪笑，存儲(chǔ)紅黑樹的節(jié)點(diǎn)可帽，鏈表頭為紅黑樹的root節(jié)點(diǎn)

before：前一個(gè)
after：后一個(gè)
before，after構(gòu)成另一個(gè)雙鏈表窗怒，用于維護(hù)插入順序(默認(rèn))或訪問順序映跟。

添加元素：

put-1.png

put-2.png

刪除元素：

remove-1.png

remove-2.png

查找：

get.png

擴(kuò)容：

初始容量是滿足指定值的最小的2的指數(shù).png

resize.png

重新計(jì)算hash.png

10.2 LinkedHashMap
實(shí)現(xiàn)機(jī)制：繼承HashMap，元素繼承HashMap的Node扬虚，額外添加before努隙，after兩個(gè)指針，在HashMap單鏈表數(shù)組的基礎(chǔ)上額外維護(hù)一個(gè)所有元素的雙鏈表辜昵。

雙鏈表.png

雙鏈表根據(jù)構(gòu)造參數(shù)用于維護(hù)元素訪問順序或插入順序(默認(rèn))

當(dāng)維護(hù)元素訪問順序時(shí)荸镊，非常適合用于實(shí)現(xiàn)LRU緩存過期策略。

10.3 WeakHashMap
實(shí)現(xiàn)機(jī)制：HashMap的簡化版堪置，單桶元素過多時(shí)不會(huì)轉(zhuǎn)成紅黑樹躬存，所有的key都繼承WeakReference，key在WeakHashMap外部無強(qiáng)引用時(shí)舀锨，會(huì)被gc回收岭洲，在key被gc回收后進(jìn)入內(nèi)部的ReferenceQueue隊(duì)列。每次讀操作都會(huì)先清理key被gc回收的元素：

清理.png

10.4 IdentityHashMap
實(shí)現(xiàn)機(jī)制：以數(shù)組存儲(chǔ)坎匿，數(shù)組長度永遠(yuǎn)都是2的指數(shù)盾剩，偶數(shù)存儲(chǔ)key，+1為對應(yīng)值碑诉。key比較引用相等彪腔。
計(jì)算hash：內(nèi)存地址的低位

計(jì)算hash.png

添加：key比較引用相等

put.png

10.5 EnumMap
實(shí)現(xiàn)機(jī)制：key必須是枚舉值侥锦，內(nèi)部使用兩個(gè)數(shù)組存儲(chǔ)进栽，一個(gè)存儲(chǔ)所有key的枚舉值，一個(gè)存儲(chǔ)對應(yīng)的value恭垦。

10.6 SortedMap 和 NavigableMap

SortedMap.png

NavigableMap.png

10.6.1 TreeMap
實(shí)現(xiàn)機(jī)制：基于紅黑樹實(shí)現(xiàn)快毛，key按指定Comparator或自身排序格嗅。
先從簡單的2-3樹開始：
2-3樹：每個(gè)節(jié)點(diǎn)可以有1或2個(gè)元素，2個(gè)元素的節(jié)點(diǎn)可以有3個(gè)子節(jié)點(diǎn)唠帝。
搜索：

search.png

單元素節(jié)點(diǎn)變雙元素節(jié)點(diǎn)：

插入-1.png

插入-2.png

節(jié)點(diǎn)拆分.png

紅黑樹：基于2-3樹贴铜，2元素節(jié)點(diǎn)之間用紅線連接，所有紅線左傾瀑晒，把所有紅線拉平绍坝，所有葉子節(jié)點(diǎn)高度相同。插入單元素節(jié)點(diǎn)時(shí)苔悦，變成2元素節(jié)點(diǎn)轩褐，如果插入右子樹，紅線右傾玖详，需要左旋把介。插入2元素節(jié)點(diǎn)變成3元素節(jié)點(diǎn)時(shí)，根據(jù)插入位置蟋座，進(jìn)行合適的左右旋轉(zhuǎn)之后轉(zhuǎn)為兩條紅線的人字行拗踢，然后提升中間元素跟父節(jié)點(diǎn)合并，拆分其余元素為獨(dú)立節(jié)點(diǎn)向臀。

red-black.png

旋轉(zhuǎn)：

左旋.png

右旋.png

單元素節(jié)點(diǎn)變雙元素節(jié)點(diǎn)秒拔，如果是插入右子樹需要左旋

插入-1.png

雙元素節(jié)點(diǎn)變?nèi)毓?jié)點(diǎn)，一共分插入中間和插入兩端三種情況飒硅，最后結(jié)果都是提升中間節(jié)點(diǎn)跟父節(jié)點(diǎn)合并砂缩，拆分另外兩個(gè)節(jié)點(diǎn)：

插入-2.png

三元素節(jié)點(diǎn)提升中間節(jié)點(diǎn)到父節(jié)點(diǎn)，然后遞歸處理：

插入-3.png

10.7 ConcurrentMap：添加remove和replace等原子操作

ConcurrentMap.png

10.7.1 ConcurrentHashMap
實(shí)現(xiàn)機(jī)制：跟HashMap一樣的存儲(chǔ)結(jié)構(gòu)三娩，通過cas實(shí)現(xiàn)線程安全庵芭，每次修改hash桶時(shí)鎖定桶的第一個(gè)節(jié)點(diǎn)。讀操作不加鎖雀监。resize時(shí)不像HashMap那樣直接遷移整個(gè)hash表双吆，而是多個(gè)線程通過cas鎖定transferIndex每次遷移一個(gè)hash桶。
添加：

put.png

刪除：

刪除.png

resize-1.png

resize-2.png

查找.png

10.8 ConcurrentNavigableMap

ConcurrentNavigableMap.png

10.8.1 ConcurrentSkipListMap
實(shí)現(xiàn)機(jī)制：基于性能類似紅黑樹但更易實(shí)現(xiàn)的跳表会前。

跳表.png

存儲(chǔ)結(jié)構(gòu)：底層數(shù)據(jù)節(jié)點(diǎn)采用普通的單鏈表好乐。上層索引節(jié)點(diǎn)包含down和right兩個(gè)指針以及被索引的節(jié)點(diǎn)，每層索引的第一個(gè)節(jié)點(diǎn)記錄當(dāng)前層次瓦宜。
查找索引：

查找索引.png

插入.png

維護(hù)索引-1.png

維護(hù)索引-2.png

刪除：

刪除.png

查找：

查找.png

10.9 性能

性能.png

java集合框架幾乎所有重要集合及其實(shí)現(xiàn)機(jī)制分析完畢Ｎ低颉！临庇！