前言

大部分編程語(yǔ)言都提供了數(shù)組來(lái)保存對(duì)象，數(shù)組是非常重要的數(shù)據(jù)結(jié)構(gòu)之一。但是數(shù)組在初始化時(shí)就已經(jīng)定義了數(shù)組長(zhǎng)度框喳，不可變，使用起來(lái)頗為麻煩。因此五垮，Java 在 JDK 1.2 版本中添加了集合框架乍惊，用來(lái)保存和操縱對(duì)象。

Java中的容器采用的是 "持有對(duì)象"（holding objects）的思想放仗，主要由繼承 Collection 與 Map 兩個(gè)接口來(lái)實(shí)現(xiàn)的润绎。下面我們來(lái)看一下這兩種容器：

1. 集合（Collection）：它主要是存放著對(duì)象的集合。主要是存放單一元素匙监。
2. 映射（Map）：它主要是存放著關(guān)于 "鍵值對(duì)" 的關(guān)系映射表凡橱，主要是存放 key-value 鍵值對(duì)的。

Collection

Collection 接口為主接口亭姥，下面還細(xì)分為 List稼钩、Set 與 Queue 這三個(gè)接口，這三個(gè)接口都是繼承于 Collection达罗，但要實(shí)現(xiàn)的功能卻不一樣坝撑。List 主要是存儲(chǔ)元素時(shí)，要保持插入的順序粮揉；Set 主要是不包含重復(fù)元素巡李；Queue 按照排序規(guī)則來(lái)確定對(duì)象產(chǎn)生的順序（通常與它們被插入的順序相同）。

Java Collection集合關(guān)系圖.png

但因?yàn)樗鼈兝^承于 Collection 接口扶认，因此侨拦，它們都具有一些相同的操作：

public interface Collection<E> extends Iterable<E> {
    int size(); // 集合的大小
    boolean isEmpty();  // 判斷集合是否為空
    boolean contains(Object o); // 判斷集合中是否存在該元素
    Iterator<E> iterator(); // 迭代器，用于遍歷集合使用
    Object[] toArray(); // 將集合轉(zhuǎn)換成數(shù)組
    <T> T[] toArray(T[] a); // 將集合轉(zhuǎn)換成指定類型的數(shù)組
    boolean add(E e);   // 將元素添加到集合中
    boolean remove(Object o);   // 將元素從集合中刪除
    boolean containsAll(Collection<?> c);   // 該集合是否包含了集合c
    boolean addAll(Collection<? extends E> c);  // 將集合c的元素都加到該集合中
    boolean removeAll(Collection<?> c); // 將集合c與該集合相同的元素都刪除
    boolean retainAll(Collection<?> c); // 去兩個(gè)集合的交集并保存在該集合中辐宾，如果不存在相同元素狱从，則該集合為空
    void clear();   // 清除該集合中元素
    boolean equals(Object o);   // 用于判斷兩集合是否相等
    int hashCode(); // 獲取hash值
}

在 Java 8 中，接口還添加了默認(rèn)方法：

// Java 8 新添加的默認(rèn)方法
default boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    boolean removed = false;
    final Iterator<E> each = iterator();
    while (each.hasNext()) {
        if (filter.test(each.next())) {
            each.remove();
            removed = true;
        }
    }
    return removed;
}
// 將集合轉(zhuǎn)換為流
default Stream<E> stream() {
    return StreamSupport.stream(spliterator(), false);
}
// 將集合轉(zhuǎn)換為并行流
default Stream<E> parallelStream() {
    return StreamSupport.stream(spliterator(), true);
}

以上就是 Collection 的 API 了叠纹。子類繼承后季研，這些方法也都繼承了，但是子類可以用不同的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)誉察。

Iterator & Iterable

Iterator 是 Java 中的迭代器与涡，能夠讓實(shí)現(xiàn)了該接口的類進(jìn)行迭代遍歷，我們來(lái)看一下 Iterator 接口：

public interface Iterator<E> {
    boolean hasNext();  // 判斷是否還存在下一個(gè)對(duì)象
    E next();   // 返回集合中的下一個(gè)對(duì)象持偏，并將訪問(wèn)指針向前移動(dòng)一位
    default void remove() { // 刪除操作
        throw new UnsupportedOperationException("remove");
    }
    // JDK 1.8
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

而我們接下來(lái)要學(xué)習(xí)的 Collection 接口繼承了 Iterable 接口驼卖，該接口中的 iterator() 方法能夠產(chǎn)生 Iterator 對(duì)象，來(lái)對(duì)集合進(jìn)行迭代遍歷：

public interface Iterable<T> {
    Iterator<T> iterator();
    // JDK 1.8
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

Iterable 接口提供了一個(gè)獲取 Iterator 對(duì)象的方法鸿秆，所以實(shí)現(xiàn)了 Iterable 接口的集合依舊可以使用 迭代器 遍歷和操作集合中的對(duì)象款慨。

我們使用一下實(shí)現(xiàn)了Iterable 接口的集合使用 Iterator 迭代器進(jìn)行遍歷：

LinkedList<String> list = new LinkedList<>();
list.add("Feb");
list.add(null);
list.add("Jan");
list.add("Mar");
System.out.println(Arrays.toString(list.toArray()));
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String it = iterator.next();
    if (it == null) iterator.remove();
}
System.out.println(Arrays.toString(list.toArray()));
/**
 * 輸出結(jié)果：
 * [Feb, null, Jan, Mar]
 * [Feb, Jan, Mar]
 */

而這樣子比較麻煩，在 JDK 1.8 之后谬莹，就提供了 for-each 方法來(lái)遍歷實(shí)現(xiàn)了 Iterable 接口的對(duì)象，它是 Java 中的一種 語(yǔ)法糖。如下所示：

for (String s : list) {
    System.out.println(s);
}

ListIterator 存在于 List 集合之中附帽，是一個(gè)功能比 Iterator 更強(qiáng)大的迭代器埠戳。

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();    // 
    void remove();  // 移除當(dāng)前索引位置的元素
    void set(E e);  // 設(shè)置當(dāng)前索引的元素
    void add(E e);  // 在當(dāng)前索引位置添加元素
}

