Java集合
類庫關系圖
List
ArrayList：Object數組
-
CopyOnArrayList
CopyOnArrayList讀遠多于寫場景的ArrayList線程安全替代者。
Vector： Object數組
LinkedList： 雙向循環(huán)鏈表
Set
HashSet（無序，唯一）
-
LinkedHashSet
LinkedHashSet 繼承與 HashSet，并且其內部是通過 LinkedHashMap 來實現的。有點類似于我們之前說的LinkedHashMap 其內部是基于 Hashmap 實現一樣，不過還是有一點點區(qū)別的。
TreeSet（有序，唯一）
紅黑樹(自平衡的排序二叉樹。)
-
ConcurrentSkipListSet
TreeSet的線程安全替代者。
https://blog.csdn.net/sunxianghuang/article/details/52221913
并發(fā)場景使用跳躍表替代紅黑樹原因：
1.樹的增刪操作維持平衡時，涉及多個節(jié)點的轉換，并發(fā)場景只能鎖上整棵樹。
2.基于鏈表的跳躍表增刪操作可基于CAS實現粒度更小的加鎖。
Queue
boolean add(E e)
Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
E element()
Retrieves, but does not remove, the head of this queue.
boolean offer(E e)
Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.
E peek()
Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
E poll()
Retrieves and removes the head of this queue, or returns null if this queue is empty.
E remove()
Retrieves and removes the head of this queue.
關系圖
BlockingQueue
void put(E e)
Inserts the specified element into this queue, waiting if necessary for space to become available.
E take()
Retrieves and removes the head of this queue, waiting if necessary until an element becomes available.
-
ArrayBlockingQueue
基于數組的阻塞隊列實現，在其內部維護了一個定長數組，以便緩存隊列中的數據對象，由于ArrayBlockingQueue內部只有一個鎖對象（ReentrantLock），因此讀寫沒有實現分離，也就意味著生產消費不能完全并行。由于長度需要定義，因此也叫有界隊列。
-
LinkedBlockingQueue
基于鏈表的阻塞隊列實現，同ArrayBlockingQueue類似，其內部也維持著一個數據緩沖隊列（鏈表構成）。
LinkedBlockingQueue之所以較ArrayBlockingQueue更加高效的處理并發(fā)數據，是因為內部實現采用了2把鎖，也就是實現了入隊、出隊分別上鎖，即讀寫分離，從而生產者、消費者完全到達了并行。
無需定義長度，也叫無界隊列。當然不定義長度時，需要注意下生產者的速度和消費者的速度，因為默認情況下隊列長度是Integer.MAX_VALUE。
-
SynchronousQueue
一個沒有緩沖的隊列，生產者生產的數據會直接被消費者獲取到并消費。它是一個輕量級的阻塞隊列，因為不具備容量，在用法上，只能是一個線程阻塞著取元素，等待另一個線程往隊列里面放入一個元素，然后會被等待著的線程立即取走，其實就是實現了線程間的輕量級的單元素交換。
-
PriorityBlockingQueue
基于優(yōu)先級（二叉樹堆）的阻塞隊列（優(yōu)先級的判斷通過構造函數傳入的Compator對象決定，也就是傳入隊列中對象必須實現Comparable接口）。
在實現PriorityBlockingQueue時，內部控制線程同步的鎖采用的是公平鎖，也是一個無界的隊列。
通俗的來說，不是先進先出的隊列了，而是誰的優(yōu)先級低誰先出去。那么可以思考下，是否每次add/offer都會進行一次排序呢？我們是否需要按照優(yōu)先級進行全排序呢？實際上，可以大致看一看add/take方法，會了解到PriorityBlockingQueue的設計思想：在add時，并不進行排序處理，當進行take時，選擇優(yōu)先級最小的拿出來而已，這樣既避免了在add時花費時間排序，又在take時節(jié)省了時間，因為并沒有全排序，僅僅是挑選了一個優(yōu)先級低的元素而已。
-
DelayQueue
帶有延遲時間的Queue,其中的元素只有當指定的延遲時間到了，才能從隊列中獲取到該元素。隊列中的元素必須實現Delayed接口，沒有大小限制。本質上來說，是借助于PriorityBlockingQueue來實現的，以延遲時間作為優(yōu)先級。延遲隊列的應用場景很多，比如緩存超時的數據進行移除，任務超時處理，空閑連接的關閉等等。
Deque
ConcurrentLinkedQueue
一個適用于高并發(fā)場景下的隊列，通過無鎖的方式（CAS+volatile），實現了高并發(fā)下的高性能，通常ConcurrentLinkedQueue的性能好于BlockingQueue。
它是一個基于鏈接節(jié)點的無界線程安全隊列，遵循先進先出的原則，頭是最先加入的，尾是最近加入的，不允許加入null元素。
注意add()/offer()都是加入元素的方法，這里沒有區(qū)別；poll()/peek()是取出頭元素的方法，區(qū)別點在于poll會刪除元素，而peek不會。
要特別注意到由于它的非阻塞性，并不像其他普通集合那樣，獲取隊列的SIZE的方法并不是常量時間的花費，而是O（N）的，因此我們應該盡可能避免使用size()方法，可以考慮使用isEmpty()代替。
雖然使用到了CAS+VOLATILE的機制避免了鎖，但是我們要明白的是，這只是保證單個操作，如peek()的安全，但是多個操作如果想保證的話，需要使用鎖機制來達到同步的效果。
Map
HashMap
非線程安全
JDK1.8之前HashMap由數組+鏈表組成的，數組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8以后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間。
HashMap 的長度為什么是2的冪次方？
為了能讓 HashMap 存取高效，盡量較少碰撞，也就是要盡量把數據分配均勻，每個鏈表/紅黑樹長度大致相同。這個實現就是把數據存到哪個鏈表/紅黑樹中的算法。
這個算法應該如何設計呢？
我們首先可能會想到采用%取余的操作來實現。但是，重點來了：“取余(%)操作中如果除數是2的冪次則等價于與其除數減一的與(&)操作（也就是說 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二進制位操作 &，相對于%能夠提高運算效率，這就解釋了 HashMap 的長度為什么是2的冪次方。
-
LinkedHashMap
LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈式散列結構即由數組和鏈表或紅黑樹組成。另外，LinkedHashMap 在上面結構的基礎上，增加了一條雙向鏈表，使得上面的結構可以保持鍵值對的插入順序。同時通過對鏈表進行相應的操作，實現了訪問順序相關邏輯。
-
ConcurrentHashMap
HashMap的線程安全替代者。
底層數據接口和HashMap一致，1.7之前數組+鏈表，1.8之后數組+鏈表+紅黑樹。
實現線程安全的方式（重要）： ① 在JDK1.7的時候，ConcurrentHashMap（分段鎖） 對整個桶數組進行了分割分段(Segment)，每一把鎖只鎖容器其中一部分數據，多線程訪問容器里不同數據段的數據，就不會存在鎖競爭，提高并發(fā)訪問率。（默認分配16個Segment，比Hashtable效率提高16倍。） 到了 JDK1.8 的時候已經摒棄了Segment的概念，而是直接用 Node 數組+鏈表+紅黑樹的數據結構來實現，并發(fā)控制使用 synchronized 和 CAS 來操作。（JDK1.6以后 對 synchronized鎖做了很多優(yōu)化） 整個看起來就像是優(yōu)化過且線程安全的 HashMap，雖然在JDK1.8中還能看到 Segment 的數據結構，但是已經簡化了屬性，只是為了兼容舊版本；② Hashtable(同一把鎖) :使用 synchronized 來保證線程安全，效率非常低下。當一個線程訪問同步方法時，其他線程也訪問同步方法，可能會進入阻塞或輪詢狀態(tài)，如使用 put 添加元素，另一個線程不能使用 put 添加元素，也不能使用 get，競爭會越來越激烈效率越低。
HashTable
線程安全
數組+鏈表組成的，數組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的
TreeMap
紅黑樹（自平衡的排序二叉樹）
-
ConcurrentSkipListMap
TreeMap的線程安全替代者。
LinkedHashMap
在HashMap基礎上，引入了鏈表保存元素加入順序，方便實現基于最近訪問原則的淘汰機制（刪除鏈表尾）。
