一、前言

Java 容器集合框架

1.1 Collection

Collection是List和Set抽象出來的接口，它包含了這些集合的基本操作。

(1) List

List接口通常表示一個(gè)列表（數(shù)組、隊(duì)列、鏈表，棧等），其中的元素可以重復(fù)，常用的實(shí)現(xiàn)類為ArrayList、LinkedList和Vector。

(2) Set

Set接口通常表示一個(gè)集合，集合中的元素不允許重復(fù)（通過hashCode和equals函數(shù)保證），常用的實(shí)現(xiàn)類有HashSet和TreeSet，HashSet是通過Map中的HashMap來實(shí)現(xiàn)的，而TreeSet則是通過Map中的TreeMap實(shí)現(xiàn)的，另外TreeSet還實(shí)現(xiàn)了SortedSet接口，因此是有序的集合。

(3) List 和 Set 的區(qū)別

• Set接口存儲的是無序的、不重復(fù)的數(shù)據(jù)
• List接口存儲的是有序的、可以重復(fù)的數(shù)據(jù)
• Set檢索效率低，刪除和插入效率高，插入和刪除不會引起元素位置改變。
• List查找元素效率高，刪除和插入效率低，List和數(shù)組類似，可以動態(tài)增長，根據(jù)實(shí)際存儲的長度自動增長List的長度。

(4) 使用的設(shè)計(jì)模式

抽象類AbstractCollection、AbstractList和AbstractSet分別實(shí)現(xiàn)了Collection、List和Set接口，這就是在Java集合框架中用的很多的適配器設(shè)計(jì)模式，用這些抽象類去實(shí)現(xiàn)接口，在抽象類中實(shí)現(xiàn)接口中的若干或全部方法，這樣下面的一些類只需直接繼承該抽象類，并實(shí)現(xiàn)自己需要的方法即可，而不用實(shí)現(xiàn)接口中的全部抽象方法。

1.2 Map

Map是一個(gè)映射接口，其中的每個(gè)元素都是一個(gè)Key-Value鍵值對，同樣抽象類AbstractMap通過適配器模式實(shí)現(xiàn)了Map接口的大部分函數(shù)，TreeMap、HashMap和WeakHashMap等實(shí)現(xiàn)類都通過繼承AbstractMap來實(shí)現(xiàn)。

1.3 Iterator

Iterator是遍歷集合的迭代器，它可以用來遍歷Collection，但是不能用來遍歷Map。Collection的實(shí)現(xiàn)類都實(shí)現(xiàn)了iterator()函數(shù)，它返回一個(gè)Iterator對象，用來遍歷集合，ListIterator則專門用來遍歷List。而Enumeration則是JDK 1.0時(shí)引入的，作用與Iterator相同，但它的功能比Iterator要少，它只能在Hashtable、Vector和Stack中使用。

1.4 Arrays 和 Collections

Arrays和Collections是用來操作數(shù)組、集合的兩個(gè)工具類，例如在ArrayList和Vector中大量調(diào)用了Arrays.Copyof()方法，而Collections中有很多靜態(tài)方法可以返回各集合類的synchronized版本，即線程安全的版本，當(dāng)然了，如果要用線程安全的集合類，首選concurrent并發(fā)包下的對應(yīng)的集合類。

二、ArrayList

ArrayList是基于一個(gè)能動態(tài)增長的數(shù)組實(shí)現(xiàn)，ArrayList并不是線程安全的，在多線程的情況下可以考慮使用Collections.synchronizedList(List T)函數(shù)返回一個(gè)線程安全的ArrayList類，也可以使用并發(fā)包下的CopyOnWriteArrayList類。

ArrayList<T>類繼承于AbstractList<T>，并實(shí)現(xiàn)了以下四個(gè)接口：

• List<T>
• RandomAccess：支持快速隨機(jī)訪問
• Cloneable：能夠被克隆
• Serializable：支持序列化

ArrayList 的擴(kuò)容

由于ArrayList是基于數(shù)組實(shí)現(xiàn)的，因此當(dāng)我們通過addXX方法向數(shù)組中添加元素之前，都要保證有足夠的空間容納新的元素，這一過程是通過ensureCapacityInternal來實(shí)現(xiàn)的，傳入的參數(shù)為所要求的數(shù)組容量：