從上面的方法中就可以了解到，ListIterator 是一個(gè)雙向移動(dòng)蕉扮，并根據(jù)迭代器中指向當(dāng)前位置的元素產(chǎn)生指向前一個(gè)和后一個(gè)元素的索引 index整胃。

public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("Jan");
    list.add(null);
    list.add("Feb");
    list.add("Mar");
    System.out.println("迭代之前的集合=" + Arrays.toString(list.toArray()));
    System.out.println("向后遍歷");
    ListIterator<String> iterator = list.listIterator();
    while (iterator.hasNext()) {
        System.out.println("當(dāng)前元素：" + iterator.next() + " 的后一個(gè)索引：" + iterator.nextIndex());
    }
    System.out.println("向前遍歷");
    while (iterator.hasPrevious()) {
        String pre = iterator.previous();
        System.out.println("當(dāng)前元素：" + pre + " 的前一個(gè)索引“);
        if (null == pre) iterator.set("Aug");
    }
    System.out.println("迭代之后的元素=" + Arrays.toString(list.toArray()));
}
/**
 * 輸出結(jié)果：
 * 迭代之前的集合=[Jan, null, Feb, Mar]
 * 向后遍歷
 * 當(dāng)前元素：Jan 的后一個(gè)索引：1
 * 當(dāng)前元素：null 的后一個(gè)索引：2
 * 當(dāng)前元素：Feb 的后一個(gè)索引：3
 * 當(dāng)前元素：Mar 的后一個(gè)索引：4
 * 向前遍歷
 * 當(dāng)前元素：Mar 的前一個(gè)索引：2
 * 當(dāng)前元素：Feb 的前一個(gè)索引：1
 * 當(dāng)前元素：null 的前一個(gè)索引：0
 * 當(dāng)前元素：Jan 的前一個(gè)索引：-1
 * 迭代之后的元素=[Jan, Aug, Feb, Mar]
 */

fail-fast

fail-fast 是Java集合中的一種錯(cuò)誤檢測(cè)機(jī)制，當(dāng)多個(gè)線程對(duì)部分集合進(jìn)行結(jié)構(gòu)上的改變的操作時(shí)喳钟，有何能會(huì)產(chǎn)生 fail-fast 機(jī)制屁使，這個(gè)時(shí)候會(huì)拋出 ConcurrentModificationException 異常。

最簡(jiǎn)單的例子就是在使用 for-each 語(yǔ)法進(jìn)行遍歷時(shí)進(jìn)行刪除操作：

List<String> list = new ArrayList<>();
list.add("Jan");
list.add(null);
list.add("Feb");
list.add("Mar");
System.out.println(Arrays.toString(list.toArray()));
for (String s : list) {
    if (s == null) list.remove(s);
}
System.out.println(Arrays.toString(list.toArray()));

這樣在運(yùn)行時(shí)會(huì)報(bào)錯(cuò)：

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1042)
    at java.base/java.util.ArrayList$Itr.next(ArrayList.java:996)
    at xxx.xxx.Xxxx.java:22)

我們都知道 for-each 只是一種 語(yǔ)法糖奔则，本身還是 Iterator 操作蛮寂，我們看上面報(bào)錯(cuò)中的源碼：

public E next() {
    checkForComodification();
    ...省略...
}

在 Iterator 的 next 操作時(shí)，會(huì)對(duì)該操作進(jìn)行檢查：

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

而 modCount 的值易茬，會(huì)在我們調(diào)用 remove 操作時(shí)進(jìn)行修改：

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;
    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);
    return oldValue;
}
private void fastRemove(Object[] es, int i) {
    modCount++; // 在進(jìn)行刪除是會(huì)對(duì) modCount進(jìn)行++操作
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

使得 modCount 與 expectedModCount 的值不能相等酬蹋，因此拋出 java.util.ConcurrentModificationException 異常，終止遍歷抽莱。

而如果想要解決上述的問(wèn)題范抓，我們給出兩個(gè)方案：

使用 Iterator 操作進(jìn)行刪除或者 JDK 1.8 新增的 removeIf 默認(rèn)方法。

Iterator<String> iterator = list.iterator();
    while (iterator.hasNext()) {
        String s = iterator.next();
        if (s == null) iterator.remove();
}
// 或者
list.removeIf(Objects::isNull);

還可以使用 CopyOnWriteArrayList 并發(fā)容器來(lái)替換 ArrayList食铐。

下面我們看一下繼承了 Collection 接口的三大子接口匕垫。

List

List 接口擴(kuò)展自 Collection 接口，其特點(diǎn)是有序虐呻、可以重復(fù)象泵。

List 主要新增了以下方法：

// 在某個(gè)位置上將集合c添加到該集合中
boolean addAll(int index, Collection<? extends E> c);
// 通過(guò)下標(biāo)獲取元素
E get(int index);
// 通過(guò)下標(biāo)設(shè)置元素
E set(int index, E element);
// 通過(guò)下標(biāo)添加元素
void add(int index, E element);
// 通過(guò)下標(biāo)移除元素
E remove(int index);
// 返回該元素的下標(biāo)位置
int indexOf(Object o);
// 返回該元素的最后遇到的位置
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);

