摘要
散清單（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行通路的資料結構。也就是說，它通過把關鍵碼值映射到表中一個位置來通路記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散清單。
HashMap是Java程式員使用最頻繁的的用于鍵值對(key value)資料處理的容器，在JDK1.7(Java Developmet Kit）時HashMap采取的是數組+連結清單的形式存儲資料，JDK1.8對HashMap進行了存儲結構上的優化，引入了紅黑樹資料結構，極大的增強了HashMap的存取性能！為什麼會引入紅黑樹呢？因為HashMap存在一個問題，即使負載因子和Hash算法設計的再合理，也無法避免出現在連結清單上拉鍊過長的問題，如果極端情況下出現嚴重的Hash沖突，會嚴重影響HashMap的存取性能，于是HashMap在jdk1.8時，引入了紅黑樹，利用紅黑樹快速增删改查的特點來優化了HashMap的性能！
簡介
Java為資料結構中的映射（鍵值對）定義了一個接口java.util.Map，這個接口有四個我們在開發中使用較為頻繁的實作類，分别是HashMap、Hashtable、LinkedHashMap、TreeMap
| 序号 | 實作類 | 特點 |
| 1 | HashMap<K, V> | 1、根據鍵的hashcode存儲資料 2、允許一條記錄的key為null，允許多條記錄的value為null 3、非線程安全 |
| 2 | Hashtable<K, V> | 1、線程安全 2、性能較低，需要使用的場景可以用ConcurrentHashMap替換 |
| 3 | LinkedHashMap<K,V> | 1、通路具有順序性，儲存了插入順序 2、可以通過構造函數入參來使其按照通路次序排序 |
| 4 | TreeMap<K,V> | 1、有序Map，可以通過排序比較器來自定義存儲資料的排序規則，預設按照key的生序排列 2、使用時key需要實作Comparable接口或者通過構造函數傳入自定義Comparator |
存儲結構
jdk1.8以後HashMap采用數組+連結清單/紅黑樹的方式來存儲資料
源碼分析
主幹
// HashMap的主幹，也就是上面的綠色部分，是一個Node數組，每個Node包含一個K-V鍵值對
transient Node[] table;
節點元素
// Node是HashMap的靜态内部類，實作了Map接口中的内部Entry接口
static class Node implements Map.Entry {
// 記錄目前Node的key的hash值，可以避免重複計算，空間換時間
final int hash;
// 鍵
final K key;
// 值
V value;
// 存儲指向下一個Entry的引用，是單向連結清單結構
Node next;
// ...
}
其他重要字段
// 預設的初始容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量，1左移30位
static final int MAXIMUM_CAPACITY = 1 << 30;
// 預設擴容因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 連結清單轉紅黑樹的連結清單長度
static final int TREEIFY_THRESHOLD = 8;
// 紅黑樹轉連結清單的門檻值
static final int UNTREEIFY_THRESHOLD = 6;
// 連結清單轉紅黑樹的數組長度
static final int MIN_TREEIFY_CAPACITY = 64;
// 實際存儲K-V鍵值對的個數
transient int size;
// 記錄HashMap被改動的次數，由于HashMap非線程安全，modCount可用于FailFast機制
transient int modCount;
// 擴容門檻值，預設16*0.75=12，當填充到13個元素時，擴容後将會變為32，
int threshold;
// 負載因子 loadFactor=capacity*threshold，HashMap擴容需要參考loadFactor的值
final float loadFactor;
構造函數
// 看一個參數比較全的構造函數，構造函數中并未給table配置設定記憶體空間，此構造函數HashMap(Map m)會給table配置設定記憶體空間
public HashMap(int initialCapacity, float loadFactor) {
// 判斷初始化容量是否合法，如果<0則抛出異常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
// 判斷initialCapacity是否大于 1<<30，如果大于則取 1<<30 = 2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 判斷負載因子是否合法，如果小于等于0或者isNaN，loadFactor!=loadFactor，則抛出異常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
// 指派loadFactor
this.loadFactor = loadFactor;
// 通過位運算将threshold設值為最接近initialCapacity的一個2的幂次方（這裡非常重要）
this.threshold = tableSizeFor(initialCapacity);
}
hash算法實作
HashMap中的hash算法實作分為三步。其中第二步使用hash值高16位參與位運算，是為了保證在數組table的length比較小的時候，可以保證高低bit都參與到hash運算中，保證配置設定均勻的同時采用位運算，也不會有太多的性能消耗；其中第三步，當n是2的整數的幂次方是，hash&(n-1)，相當于對hash值取模，而位運算比取模運算效率更高；具體流程可以通過圖示檢視。
第一步：通過key.hashCode()擷取key的hashcode；
第二步：通過(h = key.hashCode()) ^ (h >>> 16)進行高16位的位運算；
第三步：通過(n - 1) & hash對計算的hash值取模運算，得到節點插入的數組所在位置。
HashMap之put方法
第一步：判斷鍵值對數組table[i]是否為空/null，是則執行resize()擴容。
第二步：根據鍵key計算hash值得到插入數組的索引i，如果tab[i]== null則直接插入，執行第六步；如果tab[i] != null，執行第三步。
第三步：判斷tab[i]的第一個元素與插入元素key的hashcode&equals是否相等，相等則覆寫，否則執行第四步。
第四步：判斷tab[i]是否是紅黑樹節點TreeNode，是則在紅黑樹中插入節點，否則執行第五步。
第五步：周遊tab[i]判斷連結清單是否大于8，大于8則可能轉成紅黑樹（數組需要大于64），滿足則在紅黑樹中插入節點；否則在連結清單中插入；在周遊連結清單的過程中如果存在key的hashcode&equals相等則替換即可。
第六步：插入成功，判斷hashmap的size是否超過threshold的值，超過則擴容。
put(K key, V value)
public V put(K key, V value) {
// hash(key) 根據key計算一個hash值，具體實作如下函數
return putVal(hash(key), key, value, false, true);
計算key的hash值
static final int hash(Object key) {
int h;
// 如果key等于null,傳回0
// 否則取key的hashcode值h， 将h無符号右移16位也就是擷取高16位，将兩個值做異或位運算後傳回
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node[] tab; Node p; int n, i;
// 判斷table是否為空，為空則resize()建立
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash計算插入節點在數組中的索引index，為空則直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
// 如果節點key存在，則覆寫目前元素
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 節點不存在且目前的數組節點上的鍊為RBT紅黑樹，則按照紅黑樹的方式插入節點
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
// 鍊為連結清單
else {
for (int binCount = 0; ; ++binCount) {
// 節點的下一個節點為null，說明周遊到了連結清單的最後一個節點，将目前周遊到的最後一個節點的next指向新插入節點
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 連結清單長度大于8可能需要做紅黑樹轉換，具體要看treeifyBin()中判斷數組的長度是否大于64
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 節點存在則傳回
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
// 不存在且寫一個節點不為null，則将下一個節點指派給目前節點，繼續下一次循環
p = e;
}
}
// 節點存在替換後直接傳回，不會記錄HashmMap結構變化
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
// 記錄HashMap的結構變化
++modCount;
// 判斷節點插入後是否需要對hashMap的數組進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
擴容
final Node[] resize() {
// 将擴容前的數組指派給oldTab
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 判斷數組長度是否大于等于允許的最大值，超過則取最大值，直接傳回
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
// 将原先數組大小左移一位，也就是擴大兩倍，擴容前需要判斷大小是否超過允許的最大值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
// 如果數組大小小于等于0且threshold大于0(比如HashMap中的元素被全部删除了)，則将oldThr的值指派給newCap
else if (oldThr > 0)
newCap = oldThr;
//首次初始化，給與預設的值
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
// 如果新的擴容臨界值仍為0，需要給newThr計算一個值
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數組
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 周遊舊數組指派到新數組中
for (int j = 0; j < oldCap; ++j) {
Node e;
// 如果節點不為null，則将節點指派給e
if ((e = oldTab[j]) != null) {
// 将節點引用置空，等待GC回收
oldTab[j] = null;
// 如果節點的next指向為空，則根據節點記錄的hash值&擴容的大小-1，重新計算節點在數組中的索引位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果節點是紅黑樹節點，按照紅黑樹節點插入方式插入
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
// 此處表示目前節點上的鍊為連結清單，周遊連結清單，将連結清單轉移到新的數組上
else {
// 建立兩條鍊lo鍊在原先數組節點位置
Node loHead = null, loTail = null;
// hi鍊插入原先數組索引+oldCap位置
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
// 重點
// 擷取目前節點的hash值，與oldCap做按位與運算，如果運算結果為0，則加入lo鍊
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 否則加入hi鍊
else {
if (hiTail == null)
hiHead = e;
hiTail.next = e;
hiTail = e;
} while ((e = next) != null);
// 新數組的原位置指向lo鍊的頭節點
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 新數組的j+oldCap指向hi鍊的頭節點
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
return newTab;
圖文聊聊jdk1.8中擴容後resize()那些事
在jdk1.8中，當發生HashMap擴容時我們通過源碼可以發現，HashMap并未重新通過新的數組長度來确定節點的位置，而是通過(e.hash & oldCap) == 0，原hash值與原數組長度做與位運算來确定節點在新數組中的位置，當(e.hash & oldCap) == 0時，節點在新數組中的位置和老數組位置一緻；當(e.hash & oldCap) != 0時，節點在新數組中的位置為j + oldCap，也就是原先的位置加上老數組的長度。
這裡抛出兩個問題，帶着問題來分析，
問題一：為什麼能這麼實作呢？
問題二：以前hash值相同的節點在數組的同一個索引位置上，現在竟然會被随機配置設定到兩個新的索引位置上，這會不會導緻get(key)時無法擷取到元素呢？
三個前提條件
1、HashMap在做初始化的時候數組的預設大小是16，且如果我們設值的初始值不是2的整數次幂，那麼它會自動的去計算一個與初始化值最靠近的2的整數次幂的初始值，具體實作可以檢視源碼中的tableSizeFor()方法。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
2、HashMap擴容的方式是oldCap << 1，一定是擴容為原來的2倍，保證擴容後仍然是2的整數次幂
3、HashMap計算數組索引的方式為(n - 1) & hash
數組的初始大小為16，擴容因子為0.75，依次插入三個節點，節點的key分别為key1、key2、key3，假設在插入完成第三個節點後數組中節點的個數到達12個，此時需要進行擴容
此時HashMap中元素分布假設下圖所示，size=12，進行擴容
擴容的算法為 e.hash & oldCap，計算後發現key2的值為0，維持在老數組中下标位置，key1和key3需要轉移到j + oldCap的位置，也就是1+16=17下标位置上
擴容後節點分布圖
此時我們再來看擴容後根據key擷取元素的代碼
public V get(Object key) {
Node e;
// 根據目前key計算hash值，這個計算方式上面已經詳細介紹過
return (e = getNode(hash(key), key)) == null ? null : e.value;
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
// 當數組不為空，并且key對應的數組下标的元素存在
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
// 檢查擷取的節點是否是第一個節點，是則傳回
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 不是頭結點則判斷下一個節點是否存在
if ((e = first.next) != null) {
// 如果節點是紅黑樹，則在紅黑樹中擷取元素
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
// 如果是連結清單則周遊連結清單中的節點，比對key則傳回，當e不存在下一個節點則結束循環傳回null
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
// 為比對上則傳回null
從上面的源代碼中我們可以非常明顯的看見，擷取節點所在數組中的下标的方式也是(n - 1) & hash，與插入節點時計算數組下标的方式是一抹一樣的，那此時為何能準确的找到在key1、key2、key3呢？原因就是n的值變為了原來的兩倍，而節點的hash值是不會發生改變的，此時計算出來的節點在數組中的位置，與我們在擴容時，進行的節點移動操作（也可以了解為重新計算數組中的索引）是一緻的；我們可以通過get時，計算key1、key2、key3的索引來展示效果，如下
小結
- HashMap在1.8中做了很大的優化，無論是在計算hash值的算法上，還是底層資料結構從數組+連結清單變為數組+連結清單/紅黑樹，都是對性能有很大的提升
- HashMap是線程不安全的，在實際生産開發過程中我們如果需要使用的線程安全的key-value存儲，可以選擇ConcurrentHashMap或者Collections的synchronizedMap是的HashMap具有線程安全的能力，當然推薦的是ConcurrentHashMap
- 為了保證HashMap的性能，減少擴容帶來的性能損耗，我們在使用的過程中，要提前預估存儲值的大小，設定合理的初始大小和擴容因子也是有必要的
- 在使用HashMap時，有必要的情況下我們一定要重寫key的hashcode方法和equals方法