• 如果當(dāng)前數(shù)組為空，并且要求的容量小于10，那么將要求的容量設(shè)為10
• 接著嘗試將數(shù)組大小擴(kuò)充為當(dāng)前大小的2.5倍
• 如果仍然無法滿足要求，那么將數(shù)組大小設(shè)為要求的容量
• 如果要求的容量大于預(yù)設(shè)的整型的最大值減8，那么調(diào)用hugeCapacity方法，將數(shù)組的容量設(shè)為整型的最大值
• 最后，調(diào)用Arrays.copyOf將原有數(shù)組中的元素復(fù)制到新的數(shù)組中。

Arrays.copyOf最終會調(diào)用到System.arraycopy()方法。該Native函數(shù)實(shí)際上最終調(diào)用了C語言的memmove()函數(shù)，因此它可以保證同一個(gè)數(shù)組內(nèi)元素的正確復(fù)制和移動，比一般的復(fù)制方法的實(shí)現(xiàn)效率要高很多，很適合用來批量處理數(shù)組，Java強(qiáng)烈推薦在復(fù)制大量數(shù)組元素時(shí)用該方法，以取得更高的效率。

ArrayList 轉(zhuǎn)換為靜態(tài)數(shù)組

ArrayList中提供了兩種轉(zhuǎn)換為靜態(tài)數(shù)組的方法：

• Object[] toArray()
  該方法有可能會拋出java.lang.ClassCastException異常，如果直接用向下轉(zhuǎn)型的方法，將整個(gè)ArrayList集合轉(zhuǎn)變?yōu)橹付愋偷?code>Array數(shù)組，便會拋出該異常。

public class BasicModel {

    public static void main(String[] args) {
        List<Parent> list = new ArrayList<>();
        list.add(new Parent());
        //會拋出異常。
        Parent[] arrays = (Parent[]) list.toArray();
    }

    public static class Parent {}
}

而如果轉(zhuǎn)化為Array數(shù)組時(shí)不向下轉(zhuǎn)型，而是將每個(gè)元素向下轉(zhuǎn)型，則不會拋出該異常，顯然對數(shù)組中的元素一個(gè)個(gè)進(jìn)行向下轉(zhuǎn)型，效率不高，且不太方便。

• T[] toArray(T[] a)
  該方法可以直接將ArrayList轉(zhuǎn)換得到的Array進(jìn)行整體向下轉(zhuǎn)型，且從該方法的源碼中可以看出，參數(shù)a的大小不足時(shí)，內(nèi)部會調(diào)用Arrays.copyOf方法，該方法內(nèi)部創(chuàng)建一個(gè)新的數(shù)組返回，因此對該方法的常用形式如下：

public class BasicModel {

    public static void main(String[] args) {
        List<Parent> list = new ArrayList<>();
        list.add(new Parent());
        //不會拋出異常。
        Parent[] arrays = (Parent[]) list.toArray(new Parent[0]);
    }

    public static class Parent {}
}

元素訪問方式

ArrayList基于數(shù)組實(shí)現(xiàn)，可以通過下標(biāo)索引直接查找到指定位置的元素，因此查找效率高，但每次插入或刪除元素，就要大量地移動元素，插入刪除元素的效率低。

在查找給定元素索引值等的方法中，源碼都將該元素的值分為null和不為null兩種情況處理，ArrayList中允許元素為null。

三、LinkedList

LinkedList是基于雙向循環(huán)鏈表實(shí)現(xiàn)的，除了可以當(dāng)作鏈表來操作外，它還可以當(dāng)作棧，隊(duì)列和雙端隊(duì)列來使用。

LinkedList同樣是非線程安全的，在多線程的情況下可以考慮使用Collections.synchronizedList(List T)函數(shù)返回一個(gè)線程安全的LinkedList類，LinkedList繼承于AbstractSequentialList類，同時(shí)實(shí)現(xiàn)了以下四個(gè)接口：

• List<T>
• Deque和Queue：雙端隊(duì)列
• Cloneable：支持克隆操作
• Serializable：支持序列化

鏈表節(jié)點(diǎn)

