導(dǎo)讀：Map竟然不屬于Java集合框架的子集笤昨？隊(duì)列也和List一樣屬于集合的三大子集之一？更有隊(duì)列的正確使用姿勢(shì)，一起來看吧哨坪！
Java中的集合通常指的是Collection下的三個(gè)集合框架List、Set乍楚、Queue和Map集合当编，Map并不屬于Collection的子集，而是和它平行的頂級(jí)接口徒溪。Collection下的子集的關(guān)系如文章開頭圖片所示忿偷。
本文的重點(diǎn)將會(huì)圍繞： 集合的使用、性能臊泌、線程安全鲤桥、差異性、源碼解讀等幾個(gè)方面進(jìn)行介紹渠概。
本文涉及的知識(shí)點(diǎn)茶凳，分為兩部分：
第一部分，Collection所有子集：
- List => Vector播揪、ArrayList贮喧、LinkedList
- Set => HashSet、TreeSet
- Queue
第二部分猪狈，Map => Hashtable箱沦、HashMap、TreeMap雇庙、ConcurrentHashMap谓形。
一、List
我們先來看List疆前、Vector寒跳、ArrayList、LinkedList竹椒，它們之間的繼承關(guān)系圖童太，如下圖：
可以看出Vector、ArrayList、LinkedList康愤，這三者都是實(shí)現(xiàn)集合框架中的List儡循，也就是所謂的有序集合，因此具體功能也比較近似征冷，比如都提供按照位置進(jìn)行定位择膝、添加或者刪除的操作，都提供迭代器以遍歷其內(nèi)容等检激。但因?yàn)榫唧w的設(shè)計(jì)區(qū)別肴捉，在行為、性能叔收、線程安全等方面齿穗，表現(xiàn)又有很大不同。
來看它們的主要方法饺律，如下圖：
常用方法：
- size 集合個(gè)數(shù)
- add()/add(int, E) 添加末尾/添加指定位置
- get(int) 獲取
- remove 刪除
- clear 清空
- ...
1.1 Vector
Vector是Java早期提供的 線程安全的動(dòng)態(tài)數(shù)組窃页， 如果不需要線程安全，并不建議選擇复濒，畢竟同步是有額外開銷的脖卖。Vector 內(nèi)部是使用對(duì)象數(shù)組來保存數(shù)據(jù)，可以根據(jù)需要自動(dòng)的增加容量巧颈，當(dāng)數(shù)組已滿時(shí)畦木，會(huì)創(chuàng)建新的數(shù)組，并拷貝原有數(shù)組數(shù)據(jù)砸泛。
看源代碼可以知道十籍，我們Vector是通過 synchronized 實(shí)現(xiàn)線程安全的：
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
Vector動(dòng)態(tài)增加容量，源碼查看：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
capacityIncrement變量是what唇礁？答案如下：
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
Vector動(dòng)態(tài)增加容量總結(jié)： 由上面的源碼可知勾栗，如果初始化Vector的時(shí)候指定了動(dòng)態(tài)容量擴(kuò)展大小，就增加指定的動(dòng)態(tài)大小垒迂，如果未指定械姻，則擴(kuò)展一倍的容量妒蛇。
1.2 ArrayList
ArrayList 是應(yīng)用更加廣泛的<strong>動(dòng)態(tài)數(shù)組</strong>机断，它本身不是線程安全的，所以性能要好很多绣夺。
ArrayList的使用與Vector類似吏奸，但有著不同的動(dòng)態(tài)擴(kuò)容機(jī)制，如下源碼：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
其中“>> 1”是位運(yùn)算相當(dāng)于除2陶耍，所有ArrayList擴(kuò)容是動(dòng)態(tài)擴(kuò)展50%.
1.3 LinkedList
LinkedList 顧名思義是 Java 提供的<strong>雙向鏈表</strong>奋蔚，所以它不需要像上面兩種那樣調(diào)整容量，它也不是線程安全的，它包含一個(gè)非常重要的內(nèi)部類：Entry泊碑。Entry是雙向鏈表節(jié)點(diǎn)所對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)坤按，它包括的屬性有：當(dāng)前節(jié)點(diǎn)所包含的值，上一個(gè)節(jié)點(diǎn)馒过，下一個(gè)節(jié)點(diǎn)臭脓。
1.4 Vector、ArrayList腹忽、LinkedList區(qū)別
Vector来累、ArrayList、LinkedList的區(qū)別窘奏，可以從以下幾個(gè)維度進(jìn)行對(duì)比：
1.4.1 底層實(shí)現(xiàn)的區(qū)別
Vector嘹锁、ArrayList 內(nèi)部使用數(shù)組進(jìn)行實(shí)現(xiàn)，LinkedList 內(nèi)部使用雙向鏈表實(shí)現(xiàn)着裹。
1.4.2 讀寫性能方面的區(qū)別
ArrayList 對(duì)元素 非末位 的增加和刪除都會(huì)引起內(nèi)存分配空間的動(dòng)態(tài)變化领猾，因此非末位的操作速度較慢，但檢索速度很快骇扇。
LinkedList 基于鏈表方式存放數(shù)據(jù)瘤运，增加和刪除元素的速度較快，但是檢索速度較慢匠题。
1.4.3 線程安全方面的區(qū)別
Vector 使用了synchronized 修飾了操作方法是線程安全的拯坟，而 ArrayList、LinkedList 是非線程安全的韭山。
如果需要使用線程安全的List可以使用CopyOnWriteArrayList類郁季。
二、Map
Hashtable钱磅、HashMap梦裂、TreeMap 都是最常見的一些 Map 實(shí)現(xiàn)，是以<strong>鍵值對(duì)</strong>的形式存儲(chǔ)和操作數(shù)據(jù)的容器類型盖淡。
它們之間的關(guān)系年柠，如下圖：
- Hashtable 是早期 Java 類庫提供的一個(gè)<a >哈希表</a>實(shí)現(xiàn)，本身是同步的褪迟，不支持 null 鍵和值冗恨，由于同步導(dǎo)致的性能開銷，所以已經(jīng)很少被推薦使用味赃。
- HashMap 是應(yīng)用更加廣泛的哈希表實(shí)現(xiàn)掀抹，行為上大致上與 HashTable 一致，主要區(qū)別在于 HashMap 不是同步的心俗，支持 null 鍵和值等傲武。通常情況下蓉驹，HashMap 進(jìn)行 put 或者 get 操作，可以達(dá)到常數(shù)時(shí)間的性能揪利，所以<strong>它是絕大部分利用鍵值對(duì)存取場(chǎng)景的首選</strong>态兴，比如，實(shí)現(xiàn)一個(gè)用戶 ID 和用戶信息對(duì)應(yīng)的運(yùn)行時(shí)存儲(chǔ)結(jié)構(gòu)疟位。
- TreeMap 則是基于紅黑樹的一種提供順序訪問的 Map诗茎，和 HashMap 不同，它的 get献汗、put敢订、remove 之類操作都是 O（log(n)）的時(shí)間復(fù)雜度，具體順序可以由指定的 Comparator 來決定罢吃，或者根據(jù)鍵的自然順序來判斷楚午。
HashMap 的性能表現(xiàn)非常依賴于哈希碼的有效性，請(qǐng)務(wù)必掌握 hashCode 和 equals 的一些基本約定尿招，比如：
- equals 相等矾柜，hashCode 一定要相等；
- 重寫了 equals 也要重寫 hashCode就谜；
- hashCode 需要保持一致性怪蔑，狀態(tài)改變返回的哈希值仍然要一致；
- equals 的對(duì)稱丧荐、反射缆瓣、傳遞等特性；
線程安全： Hashtable是線程安全的虹统，HashMap和TreeMap是非線程安全的弓坞。HashMap可以使用ConcurrentHashMap來保證線程安全。
三车荔、Set
Set有兩個(gè)比較常用的子集：HashSet渡冻、TreeSet.
HashSet內(nèi)部使用的是HashMap實(shí)現(xiàn)的，看源代碼可知：
public HashSet() {
map = new HashMap<>();
}
HashSet也并不是線程安全的忧便，HashSet用于存儲(chǔ)無序(存入和取出的順序不一定相同)元素族吻，值也不能重復(fù)。
HashSet可以去除重復(fù)的值珠增，如下代碼：
public static void main(String[] args) {
Set set = new HashSet();
set.add("orange");
set.add("apple");
set.add("banana");
set.add("grape");
set.add("banana");
System.out.println(set);
}
編譯器不會(huì)報(bào)錯(cuò)超歌，執(zhí)行的結(jié)果為：[orange, banana, apple, grape]，去掉了重復(fù)的“banana”選項(xiàng)切平。但排序是無序的握础，如果要實(shí)現(xiàn)有序的存儲(chǔ)就要使用TreeSet了辐董。
public static void main(String[] args) {
Set set = new TreeSet();
set.add("orange");
set.add("apple");
set.add("banana");
set.add("grape");
set.add("banana");
System.out.println(set);
}
輸出的結(jié)果是：[apple, banana, grape, orange]
同樣悴品，我們查看源碼發(fā)現(xiàn)，TreeSet的底層實(shí)現(xiàn)是TreeMap，源碼如下：
public TreeSet() {
this(new TreeMap<E,Object>());
}
TreeSet也是非線程安全的苔严。
四定枷、Queue
Queue（隊(duì)列）與棧是相對(duì)的一種數(shù)據(jù)結(jié)構(gòu)。只允許在一端進(jìn)行插入操作届氢，而在另一端進(jìn)行刪除操作的線性表欠窒。棧的特點(diǎn)是后進(jìn)先出，而隊(duì)列的特點(diǎn)是先進(jìn)先出退子。隊(duì)列的用處很大岖妄，但大多都是在其他的數(shù)據(jù)結(jié)構(gòu)中，比如寂祥，樹的按層遍歷荐虐，圖的廣度優(yōu)先搜索等都需要使用隊(duì)列做為輔助數(shù)據(jù)結(jié)構(gòu)。
Queue的直接子集丸凭，如下圖：
其中最常用的就是線程安全類：BlockingQueue.
4.1 Queue方法
- 添加：add(e) / offer(e)
- 移除：remove() / poll()
- 查找：element() / peek()
注意：
- 避免add()和remove()方法福扬，而是要使用offer()和poll()添加和移除元素。后者操作失敗不會(huì)報(bào)錯(cuò)惜犀，前者會(huì)拋出異常铛碑；
- element() / peek() 都為查詢第一個(gè)元素，不會(huì)刪除集合虽界，但element()查詢失敗會(huì)拋出異常汽烦，peek()不會(huì)。
4.2 Queue使用
Queue<String> queue = new LinkedList<String>();
queue.offer("a");
queue.offer("b");
queue.offer("c");
queue.offer("d");
System.out.println(queue);
queue.poll();
System.out.println(queue);
queue.poll();
queue.poll();
queue.poll();
System.out.println(queue.peek());
// System.out.println(queue.element()); // element 查詢失敗會(huì)拋出異常
System.out.println(queue);
4.3 其他隊(duì)列
ArrayBlockingQueue 底層是數(shù)組莉御，有界隊(duì)列刹缝，如果我們要使用生產(chǎn)者-消費(fèi)者模式，這是非常好的選擇颈将。
LinkedBlockingQueue 底層是鏈表梢夯，可以當(dāng)做無界和有界隊(duì)列來使用，所以大家不要以為它就是無界隊(duì)列晴圾。
SynchronousQueue 本身不帶有空間來存儲(chǔ)任何元素颂砸，使用上可以選擇公平模式和非公平模式。
PriorityBlockingQueue 是無界隊(duì)列死姚，基于數(shù)組人乓，數(shù)據(jù)結(jié)構(gòu)為二叉堆，數(shù)組第一個(gè)也是樹的根節(jié)點(diǎn)總是最小值都毒。
ArrayBlockingQueue ：一個(gè)由數(shù)組結(jié)構(gòu)組成的有界阻塞隊(duì)列色罚。
LinkedBlockingQueue ：一個(gè)由鏈表結(jié)構(gòu)組成的有界阻塞隊(duì)列。
PriorityBlockingQueue ：一個(gè)支持優(yōu)先級(jí)排序的無界阻塞隊(duì)列账劲。
DelayQueue：一個(gè)使用優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)的無界阻塞隊(duì)列戳护。
SynchronousQueue：一個(gè)不存儲(chǔ)元素的阻塞隊(duì)列金抡。
LinkedTransferQueue：一個(gè)由鏈表結(jié)構(gòu)組成的無界阻塞隊(duì)列。
LinkedBlockingDeque：一個(gè)由鏈表結(jié)構(gòu)組成的雙向阻塞隊(duì)列
五腌且、擴(kuò)展：String的線程安全
關(guān)于String梗肝、StringBuffer、StringBuilder的線程安全
String是典型的Immutable（不可變）類铺董，被聲明為final所有屬性也都是final巫击，所有它是不可變的，所有拼加精续、截取等動(dòng)作等會(huì)產(chǎn)生新的String對(duì)象坝锰。
StringBuffer是為了解決上面的問題，而誕生的重付，提供了append方法實(shí)現(xiàn)了對(duì)字符串的拼加什黑，append方法使用了synchronized實(shí)現(xiàn)了線程安全。
StringBuilder是JDK 1.5 新出的特性堪夭，作為StringBuffer的性能補(bǔ)充愕把，StringBuffer的append方法使用了synchronized實(shí)現(xiàn)了線程的安全，但同時(shí)也帶來了性能開銷森爽，在沒有線程安全的情況下可以優(yōu)先使用StringBuilder恨豁。
六、總結(jié)
List 也就是我們前面介紹最多的有序集合爬迟，它提供了方便的訪問橘蜜、插入、刪除等操作付呕。
Set 是不允許重復(fù)元素的计福，這是和 List 最明顯的區(qū)別，也就是不存在兩個(gè)對(duì)象 equals 返回 true徽职。我們?cè)谌粘ｉ_發(fā)中有很多需要保證元素唯一性的場(chǎng)合象颖。
Queue/Deque 則是 Java 提供的標(biāo)準(zhǔn)隊(duì)列結(jié)構(gòu)的實(shí)現(xiàn)，除了集合的基本功能姆钉，它還支持類似先入先出（FIFO说订， First-in-First-Out）或者后入先出（LIFO，Last-In-First-Out）等特定行為潮瓶。這里不包括 BlockingQueue陶冷，因?yàn)橥ǔＪ遣l(fā)編程場(chǎng)合，所以被放置在并發(fā)包里毯辅。
Map 是廣義 Java 集合框架中的另外一部分埂伦，Map 接口存儲(chǔ)一組鍵值對(duì)象，提供key（鍵）到value（值）的映射思恐。
七沾谜、參考資料
《碼出高效：Java開發(fā)手冊(cè)》
Java核心技術(shù)36講：http://t.cn/EwUJvWA
Oracle docs：https://docs.oracle.com/javase/tutorial/collections/interfaces/queue.html