我們常用的 List 類主要是 ArrayList 和 LinkedList。

ArrayList

ArrayList 的底層采用數(shù)組來(lái)進(jìn)行對(duì)象的存儲(chǔ)：

transient Object[] elementData;

又由于實(shí)現(xiàn) RandomAccess 接口铃慷，因此在查找的時(shí)候非车ノ撸快。

而在添加一個(gè)元素的時(shí)候由于是添加在尾部 elementData[size++] = e犁柜，因此順序添加時(shí)非常的快洲鸠。

而 ArrayList 在刪除元素的時(shí)候，會(huì)使用 System.arraycopy進(jìn)行一次復(fù)制操作馋缅。

System.arraycopy(elementData, index+1, elementData, index, numMoved)

如果復(fù)制的元素過(guò)多扒腕，則會(huì)非常損耗性能。

LinkedList

LinkedList 的底層使用雙向鏈表實(shí)現(xiàn)對(duì)象的存儲(chǔ)萤悴。順序存取瘾腰，允許存儲(chǔ)任何對(duì)象（包括null）。LinkedList 同時(shí)還實(shí)現(xiàn)了 Deque 接口覆履，該接口是繼承于 Queue蹋盆，因此該類可以當(dāng)做隊(duì)列使用费薄。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 指向第一個(gè)結(jié)點(diǎn)的指針
    transient Node<E> first;
    // 指向最后一個(gè)結(jié)點(diǎn)的指針
    transient Node<E> last;
    ...省略...
}

因?yàn)?LinkedList 實(shí)現(xiàn)了 Deque 接口，因此它的操作是雙向的栖雾，例如如下方法楞抡，可以選擇添加頭部還是尾部的操作。

public void addFirst(E e) {
    linkFirst(e);
}
public void addLast(E e) {
    linkLast(e);
}

LinkedList 中以 Node 表示雙向鏈表中的每個(gè)結(jié)點(diǎn)析藕，如下：

private static class Node<E> {
    // 存儲(chǔ)數(shù)據(jù)
    E item;
    // 指向前一個(gè)結(jié)點(diǎn)的指針
    Node<E> next;
    // 指向下一個(gè)結(jié)點(diǎn)的指針
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

我們由上源碼中召廷，知道了 LinkedList 的數(shù)據(jù)結(jié)構(gòu)，因此账胧，要使用 LinkedList 進(jìn)行增刪改查竞慢，都會(huì)從頭開(kāi)始遍歷進(jìn)行查找，不像 ArrayList 可以隨機(jī)訪問(wèn)治泥。但是筹煮，在進(jìn)行插入和刪除的操作時(shí)，比 ArrayList 快车摄，只需要將指針指向你所需要的元素即可寺谤。

Vector

Vector 的數(shù)據(jù)結(jié)構(gòu)與 ArrayList 相似，都是使用數(shù)組 Object[] elementData 來(lái)進(jìn)行數(shù)據(jù)的存儲(chǔ)吮播，但會(huì)使用 synchronized 關(guān)鍵字加鎖進(jìn)行同步：

 public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

add 方法就是用 synchronized 關(guān)鍵字加鎖变屁，其它如 get、remove 等方法都有加鎖意狠。因此粟关，Vector 使用 synchronized 關(guān)鍵字來(lái)保證線程安全，但這樣的效率較低环戈，已經(jīng)不太建議使用闷板。

我們一般推薦使用 ArrayList 來(lái)替代 Vector 來(lái)實(shí)現(xiàn)功能。

Stack

Stack 繼承于 Vector院塞，它是一個(gè)后入先出的容器遮晚，就是不斷將元素壓入（push）Stack中，而彈出（pop）元素必定是最后壓入Stack 中的元素拦止。

Stack 實(shí)現(xiàn)的有這幾種方法：

// 將元素鍵入棧中
public E push(E item) {}
// 將元素從棧頂中彈出
public synchronized E pop() {}
// 去除棧頂?shù)脑氐粡棾?public synchronized E peek() {}
// 判斷棧是否為空
public boolean empty() {}
// 返回對(duì)象離棧頂?shù)木嚯x
public synchronized int search(Object o) {}

但因?yàn)?Stack 繼承于 Vector县遣，因此它也包含 Vector 中的全部 API。也因此不推薦使用它汹族，我們可以使用 Deque 接口來(lái)自己實(shí)現(xiàn)棧的功能萧求。

