** 1.泛型和類型安全的容器**
ArrayList，可以自動擴(kuò)充大小的數(shù)組，add插入對象少态，get訪問對象，size查看對象數(shù)目易遣。
class Apple{}
public class Box {
public static void main(String[] args) {
ArrayList<Apple> a = new ArrayList<Apple>();
for(int i = 0; i < 10000; i++){
a.add(i);
}
}
}
像上面添加10000條數(shù)據(jù)彼妻，數(shù)組會自動擴(kuò)充大小，看源碼
@Override public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
if (s < a.length) {
System.arraycopy(a, index, a, index + 1, s - index);
} else {
// assert s == a.length;
//由于原數(shù)組長度不能變化豆茫，這里新建數(shù)組實現(xiàn)擴(kuò)容
Object[] newArray = new Object[newCapacity(s)];
//將原數(shù)組數(shù)據(jù)拷貝到新數(shù)組
System.arraycopy(a, 0, newArray, 0, index);
//將需要添加的元素添加到index + 1的位置
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
a[index] = object;
size = s + 1;
modCount++;
}
//返回新數(shù)組的長度
private static int newCapacity(int currentCapacity) {
//默認(rèn)MIN_CAPACITY_INCREMENT =12
int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
return currentCapacity + increment;
}
泛型的添加可以在編譯期間防止將錯誤類型的對象放進(jìn)容器中侨歉。
2.容器分類
觀察上圖，我們可以得出容器主要分為兩種類型揩魂，兩個接口Collection與Map定義了兩類不同的對象存儲方式幽邓。
**Collection接口 **
Collection是最基本的集合接口，一個Collection代表一組Object火脉，即Collection的元素（Elements）牵舵。一些 Collection允許相同的元素而另一些不行柒啤。一些能排序而另一些不行。Java SDK不提供直接繼承自Collection的類棋枕，Java SDK提供的類都是繼承自Collection的“子接口”如List和Set白修。
所有實現(xiàn)Collection接口的類都必須提供兩個標(biāo)準(zhǔn)的構(gòu)造函數(shù)：無參數(shù)的構(gòu)造函數(shù)用于創(chuàng)建一個空的Collection，有一個 Collection參數(shù)的構(gòu)造函數(shù)用于創(chuàng)建一個新的Collection重斑，這個新的Collection與傳入的Collection有相同的元素兵睛。后一個構(gòu)造函數(shù)允許用戶復(fù)制一個Collection。
如何遍歷Collection中的每一個元素窥浪？不論Collection的實際類型如何祖很，它都支持一個iterator()的方法，該方法返回一個迭代子漾脂，使用該迭代子即可逐一訪問Collection中每一個元素假颇。典型的用法如下：
Iterator it = collection.iterator(); // 獲得一個迭代子
while(it.hasNext()) {
Object obj = it.next(); // 得到下一個元素
}
由Collection接口派生的兩個接口是List和Set。
**List接口 **
List是有序的Collection骨稿，使用此接口能夠精確的控制每個元素插入的位置笨鸡。用戶能夠使用索引（元素在List中的位置，類似于數(shù)組下標(biāo)）來訪問List中的元素坦冠，這類似于Java的數(shù)組形耗。
和下面要提到的Set不同，List允許有相同的元素辙浑。
除了具有Collection接口必備的iterator()方法外激涤，List還提供一個listIterator()方法，返回一個 ListIterator接口判呕，和標(biāo)準(zhǔn)的Iterator接口相比倦踢，ListIterator多了一些add()之類的方法，允許添加侠草，刪除辱挥，設(shè)定元素，還能向前或向后遍歷梦抢。
實現(xiàn)List接口的常用類有LinkedList般贼，ArrayList，Vector和Stack奥吩。
**LinkedList類 **
LinkedList實現(xiàn)了List接口，允許null元素蕊梧。此外LinkedList提供額外的get霞赫，remove，insert方法在 LinkedList的首部或尾部肥矢。這些操作使LinkedList可被用作堆棧（stack）端衰，隊列（queue）或雙向隊列（deque）叠洗。
注意LinkedList沒有同步方法。如果多個線程同時訪問一個List旅东，則必須自己實現(xiàn)訪問同步灭抑。一種解決方法是在創(chuàng)建List時構(gòu)造一個同步的List：
List list = Collections.synchronizedList(new LinkedList(...));
**ArrayList類 **
ArrayList實現(xiàn)了可變大小的數(shù)組。它允許所有元素抵代，包括null腾节。ArrayList沒有同步。
size荤牍，isEmpty案腺，get，set方法運(yùn)行時間為常數(shù)康吵。但是add方法開銷為分?jǐn)偟某?shù)劈榨，添加n個元素需要O(n)的時間。其他的方法運(yùn)行時間為線性晦嵌。
每個ArrayList實例都有一個容量（Capacity）同辣，即用于存儲元素的數(shù)組的大小。這個容量可隨著不斷添加新元素而自動增加惭载，但是增長算法并沒有定義旱函。當(dāng)需要插入大量元素時，在插入前可以調(diào)用ensureCapacity方法來增加ArrayList的容量以提高插入效率棕兼。
和LinkedList一樣陡舅，ArrayList也是非同步的（unsynchronized）。
**Vector類 **
Vector非常類似ArrayList伴挚，但是Vector是同步的靶衍。由Vector創(chuàng)建的Iterator，雖然和ArrayList創(chuàng)建的 Iterator是同一接口茎芋，但是颅眶，因為Vector是同步的，當(dāng)一個Iterator被創(chuàng)建而且正在被使用田弥，另一個線程改變了Vector的狀態(tài)（例如涛酗，添加或刪除了一些元素），這時調(diào)用Iterator的方法時將拋出ConcurrentModificationException偷厦，因此必須捕獲該異常商叹。
**Stack 類 **
Stack繼承自Vector，實現(xiàn)一個后進(jìn)先出的堆棧只泼。Stack提供5個額外的方法使得Vector得以被當(dāng)作堆棧使用剖笙。基本的push和pop 方法请唱，還有peek方法得到棧頂?shù)脑孛诌洌琫mpty方法測試堆棧是否為空过蹂，search方法檢測一個元素在堆棧中的位置。Stack剛創(chuàng)建后是空棧聚至。
Set接口
Set是一種不包含重復(fù)的元素的Collection酷勺，即任意的兩個元素e1和e2都有e1.equals(e2)=false，Set最多有一個null元素扳躬。
很明顯脆诉，Set的構(gòu)造函數(shù)有一個約束條件，傳入的Collection參數(shù)不能包含重復(fù)的元素坦报。
請注意：必須小心操作可變對象（Mutable Object）库说。如果一個Set中的可變元素改變了自身狀態(tài)導(dǎo)致Object.equals(Object)=true將導(dǎo)致一些問題。
**Map接口 **
請注意片择，Map沒有繼承Collection接口潜的，Map提供key到value的映射。一個Map中不能包含相同的key字管，每個key只能映射一個 value啰挪。Map接口提供3種集合的視圖，Map的內(nèi)容可以被當(dāng)作一組key集合嘲叔，一組value集合亡呵，或者一組key-value映射。
Hashtable類
Hashtable繼承Map接口硫戈，實現(xiàn)一個key-value映射的哈希表锰什。任何非空（non-null）的對象都可作為key或者value。
添加數(shù)據(jù)使用put(key, value)丁逝，取出數(shù)據(jù)使用get(key)汁胆，這兩個基本操作的時間開銷為常數(shù)。
Hashtable通過initial capacity和load factor兩個參數(shù)調(diào)整性能霜幼。通常缺省的load factor 0.75較好地實現(xiàn)了時間和空間的均衡嫩码。增大load factor可以節(jié)省空間但相應(yīng)的查找時間將增大，這會影響像get和put這樣的操作罪既。
使用Hashtable的簡單示例如下铸题，將1，2琢感，3放到Hashtable中丢间，他們的key分別是”one”，”two”驹针，”three”：
Hashtable numbers = new Hashtable();
numbers.put(“one”, new Integer(1));
numbers.put(“two”, new Integer(2));
numbers.put(“three”, new Integer(3));
要取出一個數(shù)千劈，比如2，用相應(yīng)的key：
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);
由于作為key的對象將通過計算其散列函數(shù)來確定與之對應(yīng)的value的位置牌捷，因此任何作為key的對象都必須實現(xiàn)hashCode和equals方法墙牌。hashCode和equals方法繼承自根類Object，如果你用自定義的類當(dāng)作key的話暗甥，要相當(dāng)小心喜滨，按照散列函數(shù)的定義，如果兩個對象相同撤防，即obj1.equals(obj2)=true虽风，則它們的hashCode必須相同，但如果兩個對象不同寄月，則它們的hashCode不一定不同辜膝，如果兩個不同對象的hashCode相同，這種現(xiàn)象稱為沖突漾肮，沖突會導(dǎo)致操作哈希表的時間開銷增大厂抖，所以盡量定義好的hashCode()方法，能加快哈希表的操作克懊。
如果相同的對象有不同的hashCode忱辅，對哈希表的操作會出現(xiàn)意想不到的結(jié)果（期待的get方法返回null），要避免這種問題谭溉，只需要牢記一條：要同時復(fù)寫equals方法和hashCode方法墙懂，而不要只寫其中一個。
Hashtable是同步的扮念。
<h2>HashMap類 <h2>
HashMap和Hashtable類似损搬，不同之處在于HashMap是非同步的，并且允許null柜与，即null value和null key巧勤。，但是將HashMap視為Collection時（values()方法可返回Collection）旅挤，其迭代子操作時間開銷和HashMap 的容量成比例踢关。因此，如果迭代操作的性能相當(dāng)重要的話粘茄，不要將HashMap的初始化容量設(shè)得過高签舞，或者load factor過低。
HashMap的存儲實現(xiàn)：
將多個 key-value 放入 HashMap 中時柒瓣，如下：
HashMap<String , Double> map = new HashMap<String , Double>();
map.put("語文" , 80.0);
map.put("數(shù)學(xué)" , 89.0);
map.put("英語" , 78.2);
HashMap 采用“Hash 算法”來決定每個元素的存儲位置儒搭。
當(dāng)程序執(zhí)行 map.put("語文" , 80.0); 時，系統(tǒng)將調(diào)用"語文"的 hashCode() 方法得到其 hashCode 值——每個 Java 對象都有 hashCode() 方法芙贫，都可通過該方法獲得它的 hashCode 值搂鲫。得到這個對象的 hashCode 值之后，系統(tǒng)會根據(jù)該 hashCode 值來決定該元素的存儲位置磺平。
源碼如下：
static final int hash(Object paramObject){
int i;
return ((paramObject == null) ? 0 : (i = paramObject.hashCode()) ^ i >>> 16);
}
1魂仍、首先獲取對象的hashCode()值拐辽；
2、然后將hashCode值右移16位擦酌；
3俱诸、然后將右移后的值與原來的hashCode做異或運(yùn)算，返回結(jié)果赊舶。
（其中h>>>16睁搭，在JDK1.8中，優(yōu)化了高位運(yùn)算的算法笼平，使用了零擴(kuò)展园骆，無論正數(shù)還是負(fù)數(shù)，都在高位插入0）寓调。
putVal方法
jdk1.8中hashmap 的實現(xiàn)是通過數(shù)組+鏈表+紅黑樹來實現(xiàn)的锌唾，如果鏈表的結(jié)點(diǎn)數(shù)大于8，那么就將鏈表重構(gòu)成紅黑樹捶牢。(圖片來源于網(wǎng)絡(luò))
接著看 HashMap 類的 put(K key , V value) 方法的源代碼：
public V put(K paramK, V paramV){
return putVal(hash(paramK), paramK, paramV, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//如果當(dāng)前hashMap中無數(shù)據(jù)鸠珠，那么調(diào)用resize()方法擴(kuò)容
if ((p = tab[i = (n - 1) & hash]) == null)//如果當(dāng)前通過hash方法找到的hash桶數(shù)組中沒有值
tab[i] = newNode(hash, key, value, null);//那么直接在當(dāng)前結(jié)點(diǎn)新建結(jié)點(diǎn)對象
else {//如果在當(dāng)前hash桶數(shù)組中該位置有值了
Node<K,V> e; K k;//比較該位置的hash值與傳入的參數(shù)hash值是否相等，并且key值是否相等
if (p.hash == hash && //即判斷是否是同一個key對象
((k = p.key) == key || (key != null && key.equals(k))))
e = p;//如果是秋麸，那么將當(dāng)前數(shù)組中的對象p 賦值給 臨時對象e渐排，然后在下面替換掉value值就可以了
else if (p instanceof TreeNode)//如果不是同一key對象，那么判斷p是否是紅黑樹結(jié)點(diǎn)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//如果是灸蟆，那么在紅黑樹中插入結(jié)點(diǎn)
else {//如果不是驯耻，那么就是普通的結(jié)點(diǎn)了，即存放在鏈表中
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//找到鏈表的最后一個結(jié)點(diǎn)
p.next = newNode(hash, key, value, null);//插入新節(jié)點(diǎn)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);//如果大于8炒考，那么重構(gòu)成紅黑樹
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//如果在鏈表中存在的是同一個key對象可缚，那么直接在下面的方法中替換掉
p = e;
}
}//如果當(dāng)前位置的對象是同一對象，那么直接替換掉
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)//如果超過當(dāng)前的閥值斋枢，那么擴(kuò)容
resize();
afterNodeInsertion(evict);
return null;
}
resize方法
（1） 在jdk1.8中帘靡，resize方法是在hashmap中的鍵值對大于閥值時或者初始化時，就調(diào)用resize方法進(jìn)行擴(kuò)容瓤帚；
（2）每次擴(kuò)展的時候描姚，都是擴(kuò)展2倍；
（3）擴(kuò)展后Node對象的位置要么在原位置戈次，要么移動到原偏移量兩倍的位置轩勘。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//oldTab指向hash桶數(shù)組
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {//如果oldCap不為空的話，就是hash桶數(shù)組不為空
if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了怯邪，就賦值為整數(shù)最大的閥值
threshold = Integer.MAX_VALUE;
return oldTab;//返回
}//如果當(dāng)前hash桶數(shù)組的長度在擴(kuò)容后仍然小于最大容量 并且oldCap大于默認(rèn)值16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold 雙倍擴(kuò)容閥值threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶數(shù)組
table = newTab;//將新數(shù)組的值復(fù)制給舊的hash桶數(shù)組
if (oldTab != null) {//進(jìn)行擴(kuò)容操作绊寻，復(fù)制Node對象值到新的hash桶數(shù)組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {//如果舊的hash桶數(shù)組在j結(jié)點(diǎn)處不為空，復(fù)制給e
oldTab[j] = null;//將舊的hash桶數(shù)組在j結(jié)點(diǎn)處設(shè)置為空，方便gc
if (e.next == null)//如果e后面沒有Node結(jié)點(diǎn)
newTab[e.hash & (newCap - 1)] = e;//直接對e的hash值對新的數(shù)組長度求模獲得存儲位置
else if (e instanceof TreeNode)//如果e是紅黑樹的類型澄步，那么添加到紅黑樹中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;//將Node結(jié)點(diǎn)的next賦值給next
if ((e.hash & oldCap) == 0) {//如果結(jié)點(diǎn)e的hash值與原h(huán)ash桶數(shù)組的長度作與運(yùn)算為0
if (loTail == null)//如果loTail為null
loHead = e;//將e結(jié)點(diǎn)賦值給loHead
else
loTail.next = e;//否則將e賦值給loTail.next
loTail = e;//然后將e復(fù)制給loTail
}
else {//如果結(jié)點(diǎn)e的hash值與原h(huán)ash桶數(shù)組的長度作與運(yùn)算不為0
if (hiTail == null)//如果hiTail為null
hiHead = e;//將e賦值給hiHead
else
hiTail.next = e;//如果hiTail不為空冰蘑，將e復(fù)制給hiTail.next
hiTail = e;//將e復(fù)制個hiTail
}
} while ((e = next) != null);//直到e為空
if (loTail != null) {//如果loTail不為空
loTail.next = null;//將loTail.next設(shè)置為空
newTab[j] = loHead;//將loHead賦值給新的hash桶數(shù)組[j]處
}
if (hiTail != null) {//如果hiTail不為空
hiTail.next = null;//將hiTail.next賦值為空
newTab[j + oldCap] = hiHead;//將hiHead賦值給新的hash桶數(shù)組[j+舊hash桶數(shù)組長度]
}
}
}
}
}
return newTab;
}
get方法
（1）get(Object key)
一般我們是通過get（key）來獲取對象的鍵值，在jdk1.8源碼中驮俗，通過getNode(hash(key),key)來獲取結(jié)點(diǎn)對象懂缕，如果返回的結(jié)果不為空，那么就表示有對應(yīng)的結(jié)點(diǎn)王凑，返回e.value。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
（2）getNode(int hash, Object key)
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // 總是從第一個檢查開始 聋丝，比較hash值 和key值
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)//如果是紅黑樹類型索烹，那么在紅黑樹中查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);//循環(huán)遍歷
}
}
return null;//表示沒有找到
}
**WeakHashMap類 **
WeakHashMap是一種改進(jìn)的HashMap，它對key實行“弱引用”弱睦，如果一個key不再被外部所引用百姓，那么該key可以被GC回收。
總結(jié)
1.如果涉及到堆棧况木，隊列等操作垒拢，應(yīng)該考慮用List，對于需要快速插入火惊，刪除元素求类，應(yīng)該使用LinkedList，如果需要快速隨機(jī)訪問元素屹耐，應(yīng)該使用ArrayList尸疆。
2.如果程序在單線程環(huán)境中，或者訪問僅僅在一個線程中進(jìn)行惶岭，考慮非同步的類寿弱，其效率較高，如果多個線程可能同時操作一個類按灶，應(yīng)該使用同步的類症革。
3.要特別注意對哈希表的操作，作為key的對象要正確復(fù)寫equals和hashCode方法鸯旁。
4.盡量返回接口而非實際的類型噪矛，如返回List而非ArrayList，這樣如果以后需要將ArrayList換成LinkedList時羡亩，客戶端代碼不用改變摩疑。這就是針對抽象編程。