LinkedList的實(shí)現(xiàn)是基于雙向循環(huán)鏈表的，且頭結(jié)點(diǎn)voidLink中不存放數(shù)據(jù)，所以它也不存在擴(kuò)容的方法，只需改變節(jié)點(diǎn)的指向即可，每個(gè)鏈表節(jié)點(diǎn)包含該節(jié)點(diǎn)的數(shù)據(jù)，以及前驅(qū)和后繼節(jié)點(diǎn)的引用，其定義如下所示：

    private static final class Link<ET> {
        //該節(jié)點(diǎn)的數(shù)據(jù)。
        ET data;
        //前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)。
        Link<ET> previous, next;
        Link(ET o, Link<ET> p, Link<ET> n) {
            data = o;
            previous = p;
            next = n;
        }
    }

查找和刪除操作

當(dāng)需要根據(jù)位置尋找對應(yīng)節(jié)點(diǎn)的數(shù)據(jù)時(shí)，會先比較待查找位置和鏈表的大小，如果小于一半，那么從頭節(jié)點(diǎn)的后繼節(jié)點(diǎn)開始向后尋找，反之則從頭結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)開始往前尋找，因此對于查找操作來說，它的效率很低，但是向頭尾節(jié)點(diǎn)插入和刪除數(shù)據(jù)的效率較高。

四、Vector

Vector也是基于數(shù)組實(shí)現(xiàn)的，其容量能夠動態(tài)增長。它的許多實(shí)現(xiàn)方法都加入了同步語句，因此是 線程安全 的。

Vector繼承于AbstractList類，并且實(shí)現(xiàn)了下面四個(gè)接口：

• List<E>
• RandomAccess：支持隨機(jī)訪問
• Cloneable, java.io.Serializable：支持Clone和序列化。

Vector的實(shí)現(xiàn)大體和ArrayList類似，它有以下幾個(gè)特點(diǎn)：

• Vector有四個(gè)不同的構(gòu)造方法，無參構(gòu)造方法的容量為默認(rèn)值10，僅包含容量的構(gòu)造方法則將容量增長量置為0。
• 當(dāng)Vector的容量不足以容納新的元素時(shí)，將進(jìn)行擴(kuò)容操作。首先判斷容量增長值是否為0，如果為0，那么就將新容量設(shè)為舊容量的兩倍，否則就設(shè)置新容量為舊容量加上容量增長值。假如新容量還不夠，那么就直接設(shè)置新量容量為傳入的參數(shù)。
• 在存入和讀取元素時(shí)，會根據(jù)元素值是否為null進(jìn)行處理，也就是說，Vector允許元素為null。

五、HashSet

HashSet具有以下特點(diǎn)：

• 不能保證元素的排列順序，順序有可能發(fā)生變化
• 不是同步的
• 集合元素可以是null，但只能放入一個(gè)null

當(dāng)向HashSet集合中存入一個(gè)元素時(shí)，HashSet會調(diào)用該對象的hashCode()方法來得到該對象的hashCode值，然后根據(jù)hashCode值來決定該對象在HashSet中存儲位置。
簡單的說，HashSet集合判斷兩個(gè)元素相等的標(biāo)準(zhǔn)是兩個(gè)對象通過equals方法比較相等，并且兩個(gè)對象的hashCode()方法返回值相等。

注意，如果要把一個(gè)對象放入HashSet中，重寫該對象對應(yīng)類的equals方法，也應(yīng)該重寫其hashCode()方法。其規(guī)則是如果兩個(gè)對象通過equals方法比較返回true時(shí)，其hashCode也應(yīng)該相同。另外，對象中用作equals比較標(biāo)準(zhǔn)的屬性，都應(yīng)該用來計(jì)算hashCode的值。

六、TreeSet

TreeSet是SortedSet接口的唯一實(shí)現(xiàn)類，TreeSet可以確保集合元素處于排序狀態(tài)。TreeSet支持兩種排序方式，自然排序 和 定制排序，其中自然排序?yàn)槟J(rèn)的排序方式。

TreeSet 的兩種排序方式