線程安全

因?yàn)榫€程安全的 Vector 類已經(jīng)不推薦使用，但 ArrayList 或者 LinkedList 沒(méi)有線程安全機(jī)制顶瞒，我們需要實(shí)現(xiàn)線程安全的話夸政，就要使用 Collections 類的靜態(tài)方法 synchronizedList() 獲取線程安全的 List 或者使用 CopyOnWriteArrayList 實(shí)現(xiàn)線程安全的操作。

怎么確保一個(gè)集合不能被修改榴徐？

可以使用 Collections.unmodifiableCollection(Collection c) 方法來(lái)創(chuàng)建一個(gè)只讀集合守问，這樣改變集合的任何操作都會(huì)拋出 java.lang.UnsupportedOperationException 異常匀归。

示例代碼：

List<String> list = new ArrayList<>();
list.add("Jan");
Collection<String> clist = Collections.unmodifiableCollection(list);
clist.add("Feb");   // 運(yùn)行時(shí)此處報(bào)錯(cuò)

Queue

Queue隊(duì)列是先進(jìn)先出的線性數(shù)據(jù)結(jié)構(gòu)；我們看一下 Queue 的接口：

public interface Queue<E> extends Collection<E> {
    boolean add(E e);   // 添加元素酪碘，失敗會(huì)拋異常
    boolean offer(E e); // 同上朋譬，返回值(會(huì)返回false)
    E remove(); // 刪除元素，失敗會(huì)拋異常
    E poll();   // 同上兴垦，返回值(會(huì)返回null)
    E element();    // 獲取元素，失敗會(huì)拋異常
    E peek();   // 同上字柠，返回值(會(huì)返回null)
}

我們由上可知探越，Queue 接口是繼承 Collection 的子接口，主要是添加了六個(gè)方法窑业，可以分為兩組钦幔，用于增刪查。add/remove/element 為一組常柄，它的情況是失敗后拋出異常鲤氢；offer/poll/peek 為一組，它的情況是失敗后返回特殊的值（null或false）西潘。在隊(duì)列有界且無(wú)空閑空間時(shí)才會(huì)使添加操作拋出異尘碛瘢或返回false。這種情況我們使用 offer 這種來(lái)代替 add 這組操作喷市。

在 JDK 中沒(méi)有一個(gè)隊(duì)列的實(shí)現(xiàn)僅僅實(shí)現(xiàn)了 Queue 接口相种。因?yàn)?Queue 只有基本的隊(duì)列功能。因此品姓，要擴(kuò)展 Queue 接口寝并。

PriorityQueue

PriorityQueue 是基于二叉堆實(shí)現(xiàn)的優(yōu)先級(jí)隊(duì)列，而堆是采用數(shù)組實(shí)現(xiàn)的腹备，并且可以指定 Comparator 比較器衬潦，如果不傳入 Comparator，則自然排序 ：

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {
    /**
     * Priority queue represented as a balanced binary heap: the two
     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
     * priority queue is ordered by comparator, or by the elements'
     * natural ordering, if comparator is null: For each node n in the
     * heap and each descendant d of n, n <= d.  The element with the
     * lowest value is in queue[0], assuming the queue is nonempty.
     */
    transient Object[] queue; // 隊(duì)列
    private final Comparator<? super E> comparator; // 比較器植酥，用于確定優(yōu)先級(jí)高低
    ...省略...
}

上述的注釋介紹的是 transient Object[] queue 存儲(chǔ)的優(yōu)先隊(duì)列表示為一個(gè)平衡的二叉樹(shù)并且隊(duì)列與其子隊(duì)列的位置镀岛。如果不傳入 comparator，則會(huì)按照自然順序排序惧互。

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

我們看一下它的添加元素的方法可以知道哎媚，PriorityQueue 不是線程安全的，并且不支持 null喊儡。而如果想要線程安全拨与，可以使用并發(fā)包下的 java.util.concurrent.PriorityBlockingQueue 類。

Deque

Deque 接口就是對(duì) Queue 的擴(kuò)展艾猜， Deque 是繼承于 Queue 實(shí)現(xiàn)兩端都能進(jìn)出的雙端隊(duì)列买喧。它的API中就有對(duì) First 端和 Last 端的操作捻悯，add/remove/get 是一組操作，會(huì)拋異常淤毛；offer/poll/peek 是一組操作今缚，它會(huì)在失敗時(shí)返回值。

