Collection API 位于 java.util 包中。包中的 Collection 接口是 JAVA 對于集合這一概念的抽象，存儲一組類型相同的對象。
還有一個很重要的接口：Iterable，Collection 接口以繼承的方式對 Iterable 做了擴充。實作 Collection 接口的類可以獲得增強 for 循環（forEach）。
資料結構（數組+連結清單)
HashMap 是 JAVA 集合架構的成員。基于 [ 數組 + 連結清單 ] 的資料結構存儲 key-value 形式的資料。key 是每條資料的唯一辨別，HashMap 通過一個 hash 算法（也稱雜湊演算法）根據 key 值計算出這條資料在數組中的位置，即數組下标，然後把資料裝載到一個連結清單元素
Node<K, V>
中，最後根據數組下标進行落桶（bucket）操作。
hash碰撞（沖突）：
如果兩個輸入的 hash 結果相同，則稱這兩個輸入是一個碰撞(Collision)。
在JAVA中，采用“鍊位址法”解決 hash碰撞。HashMap 在數組中存放第一個落桶的節點，這個節點也是連結清單的 head節點，擁有一個 next 屬性指向 null，當下一個相同 hash 值的元素落桶，則使此 head節點的 next 指向新的元素，即後來的節點作為連結清單的 tail節點。
由上圖可知，數組在 0 和 2 的位置存放了節點k1/k2，當節點 k3 與 k2 發生了 hash碰撞，則使節點 k2 的 next 指向節點 k3。值得注意的是，在 JAVA8 中，為了提高檢索效率，當連結清單的節點數量超過8個，并且整個數組容量超過 64 個，則把這個連結清單重載成紅黑樹（樹化），否則進行 2 倍擴容并且重新散列（rehash）所有節點。樹化操作是因為連結清單的檢索是線性時間O(n)，而紅黑樹是對數時間O(lgn)。這麼處理大概是為了盡可能避免過早的把資料存放到桶外（形成長連結清單），因為桶數組的容量是參與元素索引計算的。
存儲(hash算法，hash沖突，初始化，擴容)
// 對使用者提供的put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 散列（hash）方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 這裡的位異或運算和無符号右移運算後邊會詳細說明[1]
}
// 實作Map.put
// 如果對象已存在傳回上一個值，如果沒有則傳回null
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) // 這裡的table就是HashMap的桶數組，這個數組是需要制定容量的，預設16，屬性"DEFAULT_INITIAL_CAPACITY"
n = (tab = resize()).length; // HashMap在第一次put的時候進行初始化
if ((p = tab[i = (n - 1) & hash]) == null) // 判斷即将落桶的位置是否已經有Node存在，即是否存在hash沖突，這裡的位與運算後邊會詳細說明[2]
tab[i] = newNode(hash, key, value, null); // 不存在hash沖突直接落桶
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) // 判斷是否在數組中存放的對象（即連結清單頭節點）與新的對象的key值相同，如果相同直接提取到新的拷貝e中供後續操作
e = p;
else if (p instanceof TreeNode) // 如果p處于紅黑樹中，則調用TreeNode.putTreeVal()方法提取舊節點到e中供後續操作
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // 如果p處于連結清單中
for (int binCount = 0; ; ++binCount) { // 周遊連結清單
if ((e = p.next) == null) { // 當整個連結清單不存在與新節點相同的key，則直接把新節點加入到連結清單的尾部
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 當連結清單元素數量到達指定門檻值，預設8個，進行“樹化”
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break; // 當找到與新節點相同的key，提取到e中供後續操作
p = e;
}
}
if (e != null) { // 當新節點的key已經存在（這裡就是上邊多處提到的“供後續操作”）
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) // onlyIfAbsent參數的意思是“是否不覆寫舊值”
e.value = value;
afterNodeAccess(e); // 這個方法是為了繼承HashMap的LinkedHashMap類服務的，可以忽略
return oldValue;
}
}
++modCount; // 這是一個記錄操作次數的變量，後邊會詳細說明[3]
if (++size > threshold) // 如果不是值覆寫會執行到這步，如果本次元素插入導緻了桶數量超過門檻值，則進行擴容，後邊會詳細說明[4]
resize();
afterNodeInsertion(evict); // 和afterNodeAccess()方法一樣，可以忽略
return null;
}
// 初始化或加倍表格大小
// 如果為null，則配置設定初始容量。否則，進行2次幂擴充。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 舊的數組容量
int oldThr = threshold; // 舊的擴容門檻值
int newCap, newThr = 0; // 聲明新的數組容量和擴容門檻值
if (oldCap > 0) { // 舊的數組容量大于0說明本次是擴容操作
if (oldCap >= MAXIMUM_CAPACITY) { // 擴容前的數組大小如果已經達到最大(2^30)了
threshold = Integer.MAX_VALUE; // 修改門檻值為int的最大值(2^31-1)，這樣以後就不會擴容了
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // 普通擴容，在下邊展開解釋[4]
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 新的擴容門檻值同樣擴大2倍
}
else if (oldThr > 0) // 這裡話多了，在下邊解釋[5]
newCap = oldThr;
else { // zero initial threshold signifies using defaults, 這裡和 [5] 一起看吧
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];
table = newTab;
if (oldTab != null) {
// 把每個bucket都移動到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 删除了舊節點的引用（很細節）
if (e.next == null) // 當桶裡隻有一個節點，重新計算索引位置落桶
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((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;
if ((e.hash & oldCap) == 0) { // 直接用容量與 hash 位與運算，相當于舍掉低位特征，大概是針對hash沖突進行一次随機散列。結果為0的保持原來的索引位置不變
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { // 否則向右偏移舊數組容量
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead; // 向右偏移舊數組容量
}
}
}
}
}
return newTab;
} 詳細說明
[1]
(h = key.hashCode()) ^ (h >>> 16)
public native int hashCode(); 這裡的 hashCode() 是一個 native 方法，根據一定的規則将與對象相關的資訊（比如對象的存儲位址，對象的字段等）映射成一個數值，這個數值稱作為散列值。
無符号右移：>>>
按二進制形式把所有的數字向右移動對應的位數，低位移出(舍棄)，（如果是“有符号右移>>”：高位的空位補符号位，即正數補0，負數補1。當運算數是 byte 或 short 類型時，将自動把這些類型擴大為 int 型。由于 int 類型是 32 位，這裡的右移16位（舍去低位）并與 hashCode 異或運算将導緻高位的影響傳播到低位。
[2]
i = (n - 1) & hash
n = table.length 此處是根據hash值計算數組下标。n 是容量，值得注意的是，HashMap的預設初始容量是16，指定容量也會被擴充到2的幂次，歸根結底就是為了在計算數組下标的時候，用 (n - 1) 與 hash值進行位與運算。因為在[1]中計算hash值的計算中，把高位的特征傳播到了低位，而2的幂次減一的值永遠是形如：1111，11111，111111的，是以index僅與hash值的低n位有關，hash值的高位都被與操作置為了0。
上圖為 HashMap 根據 key 計算 hash 值并最終計算出數組下标 index 的過程。我們來驗證一下：
1.建立一個 HashMap：
可以看到，在建立map這一步，内部已經做了初始化如：size、modCount、threshold、loadFactor
2.執行下一步，put 一個 key 為 "WANGNIMA" 的元素：
現在數組 table 中已經有了資料，包括 size、modCount、threshold 也都有了值。
這裡解釋一下 threshold 這個變量，它作為 HashMap 擴容的門檻值，在初始化的時候，是根據
loadFactor（加載因子，預設0.75f）* initialCapacity（初始容量，預設16）
得到的，即
0.75 * 16 = 12
，當數組 size 超過這個門檻值的時候，觸發 2 倍的擴容。
3.接下來繼續執行到把兩個元素都 put 進去：
看到
WANGNIMA
被如期放到了下标 0 的位置，
WANGNIMA2
被放到了 9 的位置。
4.測試 hash 沖突：
我們找到了與
WANGNIMA
的 hashCode 值相同的字元串
Z@]LRTyvHV\\SCV^
，由圖可知：table 中還是 0 和 9 的位置有元素，最後 put 的
Z@]LRTyvHV\\SCV^
被放在了
WANGNIMA
的 next 中，也就是連結清單的第二個位置處。
[3]
++modCount;
fail-fast 機制。
開篇說道：實作 Collection 接口的類可以獲得增強 for 循環。其實在編譯階段，編譯器會把 forEach 這樣的語句編譯成疊代器疊代的方式：
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>(16);
map.put("WANGNIMA", 250);
map.put("WANGNIMA2", 250);
for (String key : map.keySet()) {
System.out.println("Key = " + key);
}
}
// .class
public static void main(String[] args) {
Map<String, Integer> map = new HashMap(16);
map.put("WANGNIMA", 250);
map.put("WANGNIMA2", 250);
Iterator var2 = map.keySet().iterator();
while(var2.hasNext()) {
String key = (String)var2.next();
System.out.println("Key = " + key);
}
} 如果在建立疊代器之後的任何時候對 map 進行結構修改，除了疊代器自己以外的任何線程調用 remove() 方法，疊代器将抛出 ConcurrentModificationException，是以，在并發修改的情況下，疊代器會快速失敗，而不是冒着非确定性行為的風險。
[4]
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; 其中
oldCap << 1
相當于 oldCap*2，即把新的數組容量 "newCap" 擴大2倍。
[5]
else if (oldThr > 0) // 舊的擴容門檻值指派給新的數組容量
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
} 首先 HashMap 有三個構造方法，HashMap() / HashMap(int initialCapacity) / HashMap(int initialCapacity, float loadFactor)
無參構造僅僅初始化了 loadFactor 為預設的 0.75f；
HashMap(int initialCapacity) 構造也是調用了 HashMap(int initialCapacity, float loadFactor)，而把DEFAULT_LOAD_FACTOR 預設傳入了，這兩個構造方法初始化了 loadFactor 和 threshold，值得注意的是，這裡的 threshold 代表的卻是數組容量，将會在首次 put 操作的時候，作為數組初始化的容量值，然後再去乘 loadFactor 作為真正意義上的 "擴容門檻值"。
可見，為數組申請記憶體空間這個工作被配置設定給了首次 put 操作而非構造方法，當 oldThr > 0 就說明使用者調用了有參構造方法（指定了初始容量，并被構造方法 "緩存" 到了threshold中了），需要初始化一個 threshold 大小的數組，即 newCap；否則，初始化的數組容量為預設的 16，初始化的擴容門檻值為預設的 16 * 0.75。
總結
數組和連結清單是 JAVA 中最常見的兩種資料結構，HashMap 的設計者巧妙的利用了這兩個資料結構的優點。在雜湊演算法的實作上，權衡了空間、時間和算法複雜度。
要注意的是：HashMap 的擴容操作是十分耗費時間和空間的，是以建議開發者在應用中，一定要設定初始容量，防止動态擴容的發生。這一點在《阿裡巴巴Java開發手冊》中也有提到: