1.前言：數據結構——隊列
隊列接口先說明有哪些功能矾湃，但不說是如何實現的，隊列有兩種實現方式：
- 循環(huán)數組
- 鏈表
循環(huán)數組更加高效掐场，但循環(huán)數組是個有界集合躯保，容量有限旋膳，如果對象的數量沒有上限澎语，最好用鏈表來實現途事。
一旦構建了集合就不需要知道到底使用了哪種實現验懊。所以可以使用接口類型存放集合的引用
List<String> list = new ArrayList<>();
list.add("abc");
如果我們想修改成另一種實現，只需要把ArrayList改成LinkedList尸变。
2.Collection 接口
collection接口有兩個基本方法：
// 如果添加元素確實改變了集合就返回 true;如果沒有改變就返回 false义图，比如添加的元素已經存在就不會改變原集合
boolean add(E element);
// 迭代器，見下一點
Iterator<E> iterator();
3.迭代器
Iterator接口有4個方法：
public interface Iterator<E>{
E next();
boolean hasNext();
void remove();
default void forEachRemaining(Student<? super E> stu);
}
反復調用 next() 方法召烂，能逐個訪問集合的每個元素碱工，但如果訪問到了集合的末尾，會拋出一個 NoSuchElementException奏夫，所以我們在調用next()前最好使用hasNext()檢查下怕篷。
List<String> list = new ArrayList<>();
list.add("abc");
list.add("123");
list.add("qwe");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next()); // abc 123 qwe
}
當然，如果要循環(huán)一個集合酗昼，更簡單的方法是使用forEach:
for (String s : list) {
System.out.println(s);
}
也可以使用forEachRemaining：
iterator.forEachRemaining(element -> System.out.println(iterator.next()));
順序問題：元素被訪問的順序取決于集合類型廊谓，如果對 ArrayList 進行迭代，迭代器將從索引0開始麻削，每迭代一次蒸痹，索引值加1。如果是 HashSet 呛哟，每個元素會按照某種特定的次序出現叠荠，雖然也能訪問到所有元素，但順序是隨機的扫责。
remove()刪除的是上次調用 next 方法時返回的元素榛鼎。所以調用 remove 之前必須要有 next 方法被調用。
4.集合中的接口
需要注意的是：數組支持的有序集合因為可以快速隨機訪問公给，所有最好提供一個整數索引來訪問借帘，鏈表最好使用迭代器來遍歷。
5.Java 庫中的具體集合
| 集合類型 | 描述 |
|---|---|
| ArrayList | 一種可以動態(tài)增長和縮減的索引序列 |
| LinkedList | 一種可以在任何位置進行高效地插入和刪除操作的有序序列 |
| ArrayDeque | 一種用循環(huán)數組實現的雙端隊列 |
| HashSet | 一種沒有重復元素的無序集合 |
| TreeSet | 一種有序集 |
| EnumSet | 一種包含枚舉類型值的集 |
| LinkedHashSet | 一種可以記住元素插入次序的集 |
| PriorityQueue | 一種允許高效刪除最小元素的集合 |
| HashMap | 一種存儲鍵 / 值關聯的數據結構 |
| TreeMap | 一種鍵值有序排列的映射表 |
| EnumMap | 一種鍵值屬于枚舉類型的映射表 |
| LinkedHashMap | 一種可以記住鍵 / 值添加次序的映射表 |
| WeakHashMap | 一種其值無用武之地后可以被垃圾回收器回收的映射表 |
| IdentityHashMap | 一種用 == 而不是 equals 比較鍵值的映射表 |
6.鏈表
數組列表的問題：從中間刪除一個元素之后淌铐，該元素后面的元素都需要向前移動肺然，在中間插入也是。
鏈表就沒有這個問題腿准。
鏈表讓我想到了比特幣的區(qū)塊結構际起，看圖吧
每個 Link 可以看成一個節(jié)點，每個節(jié)點存放著前一個節(jié)點的引用和后一個節(jié)點的引用吐葱，所以鏈表實際上都是雙向鏈接的街望。回到數組列表的問題弟跑，當我們需要插入一個元素的時候灾前，只需要修改該節(jié)點以及其前后節(jié)點的引用就可以了。
但鏈表不支持快速的隨機訪問孟辑，如果要查看第100個元素哎甲，就必須從頭開始蔫敲，越過99個元素。所以如果程序需要采用整數索引訪問元素時炭玫，通常不選用鏈表奈嘿。
7.數組列表
List 接口用于描述一個有序集合，并且集合中每個元素的位置十分重要吞加。有兩種訪問元素的協(xié)議：
- 用迭代器
- 用 get 和 set 方法隨機訪問每個元素
8.散列集
如果我們想要訪問某個元素裙犹，但又忘了它的位置，這時候就需要散列集衔憨。該集運用的數據結構為散列表（hash table）叶圃。散列表會為每個對象計算一個整數，成為散列碼（hash code）践图。散列碼是由對象的實例域產生的盗似。比如下表。
| 字符串 | 散列碼 |
|---|---|
| "Lee" | 76268 |
| "lee" | 107020 |
| "eel" | 100300 |
如果是我們自己定義的類平项，就要實現這個類的hashCode()方法赫舒，同時還有equals()方法。
set 類型：set 是沒有重復元素的元素集合闽瓢。set 的 add 方法首先會集中查找要添加的對象接癌，如果不存在，就將這個元素添加進去扣讼。
9.數集
TreeSet可以看成一個有序的散列集缺猛。當添加的時候會比較慢，但查詢會比散列集快很多椭符。
使用數集必須能比較元素荔燎，所有必須實現 comparable 接口。
10.隊列與雙端隊列
隊列可以讓人們有效的在尾部添加一個元素销钝，在頭部刪除一個元素有咨。有兩個端頭的隊列，即為雙端隊列蒸健，可以讓人們有效的在頭部和尾部同時添加或刪除元素座享。不支持在隊列中添加元素。Deque 接口由 ArrayDeque 和 LinkedList 實現似忧。
11.優(yōu)先級隊列
優(yōu)先級隊列中的元素可以按照任意的順序插入渣叛，卻總是按照排序的順序進行索引。也就是說盯捌，無論何時調用 remove 方法淳衙，總是獲得當前優(yōu)先級隊列中最小的元素。
12.映射的兩個實現
-
HashMap：散列映射對鍵進行散列。 -
TreeMap：樹映射用鍵的整體順序對元素進行排序箫攀，并將其組織成搜索樹筷狼。
如果不需要按照一定順序訪問鍵，就選擇散列匠童，因為散列更快一些。
一些基本的操作：
Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
String myName = maps.get("second");
System.out.println(myName); // zyc
鍵必須是唯一的塑顺，如果 put 的鍵是重復的汤求，則會覆蓋前一個。而且 put 會返回被覆蓋的那個值严拒。
13.迭代
- 利用 forEach 和 lambda 表達式：
Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
maps.forEach((k,v) ->
System.out.println("key:" + k +",val:" + v));
- 利用迭代器：
Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
Iterator<Map.Entry<String,String>> entryIterator = maps.entrySet().iterator();
entryIterator.forEachRemaining(System.out::println);
// entryIterator.forEachRemaining(element -> System.out.println(element));
14.Merge
當有這樣一個需求：需要更新/新增的映射項在映射存在或者不存在的時候會進行不同的操作扬绪，這時候就需要用上merge 了。具體看代碼吧
Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
maps.merge("first","i am new",(oldVal, newVal) -> {
System.out.println("1執(zhí)行了:" + oldVal + "," + newVal);
return oldVal;
});
maps.merge("first1","i am new",(oldVal, newVal) -> {
System.out.println("1執(zhí)行了:" + oldVal + "," + newVal);
return oldVal;
});
maps.forEach((k,v) ->
System.out.println("key:" + k +",val:" + v));
/*
1執(zhí)行了:ethan,i am new
key:third,val:zyy
key:first1,val:i am new
key:first,val:ethan
key:second,val:zyc
*/
因為first已經存在了裤唠，所以會執(zhí)行后面的函數挤牛，而first1不存在，所以根本就沒有執(zhí)行后面的值种蘸，而是僅僅把i am new設為first1對應的值墓赴。
15.映射視圖
雖然很多數據結構認為映射屬于集合，但在 java 中航瞭，映射并不在集合框架中诫硕。不過映射視圖是實現了 Collection 的對象。視圖包括鍵集合刊侯、值集合以及鍵值對集合章办。并且對三者進行remove操作會影響原視圖。鍵是不能重復的滨彻，所以直接刪除藕届，但值時可以重復的，這里只刪除了其中一個亭饵，不建議以刪除值來刪除鍵值對休偶。
Map<String, String> maps = new HashMap<>();
maps.put("first", "ethan");
maps.put("second", "zyc");
maps.put("third", "zyy");
maps.put("forth","zyc");
Set<String> keys = maps.keySet();
Collection<String> vals = maps.values();
Set<Map.Entry<String,String>> keyVals = maps.entrySet();
System.out.println(keys);
System.out.println(vals);
System.out.println(keyVals);
keys.remove("first");
vals.remove("zyc");
System.out.println(keyVals);
/*
[third, forth, first, second]
[zyy, zyc, ethan, zyc]
[third=zyy, forth=zyc, first=ethan, second=zyc]
[third=zyy, second=zyc]
*/