public interface Deque<E> extends Queue<E> {
    void addFirst(E e); // 添加到頭部低淡，異常報(bào)錯(cuò)
    void addLast(E e);  // 添加到尾部姓言，異常報(bào)錯(cuò)
    boolean offerFirst(E e);    // 添加到頭部，失敗返回false蔗蹋。
    boolean offerLast(E e);     // 添加到尾部何荚，失敗返回false。
    E removeFirst();    // 移除頭部元素猪杭，異常報(bào)錯(cuò)
    E removeLast();     // 移除尾部元素餐塘，異常報(bào)錯(cuò)
    E pollFirst();      // 移除頭部元素，失敗返回null皂吮。
    E pollLast();       // 移除尾部元素戒傻，失敗返回null。
    E getFirst();       // 獲取頭部元素蜂筹，異常報(bào)錯(cuò)
    E getLast();        // 獲取尾部元素需纳，異常報(bào)錯(cuò)
    E peekFirst();      // 獲取頭部元素，失敗返回null狂票。
    E peekLast();       // 獲取尾部元素候齿，失敗返回null。
    boolean add(E e);   // 添加元素闺属，異常報(bào)錯(cuò)
    boolean offer(E e); // 添加元素慌盯，失敗返回false。
    E remove();         // 移除元素掂器，異常報(bào)錯(cuò)
    E poll();           // 移除元素亚皂，失敗返回false。
    E element();        // 獲取元素国瓮，異常報(bào)錯(cuò)
    E peek();           // 獲取元素灭必，失敗返回null。
    void push(E e);     // 入棧
    E pop();            // 出棧
    boolean remove(Object o);   // 移除指定對(duì)象
    boolean contains(Object o); // 判斷元素是否存在
}

而在使用時(shí)乃摹，請(qǐng)選擇同一組進(jìn)行使用禁漓。

實(shí)現(xiàn) Deque 接口的主要有 ArrayDeque、LinkedList孵睬、PriorityQueue 和其它一些并發(fā)容器 ConcurrentLinkedDeque播歼、LinkedBlockingDeque 等。

這里我們只介紹 ArrayDeque 和 PriorityQueue掰读。LinkedList 已經(jīng)在上面介紹過(guò)了秘狞。

ArrayDeque

ArrayDeque 是實(shí)現(xiàn) Deque 接口的雙端隊(duì)列叭莫，它繼承于 AbstractCollection，其底層還是基于 Collection 接口實(shí)現(xiàn)的集合框架：

public class ArrayDeque<E> extends AbstractCollection<E>
    implements Deque<E>, Cloneable, Serializable {
    
    transient Object[] elements;    // 用于元素存儲(chǔ)的隊(duì)列是數(shù)組實(shí)現(xiàn)的
    transient int head; // 頭部索引
    transient int tail; // 下一步要添加到尾部的索引(當(dāng)前索引為tail-1)
    ...省略...
}

我們看一下 ArrayDeque 實(shí)現(xiàn)的 addFirst 方法：

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

從 addFirst 中可以看出烁试，它的操作不是線程安全的雇初，且不能插入 null，而如果 head == tail 减响，就會(huì)進(jìn)行擴(kuò)容靖诗。

而 LinkedList 也是實(shí)現(xiàn)了 Deque，不可避免的與 ArrayDeque 進(jìn)行比較辩蛋。

ArrayDeque 底層是由數(shù)組進(jìn)行實(shí)現(xiàn)的呻畸，而 LinkedList 底層是由循環(huán)鏈表來(lái)進(jìn)行實(shí)現(xiàn)，鏈表在添加悼院、刪除方法的性能要高于數(shù)組結(jié)構(gòu)，但查詢方法數(shù)組結(jié)構(gòu)要高于鏈表結(jié)構(gòu)咒循。但數(shù)組中元素不進(jìn)行移動(dòng)据途，只在后面添加，效率也不差叙甸。

ArrayDeque 可以作為隊(duì)列使用颖医，也可以作為棧來(lái)使用。因此裆蒸，我們可以使用它來(lái)替代 Stack 實(shí)現(xiàn)棧功能。

Set

Set 接口擴(kuò)展自 Collection 接口，其特點(diǎn)是不重復(fù)淆党。

public interface Set<E> extends Collection<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c);
    boolean removeAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT);
    }
}

由 Set 接口與 Collection 進(jìn)行對(duì)比吼蚁，Set 具有與 Collection 完全一樣的接口，沒(méi)有額外的功能辙谜。

Set的常用的實(shí)現(xiàn)類有 HashSet俺榆、LinkedHashSet 與 TreeSet 。

HashSet

從HashSet 的源碼中可知装哆，它的底層使用 HashMap 的 key 來(lái)存儲(chǔ)元素罐脊，主要特點(diǎn)是無(wú)序的。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    // 用于存儲(chǔ)元素的映射表
    private transient HashMap<E,Object> map;
    // 用來(lái)存放在映射表中的偽值
    private static final Object PRESENT = new Object();
    public HashSet() {
        map = new HashMap<>();
    }
    ...省略...
    public boolean add(E e) {
        // 將值當(dāng)作映射表的鍵來(lái)存儲(chǔ)
        return map.put(e, PRESENT)==null;
    }
    ...省略...
}

而從 add 方法可知蜕琴，HashSet 是否線程安全由 HashMap 決定萍桌，而 HashMap 本身就不是線程安全的，因此 HashSet 也是線程不安全的凌简。

LinkedHashSet

LinkedHashSet 本身繼承 HashSet

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    public LinkedHashSet() {
        super(16, .75f, true);
    }
}

它會(huì)調(diào)用父類 HashSet 的構(gòu)造方法：

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

有父類中的構(gòu)造方法可知上炎，HashMap 是由 LinkedHashMap 來(lái)實(shí)現(xiàn)的，而 LinkedHashMap 的底層使用的是 HashMap + 雙向鏈表來(lái)實(shí)現(xiàn)号醉，這樣能夠保留插入的順序反症。LinkedHashSet 也不是線程安全的辛块。

TreeSet

