《回爐重造 Java 基礎》——集合（容器）
整體框架
綠色代表介面/抽象類；藍色代表類。
主要由兩大介面組成，一個是「Collection」介面，另一個是「Map」介面。
前言
以前剛開始學習「集合」的時候，由於沒有好好預習，也沒有學好基礎知識，介面，類，這些基礎知識都沒學好，所以學到這裡還是懵懵懂懂的。第一次接觸到「集合」，這兩個字，在我的腦海中，只浮現出數學中學過的「集合」，所以當「集合」在程式語言中出現時，我就沒有繞過來。不過以我現在的視角看，也是和數學中學過的「集合」這種概念是差不多的。
數學中的「集合」：
集合是
確定的一堆東西，集合裡的東西則稱為元素。現代的集合一般被定義為：由一個或多個確定的元素所構成的整體。
Java 中的「集合」：在我的理解中，集合可以說是存放 Java 物件的東西，這個東西有人稱為集合，也有人稱為容器，這也是為什麼我的標題寫的是 集合（容器）。存放在集合中的物件，人們稱為元素。
為什麼會有集合的出現呢？
是這樣的，在某些情況下，我們需要建立許多 Java 物件，那麼這些物件應該存放在哪裡？
需求是這樣的：
- 可以存放物件
- 可以存放不同資料型別
- 可以存放很多物件，沒有限制
那麼一開始會想到陣列，陣列可以存放物件，是的，沒錯，但是，陣列有它的缺點，就是一旦建立後，那麼陣列長度是不可變的，而且存放的物件的資料型別是固定的，所以陣列不滿足這些條件。此時，集合就出現了。
Java 中的集合
從上面的框架圖中可以看到，主要就兩個介面，分別是 Collection 和 Map。
這兩個介面都抽象了元素的儲存方法，具體有什麼區別呢？好吧，不說也知道，Collection 就是用來儲存單一元素的，而 Map 是用來儲存鍵值對的。
下面我將從這兩個介面切入，進而開始好好地回爐重造，哈哈哈哈哈。
可以帶著這些問題去回顧：
- Collection 是怎樣的？Map 又是怎樣的？
- 它們分別還有什麼子介面？它們又有哪些實現類呢？
- 提供給我們的API又有哪些呢？具體的 API 用法和效果是怎樣的呢？
Collection
Collection 是最基本的集合介面，一個 Collection 代表一組 Object型別的物件，Java 沒有提供直接實現Collection 的類，只提供繼承該介面的子介面（List、Set、Queue 這些）。該介面儲存一組不唯一，無序的物件。這裡強調不唯一、無序，那麼集合的範圍就很大，想要縮小，比如唯一、有序這些，就可以通過子介面來規定，剛好，它就是這樣來定義子介面的。
- List 介面：元素不唯一且有序，說明可以儲存多個相同的元素，但是儲存是有順序的，即有序可重複。
- Set 介面：元素唯一且無序，說明不能儲存多個相同的元素，儲存的元素沒有順序，即無序不可重複。
我們再來看看 Collection 介面它抽象出來的方法有哪些。
其中，還可以看到有個以 Iterable（可迭代的） 來分類的方法，主要就是 iterator() 這個方法，即迭代器。所謂迭代器，就是用來遍歷集合元素的一個東西。
/**
* Returns an iterator over the elements in this collection. There are no
* guarantees concerning the order in which the elements are returned
* (unless this collection is an instance of some class that provides a
* guarantee).
*
* @return an <tt>Iterator</tt> over the elements in this collection
*/
Iterator<E> iterator();
iterator() 這個方法就是用來返回對此集合中元素的迭代器，也就是說獲取該集合的迭代器。 這個抽象方法不保證迭代的順序（除非此集合是某個提供保證的類的範例）。
再通俗一點，我們想要遍歷集合的元素，那麼就需要通過集合物件獲取迭代器物件，通過迭代器物件來遍歷集合中的元素，而且遍歷的順序是跟該集合有關的。
關於這個迭代器，後續再來講吧。
下面開始說一下基本的介面實現類，基本的API，加上一些自己的見解，最主要是先回顧 API 的使用，畢竟還有好多知識，這些知識需要建立在我們會用的前提下，所以這裡淺入淺出~
List 介面下的實現類
List 介面下的實現類有 ArrayList、LinkedList、Vector、Stack
這裡簡要介紹下 List 介面，List 介面是一個有序的 Collection，使用此介面能夠精確的控制每個元素插入的位置，能夠通過「索引」（即元素在 List 中位置，類似於陣列的下標，從0開始）來存取 List 中的元素。它儲存一組不唯一、有序（插入順序）的物件。
ArrayList
我們看下 ArrayList 原始碼，它是這樣定義的：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
...
}
可以看到，它
- 繼承了
AbstractList - 實現了
List，RandomAccess，Cloneable，Serializable
ArrayList 是動態陣列，所謂動態陣列，即可以動態的修改，隨時出入、刪除元素，還可以動態擴容，也就是沒有固定的容量限制，可以存放很多元素，直到你的記憶體爆炸。
初始化是這樣的：
// 1. 以多型的方式寫，介面不能範例化，所以通過其實現類對介面範例化。
List<E> list = new ArrayList<>();
// 2. 直接ArrayList
ArrayList<E> list = new ArrayList<>();
這兩種寫法有什麼區別呢？
第1種寫法：此時的 List 的物件 list，可以通過這個物件呼叫 List 介面宣告的方法，但是不能呼叫 ArrayList 獨有的方法，換句話說，List 這個介面規定了一些抽象的方法，具體實現不關心，你可以直接呼叫。這裡「具體實現不關心」就是說，你是使用 ArrayList 來範例化 List 介面或者使用 LinkedList 來範例化 List 介面，List 介面它都不關心，外界使用的時候，知道 List 提供這些 API 就夠了。另一個角度理解，即該 list 物件擁有 List 的屬性和方法，沒有 ArrayList 獨有的屬性和方法。
第2種寫法：此時 ArrayList 的物件 list，可以呼叫所有方法，畢竟 ArrayList 實現了 List 介面，那麼 List 有的方法，ArrayList 的物件 list也有。
進入正題
這些 API 的使用，需要熟悉，畢竟演演算法題也會用到。
public void apiOfArrayList() {
int idx;
List<Integer> list = new ArrayList<>();
// 新增元素
list.add(23);
list.add(30);
// 根據下標（索引）獲取元素
idx = list.get(0);
idx = list.get(1);
// 更新元素值，在某個位置重新賦值
list.set(1, 32);
List<String> list2 = new ArrayList<>();
list2.add("god23bin");
list2.add("LeBron");
list2.add("I love Coding");
// 移除下標（索引）為2的元素
list2.remove(2);
// 移除指定元素
list2.remove("god23bin");
// 獲取集合長度，遍歷會用到
int len = list2.size();
// 判斷某個元素是否在集合中，演演算法題會用到的
boolean flag = list2.contains("god23bin");
// 判斷集合是否為空，演演算法題會用到的
boolean flag2 = list2.isEmpty();
}
排序：
- ArrayList 中的 sort() 方法
Random random = new Random();
List<Integer> numList = new ArrayList<>();
for (int i = 0; i < 10; ++i) {
numList.add(random.nextInt(100));
}
// 將numList升序排序
numList.sort(Comparator.naturalOrder());
// 將numList降序排序
numList.sort(Comparator.reverseOrder());
- Collections 工具類的 sort() 方法
// 將numList升序排序
Collections.sort(numList);
關於 Collections 工具類的排序
看看這兩個方法，這兩個方法都是泛型方法。
public static <T extends Comparable<? super T>> void sort(List<T> list) {
list.sort(null);
}
public static <T> void sort(List<T> list, Comparator<? super T> c) {
list.sort(c);
}
第一個方法需要「待排序類」實現 Comparable 介面，這樣才能使用這個方法。
第二個方法需要「待排序類」有一個比較器，即 Comparator，換句話說需要有一個比較器類實現 Comparator 介面，這樣才能使用這個方法。
扯到 Comparable 和 Comparator
所以，如果你想要某個類的物件支援排序，那麼你就需要讓這個類實現 Comparable 介面，這個介面只有一個抽象方法 compareTo()，我們需要實現它，它的規則是：若 當前值 較大則返回正值，若相等則返回0，若 當前值 較小則返回負值。
這裡我們可以看到，Collections 是可以對 numList 進行排序的，因為這個 numList 集合的元素型別是 Integer，為什麼 Integer 型別的元素支援排序？我們可以從原始碼中看到 Integer 是實現了 Comparable 介面的，所以 Integer 型別的元素才支援排序。
public final class Integer extends Number implements Comparable<Integer> {
...
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}
...
}
回到第一句話，如果你想要某個類的物件支援排序，那麼你就需要讓這個類實現 Comparable 介面，不然是不支援排序的。
下面，我這裡就分別使用兩種方式（實現 Comparable 或 Comparator）讓某個類支援排序。
搞定 Comparable
舉個栗子：我這裡有一個 Game 類（待排序類，本身不支援排序，我們的任務是讓 Game 具有可排序的能力），當你把多個 Game 物件放到集合中使用 Collections 這個工具類進行排序時，Collections 是不知道如何給 Game 排序的，直到 Game 實現了 Comparable 介面後，Collections 才知道 Game 該如何排序。
Game 類實現 Comparable 介面，重寫 compareTo() 方法。
public class Game implements Comparable<Game> {
public String name;
public Double price;
// 省略 getter setter 構造方法
@Override
public int compareTo(Game o) {
return comparePrice(this.price, o.price);
}
public int comparePrice(double p1, double p2) {
return p1 > p2 ? 1 : (p1 == p2 ? 0 : -1);
}
}
這樣，我們就可以使用 Collections 對 Game 進行排序。
List<Game> gameList = new ArrayList<>();
gameList.add(new Game("GTA", 58.0));
gameList.add(new Game("FC", 118.0));
gameList.add(new Game("2K", 199.0));
Collections.sort(gameList); // 進行排序
System.out.println(gameList); // 列印排序結果
搞定 Comparator
同理，我這裡有一個 Game 類
public class Game {
public String name;
public Double price;
// 省略 getter setter 構造方法
}
寫一個 Game 的比較器類 GameComparator，讓這個類實現 Comparator 介面，重寫 compare() 方法
public class GameComparator implements Comparator<Game> {
@Override
public int compare(Game g1, Game g2) {
return g1.getPrice() - g2.getPrice();
}
}
這樣，我們就可以使用 Collections 對 Game 進行排序。
List<Game> gameList = new ArrayList<>();
gameList.add(new Game("GTA", 58.0));
gameList.add(new Game("FC", 118.0));
gameList.add(new Game("2K", 199.0));
Collections.sort(gameList, new GameComparator()); // 使用比較器進行排序
System.out.println(gameList); // 列印排序結果
總結排序
你可以選擇兩種方式（實現 Comparable 或 Comparator）中的其中一個，讓某個類支援排序。
- 選擇 Comparable，那麼該類需要實現該介面
- 選擇 Comparator，那麼需要定義一個比較器，實現該介面
最後通過 Collections.sort() 進行排序。
LinkedList
LinkedList 是連結串列，屬於線性表，學過資料結構的我們也是知道的，有指標域和資料域，雖然說 Java 裡沒有指標，但是有指標的思想，這裡我也說不太清楚，反正是可以按指標來理解的。（如有更好的描述，歡迎幫我補充啦！）
在 Java 中，這個 LinkedList 是 List 介面下面的實現類，也是很常用的一種集合容器，演演算法題也會用到它。
我們看下 LinkedList 原始碼，它是這樣定義的：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
...
}
可以看到，它
- 繼承了
AbstractSequentialList - 實現了
List，Deque，Cloneable，Serializable
同樣，LinkedList 需要掌握的方法和 ArrayList 差不多，可以說基本是一樣的，只是底層實現不一樣。
目前這裡就不演示基本的使用方法了，你可以自己動手試試啦！
Vector
我們看下 Vector 原始碼，它是這樣定義的：
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
...
}
可以看到，它
- 繼承了
AbstractList - 實現了
List，RandomAccess，Cloneable，Serializable
這樣一看，它和 ArrayList 的定義，簡直是一模一樣。那它們之間有什麼區別嗎？那當然是有啦！
區別就是 Vector 是執行緒安全的，在多執行緒操作下不會出現並行問題，因為 Vector 在每個方法上都加上了 synchronized 關鍵字，保證多個執行緒操作方法時是同步的。
Stack
Stack 顧名思義，就是棧，它是 Vector 的子類，實現了標準的棧這種資料結構。
public class Stack<E> extends Vector<E> {
...
}
它裡面包括了 Vector 的方法，也有自己的方法。
- empty()：判斷棧是否為空
- peek()：檢視棧頂元素
- push()：入棧
- pop()：出棧
- search()：搜尋元素，返回元素所在位置
public void apiOfStack() {
Stack<Integer> stack = new Stack<>();
// 入棧
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
// 獲取棧的大小 == 棧中元素個數 == 棧的長度
int size = stack.size();
// 檢視（返回）棧頂元素
Integer peek = stack.peek();
// 出棧
stack.pop();
// 判斷棧是否為空
boolean empty = stack.empty();
// 搜尋 元素1 此時棧中元素為 1 2 3，棧頂是3，棧底是1
// 從棧頂往下找，第一個元素的位置記為1
int search = stack.search(1);
}
但是目前這個已經官方不推薦使用了，而是選擇使用 LinkedList 來用作棧。
這裡就要扯到佇列 Queue 啦！
Queue 介面
Java 中的 Queue 是一個介面，和上面的 Stack 不同，Stack 是類。
我們看下 Queue 介面原始碼，它是這樣定義的：
public interface Queue<E> extends Collection<E> {
...
}
這個介面就抽象了 6 個方法：
- add()：入隊，即隊尾插入元素
- offer()：入隊，即隊尾插入元素
- peek()：檢視隊頭元素
- poll()：檢視隊頭元素
- remove()：出隊，即移除隊頭元素
- element()：出隊，即移除隊頭元素
很大的疑問來了！這些方法有什麼區別？？我們看看原始碼怎麼說的，這個原始碼說明也不怕，下面我有翻譯~
add() 和 offer() 的區別
/**
* Inserts the specified element into this queue if it is possible to do so
* immediately without violating capacity restrictions, returning
* {@code true} upon success and throwing an {@code IllegalStateException}
* if no space is currently available.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Collection#add})
* @throws IllegalStateException if the element cannot be added at this
* time due to capacity restrictions
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this queue
* @throws NullPointerException if the specified element is null and
* this queue does not permit null elements
* @throws IllegalArgumentException if some property of this element
* prevents it from being added to this queue
*/
/**
* 將指定的元素插入此佇列（如果可以立即執行此操作而不違反容量限制），成功則返回 true
* 如果容量不夠，則失敗，丟擲 IllegalStateException
*/
boolean add(E e);
/**
* Inserts the specified element into this queue if it is possible to do
* so immediately without violating capacity restrictions.
* When using a capacity-restricted queue, this method is generally
* preferable to {@link #add}, which can fail to insert an element only
* by throwing an exception.
*
* @param e the element to add
* @return {@code true} if the element was added to this queue, else
* {@code false}
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this queue
* @throws NullPointerException if the specified element is null and
* this queue does not permit null elements
* @throws IllegalArgumentException if some property of this element
* prevents it from being added to this queue
*/
/**
* 如果可以在不違反容量限制的情況下立即將指定的元素插入到此佇列中。
* 使用容量受限的佇列時，通常此方法是最好的入隊方法 ，只有當引發異常時才可能無法插入元素。
* 成功返回 true，失敗返回 false
*/
boolean offer(E e);
所以區別就是：在容量有限制的佇列中，add() 超過限制會丟擲異常，而 offer() 不會，只會返回 false
remove() 和 poll() 的區別
/**
* Retrieves and removes the head of this queue. This method differs
* from {@link #poll poll} only in that it throws an exception if this
* queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException if this queue is empty
*/
/**
* 檢索並刪除此佇列的隊頭元素。 這個方法與 poll 的區別僅僅是當佇列為空時刪除會丟擲異常。
*/
E remove();
/**
* Retrieves and removes the head of this queue,
* or returns {@code null} if this queue is empty.
*
* @return the head of this queue, or {@code null} if this queue is empty
*/
/**
* 檢索並刪除此佇列的隊頭元素。如果隊空，則返回 null
* or returns {@code null} if this queue is empty.
*
* @return the head of this queue, or {@code null} if this queue is empty
*/
E poll();
所以區別是：當隊空時刪除元素，那麼 remove() 會丟擲異常， poll() 會返回null
element() 和 peek() 的區別
/**
* Retrieves, but does not remove, the head of this queue. This method
* differs from {@link #peek peek} only in that it throws an exception
* if this queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException if this queue is empty
*/
/**
* 佇列為空時會丟擲異常
*/
E element();
/**
* Retrieves, but does not remove, the head of this queue,
* or returns {@code null} if this queue is empty.
*
* @return the head of this queue, or {@code null} if this queue is empty
*/
/**
* 佇列為空時會返回 null
*/
E peek();
所以區別是：當隊空檢視隊頭元素時，那麼 element() 會丟擲異常， peek() 會返回null
總的來說，就是失敗的區別：
| 丟擲異常 | 返回特殊值 | |
|---|---|---|
| 入隊 | add() | offer() 返回false |
| 出隊 | remove() | poll() 返回 null |
| 檢視隊頭元素 | element() | peek() 返回 null |
雙端佇列和優先順序佇列
Queue 有個子介面 Deque，就是雙端佇列，需要掌握的 Deque 實現類為 LinkedList 和 ArrayDeque。然後我們可以發現 Deque 這個介面抽象出來的方法，在原有的 Queue 上，多出了 First、Last 這些方法，對應著就是從佇列的頭部和尾部進行操作（入隊、出隊等等）。
有個抽象類 AbstractQueue 實現了 Queue 介面，然後 PriorityQueue 繼承了 AbstractQueue 。
演示下基本的 API，大部分操作都是大同小異。
public void apiOfDeque() {
// 通過 LinkedList 建立 Deque 物件
Deque<Integer> deque = new LinkedList<>();
// 正常隊尾入隊 => 完成入隊後 [1,2,3]
deque.addLast(1);
deque.addLast(2);
deque.addLast(3);
// 從隊頭入隊 => [4,1,2,3]
deque.addFirst(4);
// 獲取隊頭元素 => 4
// 這裡 get 和 peek 的區別就是，get 如果隊空會丟擲異常
Integer first = deque.getFirst();
// 使用 offer 入隊 => [4,1,2,3,5]
deque.offerLast(5);
// 使用 poll 出隊 => [1,2,3,5]
Integer integer = deque.pollFirst();
// 剩下的操作也是差不多的...
}
至於優先順序佇列的呢？之後再寫啦！這個坑等著後面補回來