List接口與其實現(xiàn)類

List類似于數(shù)組，可以通過索引來訪問元素，實現(xiàn)該接口的常用類有ArrayList、LinkedList、Vector、Stack等。

ArrayList

ArrayList是動態(tài)數(shù)組，可以根據(jù)插入的元素的數(shù)量自動擴容，而使用者不需要知道其內(nèi)部是什么時候進行擴展的，把它當(dāng)作足夠容量的數(shù)組來使用即可。
ArrayList訪問元素的方法get是常數(shù)時間，因為是直接根據(jù)下標索引來訪問的，而add方法的時間復(fù)雜度是O(n)，因為需要移動元素，將新元素插入到合適的位置。
ArrayList是非線程安全的，即它沒有同步，不過，可以通過Collections.synchronizedList()靜態(tài)方法返回一個同步的實例，如：

List synList = Collections.synchronizedList(list);

數(shù)組擴容：ArrayList在插入元素的時候，都會檢查當(dāng)前的數(shù)組大小是否足夠，如果不夠，將會擴容到當(dāng)前容量 * 1.5 + 1（加1是為了當(dāng)前容量為1時，也能擴展到2），即把原來的元素全部復(fù)制到一個兩倍大小的新數(shù)組，將舊的數(shù)組拋棄掉(等待垃圾回收)，這個操作是比較耗時，因此建議在創(chuàng)建ArrayList的時候，根據(jù)要插入的元素的數(shù)量來初步估計Capacity，并初始化ArrayList，如：

ArrayList list = new ArrayList(100);

這樣，在插入小于100個元素的時候都是不需要進行擴容的，能夠帶來性能的提升，當(dāng)然，如果對這個容量估計大了，可能會帶來一些空間的損耗。

LinkedList

LinkedList也實現(xiàn)了List接口，其內(nèi)部實現(xiàn)是使用雙向鏈表來保存元素，因此插入與刪除元素的性能都表現(xiàn)不錯。它還提供了一些其它操作方法，如在頭部、尾部插入或者刪除元素，因此，可以用它來實現(xiàn)棧、隊列、雙向隊列。
由于是使用鏈表保存元素的，所以隨機訪問元素的時候速度會比較慢(需要遍歷鏈表找到目標元素)，這一點相比ArrayList的隨機訪問要差，ArrayList是采用數(shù)組實現(xiàn)方式，直接使用下標可以訪問到元素而不需要遍歷。因此，在需要頻繁隨機訪問元素的情況下，建議使用ArrayList。
與ArrayList一樣，LinkedList也是非同步的，如果需要實現(xiàn)多線程訪問，則需要自己在外部實現(xiàn)同步方法。當(dāng)然也可以使用Collections.synchronizedList()靜態(tài)方法。

Vector

Vector是ArrayList的線程同步版本，即是說Vector是同步的，支持多線程訪問。除此之外，還有一點不同時，當(dāng)容量不夠時，Vector默認擴展一倍容量，而ArrayList是當(dāng)前容量 * 1.5 + 1

Stack

Stack是一種后進先出的數(shù)據(jù)結(jié)構(gòu)，繼承自Vector類，提供了push、pop、peek（獲得棧頂元素）等方法。

Set接口

Set是不能包含重合元素的容器，其實現(xiàn)類有HashSet，繼承于它的接口有SortedSet接口等。Set中提供了加、減、和交等集合操作函數(shù)。Set不能按照索引隨機訪問元素，這是它與List的一個重要區(qū)別。

HashSet

HashSet實現(xiàn)了Set接口，其內(nèi)部是采用HashMap實現(xiàn)的。放入HashSet的對象最好重寫hashCode、equals方法，因為默認的這兩個方法很可能與你的業(yè)務(wù)邏輯是不一致的，而且，要同時重寫這兩個函數(shù)，如果只重寫其中一個，很容易發(fā)生意想不到的問題。
記住下面幾條規(guī)則：

• 相等對象，hashCode一定相等。
• 不等對象，hashCode不一定不相等。
• 兩個對象的hashCode相同，不一定相等。
• 兩個對象的hashCode不同，一定不相等。

TreeSet

TreeSet同樣的Set接口的實現(xiàn)類，同樣不能存放相同的對象。它與HashSet不同的是，TreeSet的元素是按照順序排列的，因此用TreeSet存放的對象需要實現(xiàn)Comparable接口。

Map接口