TreeSet 底層是使用 TreeMap 來(lái)實(shí)現(xiàn)，數(shù)據(jù)結(jié)構(gòu)是數(shù)組+紅黑樹(shù)铅碍，因此它存儲(chǔ)的元素有序润绵，可以自定義比較器或使用本身比較器實(shí)現(xiàn)自然排序。

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    private transient NavigableMap<E,Object> m; // 用來(lái)存儲(chǔ)元素的映射表
    
    // 用來(lái)存放在Map的偽值與key構(gòu)建成鍵值對(duì)
    private static final Object PRESENT = new Object();

    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
    ...省略...
}

如果需要自定義排序胞谈，使用如下構(gòu)造方法來(lái)傳入一個(gè) Comparator 比較器：

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

TreeSet 不可以存儲(chǔ) null尘盼，并且也不是線程安全的。由于 TreeSet 無(wú)重復(fù)且有序的特點(diǎn)烦绳，可以使用 TreeSet 實(shí)現(xiàn)學(xué)校的成績(jī)榜單功能卿捎。

class Student implements Comparable<Student> {
    String name;
    double totalScore;
    public Student(String name, double totalScore) {
        this.name = name;
        this.totalScore = totalScore;
    }
    @Override
    public int compareTo(Student o) {
        return Double.compare(o.totalScore, this.totalScore);
    }
    @Override
    public String toString() {
        return "Student{" + "姓名='" + name + '\'' + ", 總分=" + totalScore + '}';
    }
}
public static void main(String[] args) {
    Set<Student> students = new TreeSet<>();
    students.add(new Student("小趙", 561.5));
    students.add(new Student("小錢(qián)", 342.5));
    students.add(new Student("小孫", 720));
    students.add(new Student("小李", 480));
    System.out.println(Arrays.toString(students.toArray()));
}
/**
 * 輸出結(jié)果：
 * [Student{姓名='小孫', 總分=720.0}, Student{姓名='小趙', 總分=561.5}, Student{姓名='小李', 總分=480.0}, Student{姓名='小錢(qián)', 總分=342.5}]
 */

上面就是對(duì) Collection 集合的大體介紹，下面讓我們來(lái)了解 Map 径密。

Map

Map是存儲(chǔ)著由 key-value組成的對(duì)象的映射表午阵，key 具有唯一性，我們可以使用 key 來(lái)查找對(duì)應(yīng)的 value 享扔。

Java Map映射關(guān)系.png

下面看一下 Map 接口的定義：

public interface Map<K,V> {
    // 映射表大小(用于判斷映射表中鍵值對(duì)的數(shù)量)
    int size();
    // 判斷映射表是否為空
    boolean isEmpty();
    // 判斷該映射表中是否包含指定的鍵key
    boolean containsKey(Object key);
    // 判斷該映射表中是否包含指定的值value
    boolean containsValue(Object value);
    // 通過(guò)鍵key底桂，獲取該映射表中對(duì)應(yīng)的值
    V get(Object key);
    // 將 key-value 對(duì)應(yīng)關(guān)系存放在該映射表中
    V put(K key, V value);
    // 刪除該映射表中對(duì)應(yīng)的鍵key的映射關(guān)系
    V remove(Object key);
    // 將m映射表中的鍵值關(guān)系全部存入該映射表中
    void putAll(Map<? extends K, ? extends V> m);
    // 移除當(dāng)前映射表中所有的映射關(guān)系
    void clear();
    // 將該映射表中所有的鍵組成集合，并返回
    Set<K> keySet();
    // 將該映射表中所有的值組成集合惧眠，并返回
    Collection<V> values();
    // 將該映射表中所有鍵值對(duì)組成集合籽懦，并返回
    Set<Map.Entry<K, V>> entrySet();
    // Entry接口代表Map中存儲(chǔ)的鍵值關(guān)系
    interface Entry<K,V> {
        // 返回當(dāng)前entry對(duì)應(yīng)的鍵
        K getKey();
        // 返回當(dāng)前entry對(duì)應(yīng)的值
        V getValue();
        // 設(shè)置當(dāng)前entry對(duì)應(yīng)鍵的值
        V setValue(V value);
        // 判斷當(dāng)前entry與另一個(gè)是否相等
        boolean equals(Object o);
        // 獲取當(dāng)前entry的hash碼
        int hashCode();
    }
    // 用于判斷兩個(gè)映射表是否相等
    boolean equals(Object o);
    // 獲取映射表的hash碼
    int hashCode();
}

有以上的方法可以知道一些 Map 提供的功能。而對(duì)于 Map 的實(shí)現(xiàn)會(huì)有兩種不同的方向：

• AbstractMap ：使用抽象類來(lái)實(shí)現(xiàn) Map 的一些通用功能氛魁，基本上實(shí)現(xiàn)的 Map 都要繼承它暮顺，例如 HashMap。
• SortedMap：這是對(duì) Map 接口進(jìn)行擴(kuò)展的可排序的接口類秀存，該接口中定義了 Comparator 對(duì)象捶码，會(huì)按照它進(jìn)行排序，例如 TreeMap应又。

下面介紹幾個(gè)最常用的實(shí)現(xiàn)類 HashMap宙项、TreeMap、LinkedHashMap 和 ConcurrentHashMap株扛。