向TreeSet中加入的應(yīng)該是同一個(gè)類的對象。TreeSet判斷兩個(gè)對象不相等的方式是兩個(gè)對象通過equals方法返回false，或者通過CompareTo方法比較沒有返回0。

自然排序

自然排序使用要排序元素的CompareTo(Object obj)方法來比較元素之間大小關(guān)系，然后將元素按照升序排列。
Java提供了一個(gè)Comparable接口，該接口里定義了一個(gè)compareTo(Object obj)方法，該方法返回一個(gè)整數(shù)值，實(shí)現(xiàn)了該接口的對象就可以比較大小。

obj1.compareTo(obj2)方法如果返回0，則說明被比較的兩個(gè)對象相等，如果返回一個(gè)正數(shù)，則表明obj1大于obj2，如果是負(fù)數(shù)，則表明obj1小于obj2。如果我們將兩個(gè)對象的equals方法總是返回true，則這兩個(gè)對象的compareTo方法返回應(yīng)該返回0.

定制排序

自然排序是根據(jù)集合元素的大小，以升序排列，如果要定制排序，應(yīng)該使用Comparator接口，實(shí)現(xiàn)int compare(T o1,T o2)方法。

• TreeSet是二叉樹實(shí)現(xiàn)的，Treeset中的數(shù)據(jù)是自動排好序的，不允許放入null值。
• HashSet是哈希表實(shí)現(xiàn)的，HashSet中的數(shù)據(jù)是無序的，可以放入null，但只能放入一個(gè)null，兩者中的值都不能重復(fù)，就如數(shù)據(jù)庫中唯一約束。
• HashSet要求放入的對象必須實(shí)現(xiàn)hashCode()方法，放入的對象，是以hashcode()碼作為標(biāo)識的，而具有相同內(nèi)容的String對象，hashcode是一樣，所以放入的內(nèi)容不能重復(fù)。但是同一個(gè)類的對象可以放入不同的實(shí)例 。

七、HashMap

HashMap是基于哈希表實(shí)現(xiàn)的，每一個(gè)元素都是一個(gè)key-value對，其內(nèi)部通過單鏈表解決沖突問題，容量不足時(shí)，同樣會自動增長。HashMap是非線程安全的，只是用于單線程環(huán)境下，多線程環(huán)境下可以采用并發(fā)包下的ConcurrentHashMap。

HashMap繼承于AbstractMap，同時(shí)實(shí)現(xiàn)了Cloneable和Serializable接口，因此，它支持克隆和序列化。

HashMap 的整體結(jié)構(gòu)

HashMap是基于數(shù)組和鏈表來實(shí)現(xiàn)的：

• 首先根據(jù)Key的hashCode方法，計(jì)算出在數(shù)組中的坐標(biāo)。

//計(jì)算 Key 的 hash 值。
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
//根據(jù) Key 的 hash 值和鏈表的長度來計(jì)算下標(biāo)。
int i = indexFor(hash, table.length);

• 判斷在數(shù)組的當(dāng)前位置是否已經(jīng)有元素，如果沒有，那么就將Key/Value封裝成HashMapEntry數(shù)據(jù)結(jié)構(gòu)，并將其作為數(shù)組在該位置上的元素。否則就先從頭節(jié)點(diǎn)開始遍歷該鏈表，如果 滿足下面的兩個(gè)條件，那么就替換鏈表該節(jié)點(diǎn)的Value

//Value 替換的條件
//條件1：hash 值完全相同
//條件2：key 指向同一塊內(nèi)存地址 或者 key 的 equals 方法返回為 true
(e.hash == hash && ((k = e.key) == key || key.equals(k)))

• 遍歷完整個(gè)鏈表都沒有找到可替代的節(jié)點(diǎn)，那么將這個(gè)新的HashMapEntry作為鏈表的頭節(jié)點(diǎn)，并且也是數(shù)組在該位置上的元素，原先的頭節(jié)點(diǎn)則作為它的后繼節(jié)點(diǎn)。

HashMapEntry 的數(shù)據(jù)結(jié)構(gòu)

HashMapEntry的定義如下：

static class HashMapEntry<K,V> implements Map.Entry<K,V> {
        //Key
        final K key;
        //Value
        V value;
        //后繼節(jié)點(diǎn)。
        HashMapEntry<K,V> next;
        //如果 Key 不為 null ，那么就是它的哈希值，否則為0。
        int hash;
        //....
}