Map集合提供了按照“鍵值對”存儲元素的方法，一個鍵唯一映射一個值。集合中“鍵值對”整體作為一個實體元素時，類似List集合，但是如果分開來年，Map是一個兩列元素的集合：鍵是一列，值是一列。與Set集合一樣，Map也沒有提供隨機訪問的能力，只能通過鍵來訪問對應(yīng)的值。
Map的每一個元素都是一個Map.Entry，這個實體的結(jié)構(gòu)是< Key, Value >樣式。

HashMap

HashMap實現(xiàn)了Map接口，但它是非線程安全的。HashMap允許key值為null，value也可以為null。

Hashtable

Hashtable也是Map的實現(xiàn)類，繼承自Dictionary類。它與HashMap不同的是，它是線程安全的。而且它不允許key為null，value也不能為null。
由于它是線程安全的，在效率上稍差于HashMap。

List總結(jié)

ArrayList內(nèi)部實現(xiàn)采用動態(tài)數(shù)組，當(dāng)容量不夠時，自動擴容至（當(dāng)前容量1.5+1）。元素的順序按照插入的順序排列。默認初始容量為10。
contains復(fù)雜度為O(n)，add復(fù)雜度為分攤的常數(shù)，即添加n個元素需要O(n)時間，remove為O(n)，get復(fù)雜度為O(1)
隨機訪問效率高，隨機插入、刪除效率低。ArrayList是非線程安全*的。

LinkedList內(nèi)部使用雙向鏈表實現(xiàn)，隨機訪問效率低，隨機插入、刪除效率高。可以當(dāng)作堆棧、隊列、雙向隊列來使用。LinkedList也是非線程安全的。

Vector跟ArrayList是類似的，內(nèi)部實現(xiàn)也是動態(tài)數(shù)組，隨機訪問效率高。Vector是線程安全的。

Stack是棧，繼承于Vector，其各種操作也是基于Vector的各種操作，因此其內(nèi)部實現(xiàn)也是動態(tài)數(shù)組，先進后出。Stack是線程安全的。

List使用場景

• 對于需要快速插入、刪除元素，應(yīng)該使用LinkedList
• 對于需要快速隨機訪問元素，應(yīng)該使用ArrayList
• 如果List需要被多線程操作，應(yīng)該使用Vector，如果只會被單線程操作，應(yīng)該使用ArrayList

Set總結(jié)

HashSet內(nèi)部是使用HashMap實現(xiàn)的，HashSet的key值是不允許重復(fù)的，如果放入的對象是自定義對象，那么最好能夠同時重寫hashCode與equals函數(shù)，這樣就能自定義添加的對象在什么樣的情況下是一樣的，即能保證在業(yè)務(wù)邏輯下能添加對象到HashSet中，保證業(yè)務(wù)邏輯的正確性。另外，HashSet里的元素不是按照順序存儲的。HashSet是非線程安全的。

TreeSet存儲的元素是按順序存儲的，如果是存儲的元素是自定義對象，那么需要實現(xiàn)Comparable接口。TreeSet也是非線程安全的。

LinkedHashSet繼承自HashSet，它與HashSet不同的是，LinkedHashSet存儲元素的順序是按照元素的插入順序存儲的。LinkedHashSet也是非線程安全的。

Map總結(jié)

HashMap存儲鍵值對。當(dāng)程序試圖將一個key-value對放入 HashMap 中時，程序首先根據(jù)該key的hashCode()返回值決定該Entry的存儲位置：如果兩個Entry的key的hashCode() 返回值相同，那它們的存儲位置相同。如果這兩個Entry的key通過equals比較返回true，新添加Entry的value將覆蓋集合中原有Entry的 value，但key不會覆蓋。如果這兩個Entry的key通過equals 比較返回false，新添加的Entry將與集合中原有Entry形成Entry 鏈，而且新添加的 Entry 位于 Entry 鏈的頭部。看下面HashMap添加鍵值對的源代碼：

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

HashMap允許key、value值為null。HashMap是非線程安全的。

Hashtable是HashMap的線程安全版本。而且，key、value都不允許為null。

哈希值的使用不同: Hashtable直接使用對象的hashCode，如下代碼：

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

而HashMap重新計算hash值，如下代碼：

int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
    return h & (length-1);
}

擴展容量不同： Hashtable中hash數(shù)組默認大小是11，增加的方式是 old*2+1。HashMap中hash數(shù)組的默認大小是16，而且一定是2的指數(shù)。