HashMap

HashMap 是最常用的一個(gè) Map尤筐，它實(shí)現(xiàn)了 AbstractMap 類

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

它通過(guò)計(jì)算 key 對(duì)象的 hash 值來(lái)決定在Map中的存儲(chǔ)位置，不能保證插入的順序洞就。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在 JDK 1.8 之前盆繁，底層采用數(shù)組+單鏈表實(shí)現(xiàn)；JDK 1.8 之后使用數(shù)組+單鏈表+紅黑樹(shù)實(shí)現(xiàn)旬蟋。發(fā)生 hash 沖突時(shí)油昂，HashMap 會(huì)將具有相同映射地址的元素連成一條鏈表，當(dāng)鏈表長(zhǎng)度大于8且數(shù)組長(zhǎng)度大于64時(shí)，會(huì)將單鏈表轉(zhuǎn)換成紅黑樹(shù)冕碟。

TreeMap

TreeMap 是具有排序功能的 Map拦惋，它實(shí)現(xiàn)了 NavigableMap 接口：

public interface NavigableMap<K,V> extends SortedMap<K,V> {
    ...省略...
}

而 NavigableMap 是繼承于 SortedMap 接口的擴(kuò)展接口，可以接收一個(gè) Comparator 進(jìn)行自定義排序：

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

而如果不傳入 Comparator安寺，默認(rèn)會(huì)按照 key 自然排序厕妖，因此，key 是要實(shí)現(xiàn)了 Comparable 接口的對(duì)象挑庶，否則會(huì)在運(yùn)行時(shí)拋出 java.lang.CassCastException 異常言秸。

TreeMap 底層是采用數(shù)組+紅黑樹(shù) 來(lái)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，整個(gè)數(shù)據(jù)結(jié)構(gòu)都保持著有序的狀態(tài)迎捺，并且不可以插入null鍵举畸，但可以有null值。

下面來(lái)舉一個(gè)小例子：

class Student {
    String name;
    double totalScore;
    public Student(String name, double totalScore) {
            this.name = name;
            this.totalScore = totalScore;
        }
    @Override
    public String toString() {
    return "Student{" + "姓名='" + name + '\'' + ", 總分=" + totalScore + '}';
    }
}
public static void main(String[] args) {
    TreeMap<Integer, Student> students = new TreeMap<>();
    students.put(2, new Student("小趙", 561.5));
    students.put(4, new Student("小錢(qián)", 342.5));
    students.put(1, new Student("小孫", 720));
    students.put(3, new Student("小李", 480));
    System.out.println(students);
}
/**
 * 輸出結(jié)果：
 * {1=Student{姓名='小孫', 總分=720.0}, 2=Student{姓名='小趙', 總分=561.5}, 3=Student{姓名='小李', 總分=480.0}, 4=Student{姓名='小錢(qián)', 總分=342.5}}
 */

LinkedHashMap

LinkedHashMap 是在 HashMap 的基礎(chǔ)上加上雙向鏈表凳枝，用于保證元素的有序性抄沮。

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    // 用于訪問(wèn)鏈表的頭部
    transient LinkedHashMap.Entry<K,V> head;
    // 用于訪問(wèn)鏈表的尾部
    transient LinkedHashMap.Entry<K,V> tail;
    ...省略...
}

來(lái)個(gè)小例子：

LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("八月", 8);
map.put("十二月", 12);
map.put("二月", 2);
map.put("七月", 7);
System.out.println(map);
/**
 * 輸出結(jié)果：
 * {八月=8, 十二月=12, 二月=2, 七月=7}
 */

可以看出，它輸出結(jié)果與插入順序一致岖瑰，是有序的合是。

IdentityHashMap

IdentityHashMap 繼承于 AbstractMap 抽象類并實(shí)現(xiàn)了 Map 接口，它與 HashMap 的繼承類與實(shí)現(xiàn)接口基本相同锭环。

public class IdentityHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, java.io.Serializable, Cloneable

但是 IdentityHashMap 使用 Object[] table 數(shù)組來(lái)存儲(chǔ)元素，并且可以存儲(chǔ)重復(fù)的 key泊藕，因?yàn)樵?IdentityHashMap 中使用的是 item == k辅辩，要相同的引用才能判斷它倆相同。

我們看下面的例子：

IdentityHashMap<String, Integer> identityHashMap = new IdentityHashMap<>();
String jan1 = "Jan";
String jan2 = "Jan";
identityHashMap.put(jan1, 1);
identityHashMap.put(jan2, 1);
System.out.println(identityHashMap.get("Jan"));
System.out.println(identityHashMap);
/**
 * 輸出結(jié)果：
 * 1
 * {Jan=1}
 */

這是因?yàn)?jan1 和 jan2 都只想常量池中的 Jan娃圆。而如果使用如下方式：

IdentityHashMap<String, Integer> identityHashMap = new IdentityHashMap<>();
String jan1 = "Jan";
String jan2 = new String("Jan");
identityHashMap.put(jan1, 1);
identityHashMap.put(jan2, 1);
System.out.println(identityHashMap.get("Jan"));
System.out.println(identityHashMap);
/**
 * 輸出結(jié)果：
 * 1
 * {Jan=1, Jan=1}
 */

