本章將簡單介紹一下常用的集合類的特點，同時并不會深入源碼分析原理舍哄，本文目的僅僅在于對 Java 集合類有一個整體認識
關于 API宴凉，本文不涉及過多，建議直接查看 Java 官方文檔
https://docs.oracle.com/javase/9/docs/api/overview-summary.html
1. 容器概述
1.1 引入原因
Java 中表悬，數組用來保存一組對象弥锄，但是數組具有固定的尺寸。于是為了解決數組長度固定蟆沫，無法應對對象數量未知的情況籽暇，引入容器/集合類。
容器用途就是保存對象饭庞。
1.2 容器層級
容器有兩大山脈：Collection 和 Map戒悠，其層次關系大致如下。
先來個基礎的：
再來個復雜一點的：
其中：
- Collection 接口是集合類的根接口舟山，本身沒有實現類绸狐。
- Map 是容器的另一個根接口卤恳，與 Collection 相互獨立
- Iterator 是所有容器都實現的接口，用于遍歷容器中元素寒矿。
- 另外 Collections 和 Arrays 是 Object 的直接子類纬黎，其中包含了一系列關于 容器 和 數組 的靜態(tài)方法
1.3 類型安全
通過 泛型 指定參數類型，即指定這個容器實例可以保存的類型劫窒。通過使用泛型，可以在編譯期防止將錯誤類型的對象放置到容器中拆座。
保證 類型安全 僅僅是 Java 泛型的其中一個作用主巍。后續(xù)我們會學習更多關于 泛型的知識（劇透一下，很復雜）
舉個例子：
List<String> list = new ArrayList<String>();
//先不用管 List 和 ArrayList 是啥挪凑，就先當作是一個集合就好
//通過指定泛型為 String孕索，那么這個集合就是用來存放 String 類型的，放入其他類型的東西都會出錯躏碳。
2. Collection
Collection 是一個接口搞旭，它下面的 List，Set菇绵，Queue 同樣也都是接口肄渗。
一個獨立元素的序列，這些元素都服從一條或多條規(guī)則咬最。其中 List 必須按照插入的順序保存元素翎嫡；Set 不能有重復元素；Queue 按照排隊規(guī)則來確定對象的產生順序（通常與插入順序相同）
2.1 List
List 是一個接口永乌，它承諾可以將元素維護在特定的序列中惑申。List 接口在 Collection 的基礎上添加大量的方法，使得可以在 List 中間插入和移除元素翅雏。
- 有序
- 元素可重復
下面主要介紹 兩種 List ：ArrayList 和 LinkedList圈驼。
2.1.1 ArrayList
優(yōu)點在于隨機訪問元素快，但是在中間插入和移除比較慢
原因是 ArrayList 底層是用數組實現的望几，這也是為什么讀取時和數組效率相同绩脆，時間復雜度都是1.
2.1.2 LinkedList
優(yōu)點是善于在中間插入和移除元素，提供了優(yōu)化的順序訪問橄妆，相反缺點是隨機訪問較慢
原因是底層是使用鏈式存儲
同時衙伶，LinkedList 可以實現比 ArrayList 更多的功能特性：LinkedList 支持棧、隊列和雙端隊列害碾。
2.1.3 Stack
Stack（棧）通常指 “后進先出”（LIFO）的容器矢劲，最后一個壓入棧的元素，第一個彈出棧慌随。
可以想象為彈簧芬沉，最先放上彈簧的被放在最下面躺同，后放上去的在上面，每次彈出來一個時丸逸，上面的（后放的）先被彈出蹋艺。
Stack 是通過 LinkedList 實現的。
Stack 繼承自 Vector黄刚，而 Vector 已被棄用瓜晤。
2.2 Set
Set 也是一個集合帅韧，但是它不保存重復的元素。
Set 具有和 Collection 完全一樣的接口，因此沒有任何額外的功能医舆，實際上 Set 就是 Collection分预，只不過行為不同叮称。
繼承與多態(tài)思想的應用：表現不同的行為
下面簡單介紹兩個實現類：HashSet 和 TreeSet
2.2.1 HashSet
查詢速度塊酣藻。HashSet 使用了散列，散列的價值在于速度 -- 散列使得查詢更加快速
-
存儲無序
HashSet 底層使用散列函數
2.2.2 TreeSet
-
存儲有序
TreeSet 將元素存儲在紅黑樹中程储，因此存儲結果有序蹭沛。
2.2.3 LinkedHashSet
-
存儲有序
通過鏈表保存添加的順序
2.3 Queue
Queue （隊列）是典型的 先進先出 的容器，即從一端放入事物章鲤，從另一端取出摊灭，且元素放入容器的順序和取出的順序是相同的。
可以想象一個傳送帶败徊，先放上傳送帶的物品會首先到達斟或。
同時 Queue 中允許重復元素。
LinkedList 實現了 Queue 接口集嵌，因此 LinkedList 可以用作 Queue 的一種實現（將LinkedList 可以向上轉型為 Queue）萝挤。
相關方法介紹：
| 方法 | 作用 | 說明 |
|---|---|---|
| add、offer | 將元素插入隊尾 | 隊列容量已滿時<br />add 會拋出異常<br />offer會返回 false |
| element根欧、peek | 返回對頭元素（不刪除） | 隊列為空時<br />emelent 會拋出異常<br />peek會返回 null |
| remove怜珍、poll | 返回對頭元素，并將該元素從隊列移除 | 隊列為空時<br />remove 會拋出異常<br />poll 會返回 null |
2.3.1 PriorityQueue
先入先出描述的是下一個元素應該是等待時間最長的元素
PriorityQueue（優(yōu)先級隊列）描述的是下一個元素應該是優(yōu)先級最高的元素凤粗。
當我們在 PriorityQueue 上調用 offer() 插入元素的時候酥泛，這個元素會在隊列中自動被排序，默認情況是自然排序嫌拣。當然我們可以通過自定義 Comparator 來修改這個順序柔袁。
PriorityQueue 保證我們調用 peek、poll 等方法時异逐，返回的是隊列中優(yōu)先級最高的元素捶索。
3. Map
Map 就是一組成對的 “鍵值對” 對象，允許使用鍵來查找值灰瞻。Map 可以將對象映射到其他對象上腥例，在實際開發(fā)中使用非常廣辅甥。
主要方法介紹：
| 方法 | 用途 |
|---|---|
| put | 添加鍵值對元素 |
| get | 返回與鍵對應的值 |
| containsKey | 查詢是否包含某個鍵 |
| containsValue | 查詢是否包含某個值 |
| keySet | 返回鍵的 set |
| entrySet | 返回鍵值對的 set |
| values | 返回值的 collection |
3.1 HashMap
查詢速度很快
-
存儲無序
原因在于，底層使用了 散列函數
鍵可以是 null燎竖，鍵值不可重復（重復會覆蓋舊的）
3.2 TreeMap
-
按照比較結果的升序保存鍵
紅黑樹存儲
3.3 LinkedHashMap
按照插入順序保存鍵
-
保留了 HashMap 的查詢速度
底層使用了散列函數 璃弄，同時用一個鏈表保存插入順序。
4. 迭代器
4.1 概念
Java 中的迭代器（Iterator）：
- 是一個輕量級對象：創(chuàng)建代價小
- 工作是遍歷并選擇序列中的對象构回，不關注容器中元素的數量
- 只能單向移動
4.2 用處：
- 使用方法 iterator() 要求容器返回一個 Iterator夏块，此時 Iterator 將準備好返回第一個元素
- 使用 next() 獲得序列下一個元素
- 使用 hasNext() 檢查序列中是否還有元素
- 使用 remove() 將迭代器最近返回的元素刪除
4.3 ListIterator
ListIterator 是 Iterator 的子類型，只能用于各種 List 類的訪問纤掸。
ListIterator 可以雙向移動拨扶，它可以產生相對于迭代器在列表中指向的當前位置的前一個（previous()方法）和后一個元素的索引（next() 方法）。
4.4 Iterator 與 foreach
foreach 除了可以作用于數組茁肠，還可以應用于所有的 Collection 對象。這是因為 Collection 繼承了 Iterable 的接口缩举。該接口包含一個能夠產生 iterator 的 iterator() 對象垦梆，并且 Iterable 接口被 foreach 用來在序列中移動。
public class IterableClass implements Iterable<String> {
protected String[] words=("Hello Java").split(" ");
public Iterator<String> iterator(){
return new Iterator<String>(){
private int index=0;
public boolean hasNext() {
return index<words.length;
}
public String next() {
return words[index++];
}
public void remove() {
}
};
}
public static void main(String[] args){
for(String s : new iterableClass())
System.out.println(s + "");
}
}
//輸出：
//Hello Java
5. Collections 和 Arrays
Collections 和 Arrays 都是 Object 的直接子類仅孩，里面封裝了一系列關于集合和數組的靜態(tài)方法托猩。
部分方法如下：
-
Collections.addAll()：用于將一些列元素加入到 Collection
public static <T> boolean addAll(Collection<? super T> c, T... elements) -
Arrays.asList()：將數組（可變參數列表）寫入到一個列表，并將該列表返回
public static <T> List<T> asList(T... a)底層表示為數組辽慕，因此不能修改尺寸京腥。如果調用add() 或 delete()，有可能改變數組尺寸溅蛉，因此會報錯公浪。
Arrays.toString()：產生數組的可打印表示。
總結
Java 提供大量持有對象的方式：
- 數組是將數字和對象聯系起來船侧，它保存明確的對象欠气，查詢對象時候不需要對查詢結果進行轉換，它可以是多維的镜撩，可以保存基本類型的數據预柒，但是數組一旦生成，其容量不能改變袁梗。所以數組是不可以直接刪除和添加元素宜鸯。
- Collection 保存單一的元素，而 Map 保存相關聯的值鍵對遮怜，有了 Java 泛型淋袖，可以指定容器存放對象類型，不會將錯誤類型的對象放在容器中锯梁，取元素時候也不需要轉型适贸。而且 Collection 和 Map 都可以自動調整其尺寸灸芳。容器不可以持有基本類型。
- 像數組一樣拜姿，List 也建立數字索引和對象的關聯烙样，因此，數組和 List 都是排好序的容器蕊肥，List 可以自動擴容
- 如果需要大量的隨機訪問就要使用 ArrayList谒获，如果要經常從中間插入和刪除就要使用 LinkedList。
- 各種 Queue 和 Stack 由 LinkedList 支持
- Map 是一種將對象（而非數字）與對象相關聯的設計壁却。HashMap 用于快速訪問批狱，TreeMap 保持鍵始終處于排序狀態(tài)，所以不如 HashMap 快展东，而 LinkedHashMap 保持元素插入的順序赔硫，但是也通過散列提供了快速訪問的能力
- Set 不接受重復的元素，HashSet 提供最快的訪問能力盐肃，TreeSet 保持元素排序狀態(tài)爪膊，LinkedHashSet 以插入順序保存元素。
- 不應使用過時的 Vector砸王、HashTable
回顧一下開篇的簡圖：
可以發(fā)現其實只有四種容器 -- List推盛、Set、Queue谦铃、Map耘成。常用的用紅色標出，綠色標識接口驹闰，其他標識普通的類瘪菌。
使用時需要注意容器類之間方法的獨立性：有些相同，而有些相差很遠嘹朗。
上述即為本章的全部控嗜，共勉。