元素寫入

在第一小節(jié)中，我們簡要的計(jì)算了HashMap的整體結(jié)構(gòu)，由此我們可以推斷出在設(shè)計(jì)的時(shí)候應(yīng)當(dāng)盡可能地使元素均勻分布，使得數(shù)組每個(gè)位置上的鏈表盡可能地短，避免從鏈表頭結(jié)點(diǎn)開始遍歷的過程。

而元素是否分布均勻就取決于根據(jù)Key的Hash值計(jì)算數(shù)組下標(biāo)的過程，首先我們看一下Hash值的計(jì)算，這里首先調(diào)用對象的hashCode方法，再通過二次Hash算法獲得一個(gè)Hash值：

    public static int secondaryHash(Object key) {
        return secondaryHash(key.hashCode());
    }

    private static int secondaryHash(int h) {
        h += (h <<  15) ^ 0xffffcd7d;
        h ^= (h >>> 10);
        h += (h <<   3);
        h ^= (h >>>  6);
        h += (h <<   2) + (h << 14);
        return h ^ (h >>> 16);
    }

之后，再通過這個(gè)計(jì)算出來Hash值 與上當(dāng)前數(shù)組長度減一 進(jìn)行取余，獲得對應(yīng)的數(shù)組下標(biāo)：

hash & (tab.length - 1)

由于HashMap在擴(kuò)容的時(shí)候，保證了數(shù)組的長度始終為2的n冪，因此length - 1的二進(jìn)制表示始終為全1，因此進(jìn)行&操作的結(jié)果既保證了最終的結(jié)果不會超過數(shù)組的長度范圍，同時(shí)也保證了兩個(gè)Hash值相同的元素不會映射到數(shù)組的同一位置，再加上上面二次Hash的過程加上了高位的計(jì)算優(yōu)化，從而使得數(shù)據(jù)的分布盡可能地平均。

元素讀取

理解了上面存儲的過程，讀取自然也就很好理解了，其實(shí)通過Key計(jì)算數(shù)組下標(biāo)，遍歷該位置上數(shù)組元素的鏈表進(jìn)行查找的過程。

擴(kuò)容

當(dāng)HashMap中的元素越來越多的時(shí)候，hash沖突的幾率也就越來越高，因?yàn)閿?shù)組的長度是固定的，所以為了提高查詢的效率，就要對HashMap的數(shù)組進(jìn)行擴(kuò)容。

當(dāng)HashMap中的元素個(gè)數(shù)超過數(shù)組大小 * loadFactor時(shí)，loadFactor的默認(rèn)值為0.75，就會進(jìn)行數(shù)組擴(kuò)容，擴(kuò)容后的大小為原先的2倍，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置，原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置，并放進(jìn)去。

擴(kuò)容是一個(gè)相當(dāng)耗費(fèi)性能的操作，因此如果我們已經(jīng)預(yù)知HashMap中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高HashMap的性能。

Fail-Fast 機(jī)制

HashMap并不是線程安全的，因此如果在使用迭代器的過程中有其他線程修改了map，那么將拋出ConcurrentModificationException，這就是所謂fail-fast策略。

這一策略在源碼中的實(shí)現(xiàn)是通過modCount域，modCount顧名思義就是修改次數(shù)，對HashMap內(nèi)容的修改都將增加這個(gè)值，那么在迭代器初始化過程中會將這個(gè)值賦給迭代器的expectedModCount。

在迭代過程中，判斷modCount跟expectedModCount是否相等，如果不相等就表示已經(jīng)有其他線程修改了Map，那么就會通過下面的方法拋出異常：

    HashMapEntry<K, V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
           //省略...
    }

modCount聲明為volatile，保證了多線程情況下的內(nèi)存可見性。

在迭代器創(chuàng)建之后，如果從結(jié)構(gòu)上對映射進(jìn)行修改，除非通過迭代器本身的remove方法，其他任何時(shí)間任何方式的修改，迭代器都將拋出ConcurrentModificationException。因此，面對并發(fā)的修改，迭代器很快就會完全失敗，而不保證在將來不確定的時(shí)間發(fā)生任意不確定行為的風(fēng)險(xiǎn)