這說(shuō)明 jan2 是指向堆中的空間玫锋，new 出來(lái)的字符串對(duì)象。而如果使用 identityHashMap.get(new String("Jan")) 來(lái)獲取值讼呢，就會(huì)輸出 null撩鹿，原理也是在堆中創(chuàng)建的新的字符串對(duì)象。

IdentityHashMap 也是 hash 存儲(chǔ)悦屏，因此它無(wú)序节沦，而且還不是線程安全的。

WeakHashMap

WeakHashMap 繼承于 AbstractMap 抽象類并實(shí)現(xiàn)了 Map 接口础爬，它也是基于 hash 實(shí)現(xiàn)的 Map甫贯， 因此它與 HashMap 的大多數(shù)功能都相同。

public class WeakHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>

但是在 WeakHashMap 中實(shí)現(xiàn)的 Entry 卻不相同：

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    V value;
    final int hash;
    Entry<K,V> next;
    Entry(Object key, V value,
        ReferenceQueue<Object> queue,
        int hash, Entry<K,V> next) {
        super(key, queue);
        this.value = value;
        this.hash  = hash;
        this.next  = next;
    }
    ...省略...
}

Entry 繼承了 WeakReference 看蚜，利用 WeakReference 的機(jī)制來(lái)實(shí)現(xiàn)不阻止GC回收Key叫搁，即每次GC，都會(huì)將這個(gè)對(duì)象清除。

而WeakHashMap 中維護(hù)的 ReferenceQueue 的作用就是用來(lái)存儲(chǔ)哪些 key 已被清除渴逻。

private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

在每次 put/size 等操作時(shí)疾党，都會(huì)調(diào)用 expungeStaleEntries 方法，用來(lái)刪除表中已經(jīng)被刪除的 key 對(duì)應(yīng)的 Entry惨奕，來(lái)達(dá)到同步的效果雪位。

private void expungeStaleEntries() {
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>) x;  // 隊(duì)列中已被刪除的entry
            // 獲取元素在table的索引
            int i = indexFor(e.hash, table.length);
            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            while (p != null) { // 偏移鏈表
                Entry<K,V> next = p.next;
                if (p == e) {   // 如果鏈表中存在過(guò)期的entry，我們就要?jiǎng)h除它
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next;
                    // 我們這里將置null墓贿，來(lái)幫助GC
                    e.value = null; // Help GC
                    size--; // 容器數(shù)量減一
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }
}

WeakHashMap 通常作為緩存使用茧泪，適用于存儲(chǔ)只需保存短暫時(shí)間的鍵值對(duì)，它也是非線程安全的集合聋袋。

Hashtable

Hashtable 也是實(shí)現(xiàn)了 Map 接口的類队伟。底層使用 數(shù)組+鏈表 來(lái)實(shí)現(xiàn)。

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
    private transient Entry<?,?>[] table;
    ...省略...
}

在進(jìn)行 put/remove 等操作時(shí)幽勒，都會(huì)在方法上添加 synchronized 關(guān)鍵字來(lái)實(shí)現(xiàn)同步嗜侮，比較簡(jiǎn)單粗暴。

public synchronized V put(K key, V value) {
    if (value == null) {
        throw new NullPointerException();
    }
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    addEntry(hash, key, value, index);
    return null;
}

這樣的操作使得 Hashtable 是一個(gè)線程安全的 Map啥容，但這樣也使 Hashtable 的性能較差锈颗，與 Vector 差不多，因此會(huì)被淘汰咪惠。

而我們想要使用線程安全的 Map击吱，就可以使用 java.util.concurrent 包下的 ConcurrentHashMap 類。

總結(jié)

此文是對(duì) Java 容器做一個(gè)較為整體的介紹遥昧，了解了每個(gè)容器的特性覆醇。我們做一下總結(jié)：

1. 以對(duì)象方式存儲(chǔ)，使用的是實(shí)現(xiàn) Collection 接口的實(shí)現(xiàn)類炭臭；以鍵值對(duì)方式存儲(chǔ)永脓，使用的是實(shí)現(xiàn) Map 接口的實(shí)現(xiàn)類。
2. 實(shí)現(xiàn) List 接口的類都是有序并可重復(fù)存儲(chǔ)的集合鞋仍，常見(jiàn)的有 ArrayList常摧、LinkedList 和 Vector。
3. 實(shí)現(xiàn) Set 接口的類都存儲(chǔ)的元素不可重復(fù)威创，常見(jiàn)的有 HashSet落午、LinkedHashSet和TreeSet。
4. Queue 接口實(shí)現(xiàn)了隊(duì)列的基本操作那婉，而 Deque 定義雙端隊(duì)列的操作板甘。
5. 實(shí)現(xiàn)了 Map 接口的類有基于 hash 存儲(chǔ)的 HashMap，可以排序的 TreeMap 和弱引用的 WeakHashMap详炬。

而在選擇容器時(shí)盐类，我們通常都會(huì)將它們實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)寞奸，線程安全性，是否重復(fù)在跳，有序枪萄，應(yīng)用場(chǎng)景等進(jìn)行對(duì)比，來(lái)選擇我們要使用的容器猫妙。

如果想要查看更多文章瓷翻，請(qǐng)關(guān)注公眾號(hào)「海人為記」