List接口與其實(shí)現(xiàn)類
List類似于數(shù)組刹勃，可以通過索引來訪問元素，實(shí)現(xiàn)該接口的常用類有ArrayList埃碱、LinkedList猖辫、Vector、Stack等砚殿。
ArrayList
ArrayList是動態(tài)數(shù)組啃憎，可以根據(jù)插入的元素的數(shù)量自動擴(kuò)容，而使用者不需要知道其內(nèi)部是什么時候進(jìn)行擴(kuò)展的似炎，把它當(dāng)作足夠容量的數(shù)組來使用即可辛萍。
ArrayList訪問元素的方法get是常數(shù)時間，因?yàn)槭侵苯痈鶕?jù)下標(biāo)索引來訪問的羡藐，而add方法的時間復(fù)雜度是O(n)贩毕，因?yàn)樾枰苿釉兀瑢⑿略夭迦氲胶线m的位置传睹。
ArrayList是非線程安全的耳幢，即它沒有同步，不過欧啤，可以通過Collections.synchronizedList()靜態(tài)方法返回一個同步的實(shí)例睛藻，如：
List synList = Collections.synchronizedList(list);
數(shù)組擴(kuò)容：ArrayList在插入元素的時候，都會檢查當(dāng)前的數(shù)組大小是否足夠邢隧，如果不夠店印，將會擴(kuò)容到當(dāng)前容量 * 1.5 + 1（加1是為了當(dāng)前容量為1時，也能擴(kuò)展到2）倒慧，即把原來的元素全部復(fù)制到一個兩倍大小的新數(shù)組按摘，將舊的數(shù)組拋棄掉(等待垃圾回收)，這個操作是比較耗時纫谅，因此建議在創(chuàng)建ArrayList的時候炫贤，根據(jù)要插入的元素的數(shù)量來初步估計Capacity，并初始化ArrayList付秕，如：
ArrayList list = new ArrayList(100);
這樣兰珍，在插入小于100個元素的時候都是不需要進(jìn)行擴(kuò)容的，能夠帶來性能的提升询吴，當(dāng)然掠河，如果對這個容量估計大了，可能會帶來一些空間的損耗猛计。
LinkedList
LinkedList也實(shí)現(xiàn)了List接口唠摹，其內(nèi)部實(shí)現(xiàn)是使用雙向鏈表來保存元素，因此插入與刪除元素的性能都表現(xiàn)不錯奉瘤。它還提供了一些其它操作方法勾拉，如在頭部、尾部插入或者刪除元素，因此望艺，可以用它來實(shí)現(xiàn)棧苛秕、隊列、雙向隊列找默。
由于是使用鏈表保存元素的，所以隨機(jī)訪問元素的時候速度會比較慢(需要遍歷鏈表找到目標(biāo)元素)吼驶，這一點(diǎn)相比ArrayList的隨機(jī)訪問要差惩激，ArrayList是采用數(shù)組實(shí)現(xiàn)方式，直接使用下標(biāo)可以訪問到元素而不需要遍歷蟹演。因此风钻，在需要頻繁隨機(jī)訪問元素的情況下，建議使用ArrayList酒请。
與ArrayList一樣骡技，LinkedList也是非同步的，如果需要實(shí)現(xiàn)多線程訪問羞反，則需要自己在外部實(shí)現(xiàn)同步方法布朦。當(dāng)然也可以使用Collections.synchronizedList()靜態(tài)方法。
Vector
Vector是ArrayList的線程同步版本昼窗，即是說Vector是同步的是趴，支持多線程訪問。除此之外澄惊，還有一點(diǎn)不同時唆途，當(dāng)容量不夠時，Vector默認(rèn)擴(kuò)展一倍容量掸驱，而ArrayList是當(dāng)前容量 * 1.5 + 1
Stack
Stack是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)肛搬，繼承自Vector類，提供了push毕贼、pop温赔、peek（獲得棧頂元素）等方法。
Set接口
Set是不能包含重合元素的容器帅刀，其實(shí)現(xiàn)類有HashSet让腹，繼承于它的接口有SortedSet接口等。Set中提供了加扣溺、減骇窍、和交等集合操作函數(shù)。Set不能按照索引隨機(jī)訪問元素锥余，這是它與List的一個重要區(qū)別腹纳。
HashSet
HashSet實(shí)現(xiàn)了Set接口，其內(nèi)部是采用HashMap實(shí)現(xiàn)的。放入HashSet的對象最好重寫hashCode嘲恍、equals方法足画，因?yàn)槟J(rèn)的這兩個方法很可能與你的業(yè)務(wù)邏輯是不一致的，而且佃牛，要同時重寫這兩個函數(shù)淹辞，如果只重寫其中一個，很容易發(fā)生意想不到的問題俘侠。
記住下面幾條規(guī)則：
- 相等對象象缀，hashCode一定相等。
- 不等對象爷速，hashCode不一定不相等央星。
- 兩個對象的hashCode相同，不一定相等惫东。
- 兩個對象的hashCode不同莉给，一定不相等。
TreeSet
TreeSet同樣的Set接口的實(shí)現(xiàn)類廉沮，同樣不能存放相同的對象颓遏。它與HashSet不同的是，TreeSet的元素是按照順序排列的废封，因此用TreeSet存放的對象需要實(shí)現(xiàn)Comparable接口州泊。
Map接口
Map集合提供了按照“鍵值對”存儲元素的方法，一個鍵唯一映射一個值漂洋。集合中“鍵值對”整體作為一個實(shí)體元素時遥皂，類似List集合，但是如果分開來年刽漂，Map是一個兩列元素的集合：鍵是一列演训，值是一列。與Set集合一樣贝咙，Map也沒有提供隨機(jī)訪問的能力样悟，只能通過鍵來訪問對應(yīng)的值。
Map的每一個元素都是一個Map.Entry庭猩，這個實(shí)體的結(jié)構(gòu)是< Key, Value >樣式窟她。
HashMap
HashMap實(shí)現(xiàn)了Map接口，但它是非線程安全的蔼水。HashMap允許key值為null震糖，value也可以為null。
Hashtable
Hashtable也是Map的實(shí)現(xiàn)類趴腋，繼承自Dictionary類吊说。它與HashMap不同的是论咏，它是線程安全的。而且它不允許key為null颁井，value也不能為null厅贪。
由于它是線程安全的，在效率上稍差于HashMap雅宾。
List總結(jié)
ArrayList內(nèi)部實(shí)現(xiàn)采用動態(tài)數(shù)組养涮，當(dāng)容量不夠時，自動擴(kuò)容至（當(dāng)前容量1.5+1）秀又。元素的順序按照插入的順序排列单寂。默認(rèn)初始容量為10。
contains復(fù)雜度為O(n)吐辙，add復(fù)雜度為分?jǐn)偟某?shù)，即添加n個元素需要O(n)時間蘸劈，remove為O(n)昏苏，get復(fù)雜度為O(1)
隨機(jī)訪問效率高，隨機(jī)插入威沫、刪除效率低贤惯。ArrayList是非線程安全*的。
LinkedList內(nèi)部使用雙向鏈表實(shí)現(xiàn)棒掠，隨機(jī)訪問效率低孵构，隨機(jī)插入、刪除效率高烟很【笔可以當(dāng)作堆棧、隊列雾袱、雙向隊列來使用恤筛。LinkedList也是非線程安全的。
Vector跟ArrayList是類似的芹橡，內(nèi)部實(shí)現(xiàn)也是動態(tài)數(shù)組毒坛，隨機(jī)訪問效率高。Vector是線程安全的林说。
Stack是棧煎殷，繼承于Vector，其各種操作也是基于Vector的各種操作腿箩，因此其內(nèi)部實(shí)現(xiàn)也是動態(tài)數(shù)組豪直，先進(jìn)后出。Stack是線程安全的度秘。
List使用場景
- 對于需要快速插入顶伞、刪除元素饵撑，應(yīng)該使用LinkedList
- 對于需要快速隨機(jī)訪問元素，應(yīng)該使用ArrayList
- 如果List需要被多線程操作唆貌，應(yīng)該使用Vector滑潘，如果只會被單線程操作，應(yīng)該使用ArrayList
Set總結(jié)
HashSet內(nèi)部是使用HashMap實(shí)現(xiàn)的锨咙，HashSet的key值是不允許重復(fù)的语卤，如果放入的對象是自定義對象，那么最好能夠同時重寫hashCode與equals函數(shù)酪刀，這樣就能自定義添加的對象在什么樣的情況下是一樣的粹舵，即能保證在業(yè)務(wù)邏輯下能添加對象到HashSet中，保證業(yè)務(wù)邏輯的正確性骂倘。另外眼滤，HashSet里的元素不是按照順序存儲的。HashSet是非線程安全的历涝。
TreeSet存儲的元素是按順序存儲的诅需，如果是存儲的元素是自定義對象，那么需要實(shí)現(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);
}
擴(kuò)展容量不同： Hashtable中hash數(shù)組默認(rèn)大小是11，增加的方式是 old*2+1芥挣。HashMap中hash數(shù)組的默認(rèn)大小是16驱闷，而且一定是2的指數(shù)空免。