八、HashTable

HashTable經(jīng)常用來和HashMap進(jìn)行比較，前者是線程安全的，而后者則不是，其實(shí)HashTable要比HashMap出現(xiàn)得要早，它實(shí)現(xiàn)線程安全的原理并沒有什么高級的地方，只不過是在寫入和讀取時(shí)加上了synchronized關(guān)鍵字用于同步，并且也不推薦使用了，因?yàn)樵诓l(fā)包中提供了更好的解決方案ConcurrentHashMap，它內(nèi)部的實(shí)現(xiàn)比較復(fù)雜，之后我們再通過一篇文章進(jìn)行分析。

這里簡單地總結(jié)一下它和HashMap之間的區(qū)別：

• HashTable基于Dictionary類，而HashMap是基于AbstractMap。Dictionary是任何可將鍵映射到相應(yīng)值的類的抽象父類，而AbstractMap基于 Map接口的實(shí)現(xiàn)，它以最大限度地減少實(shí)現(xiàn)此接口所需的工作。
• HashMap的key和value都允許為null，而Hashtable的key和value都不允許為null。HashMap遇到key為null的時(shí)候，調(diào)用putForNullKey方法進(jìn)行處理，而對value沒有處理，Hashtable遇到null，直接返回 NullPointerException。
• Hashtable方法是同步，而HashMap則不是。我們可以看一下源碼，Hashtable中的幾乎所有的public的方法都是synchronized的，而有些方法也是在內(nèi)部通過synchronized代碼塊來實(shí)現(xiàn)。所以有人一般都建議如果是涉及到多線程同步時(shí)采用HashTable，沒有涉及就采用HashMap，但是在 Collections類中存在一個(gè)靜態(tài)方法：synchronizedMap()，該方法創(chuàng)建了一個(gè)線程安全的Map對象，并把它作為一個(gè)封裝的對象來返回。

九、TreeMap

TreeMap是一個(gè)有序的key-value集合，它是通過 紅黑樹 實(shí)現(xiàn)的。TreeMap繼承于AbstractMap，所以它是一個(gè)Map，即一個(gè)key-value集合。TreeMap實(shí)現(xiàn)了NavigableMap接口，意味著它支持一系列的導(dǎo)航方法，比如返回有序的key集合。TreeMap實(shí)現(xiàn)了Cloneable和Serializable接口，意味著它可以被Clone和序列化。

TreeMap基于紅黑樹實(shí)現(xiàn)，該映射根據(jù)其鍵的自然順序進(jìn)行排序，或者根據(jù)創(chuàng)建映射時(shí)提供的 Comparator進(jìn)行排序，具體取決于使用的構(gòu)造方法。TreeMap的基本操作containsKey、get、put和remove的時(shí)間復(fù)雜度是log(n) ，另外，TreeMap是非同步的， 它的iterator方法返回的迭代器是Fail-Fastl的。

十、LinkedHashMap

• LinkedHashMap是HashMap的子類，與HashMap有著同樣的存儲結(jié)構(gòu)，但它加入了一個(gè)雙向鏈表的頭結(jié)點(diǎn)，將所有put到LinkedHashmap的節(jié)點(diǎn)一一串成了一個(gè)雙向循環(huán)鏈表，因此它保留了節(jié)點(diǎn)插入的順序，可以使節(jié)點(diǎn)的輸出順序與輸入順序相同。
• LinkedHashMap可以用來實(shí)現(xiàn)LRU算法。
• LinkedHashMap同樣是非線程安全的，只在單線程環(huán)境下使用。

十一、LinkedHashSet

LinkedHashSet是具有可預(yù)知迭代順序的Set接口的哈希表和鏈接列表實(shí)現(xiàn)。此實(shí)現(xiàn)與HashSet的不同之處在于，后者維護(hù)著一個(gè)運(yùn)行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序可為插入順序或是訪問順序。

LinkedHashSet的實(shí)現(xiàn)：對于LinkedHashSet而言，它繼承與HashSet、又基于LinkedHashMap來實(shí)現(xiàn)的。