HashMap簡介
在 Java8 中垂涯，HashMap 是由數(shù)組和鏈表構(gòu)成的數(shù)據(jù)結(jié)構(gòu)袖外，當(dāng)它的鏈表長度超過8時史隆，會將鏈表轉(zhuǎn)成紅黑樹。它是基于哈希算法實現(xiàn)的一個結(jié)構(gòu)曼验，存取時泌射，根據(jù)鍵值來計算出 HashCode, 再根據(jù) HashCode 來定位到數(shù)組中相應(yīng)的位置，同時它支持 null 鍵值對鬓照，但是不保證有序熔酷，也不保證順序永遠不會變化，而且它是線程不安全的豺裆。
HashCode
上面說到了 HashCode, HashCode 用于指定數(shù)組的索引拒秘， 可以快速找到對象再數(shù)組的位置号显，再通過遍歷這個數(shù)組下的鏈表來獲取存儲的值，在存入的時候躺酒，也會根據(jù)鍵值生成對應(yīng)的 HashCode押蚤。
時間復(fù)雜度
如果在理想的狀況下， 例如每個對象都有獨屬于自己的 HashCode,那么獲取這個對象的時間復(fù)雜度是 O(1), 反之羹应，最壞的情況是 O(N)揽碘，所以一個好的哈希算法可以讓時間復(fù)雜度趨向于 O(1)。
負載因子
默認 HashMap 的長度為16园匹，但是當(dāng) HashMap 需要擴容時雳刺，參與影響的參數(shù)還有負載因子。
默認的負載因子大小為 0.75裸违，即當(dāng)前使用的容量超過 總?cè)萘?負載因子 的數(shù)量時掖桦，則會擴容，默認的擴容是一次擴大兩倍供汛。
所以可以根據(jù)計算知道枪汪， 默認情況下，HashMap 第一次擴容是在存入第13個對象的時候怔昨。
當(dāng)然我們也可以自己定義數(shù)組的容量和負載因子料饥。
public HashMap(int initialCapacity, float loadFactor)
//第一個參數(shù)為數(shù)組大小， 第二個參數(shù)為負載因子
值得一提的時朱监，HashMap 的擴容也是體力活岸啡，需要創(chuàng)建一個新的數(shù)組，再把原來的數(shù)據(jù)存放到新的數(shù)組里赫编，同時需要重新計算 HashCode巡蘸，來確定原來的對象在新的數(shù)組中的位置。
至于默認是0.75的原因擂送，我認為是在數(shù)組容量不變的情況下悦荒，存放的鍵值對越多，會導(dǎo)致鏈表越長（紅黑樹也是）嘹吨，從而影響查找的效率搬味，所以擴容可以有效的解決這個問題，而0.75的默認值也是一個權(quán)衡問題蟀拷，如果后期存儲的鍵值對數(shù)量龐大起來碰纬，那么可以比較好的提升查找效率，但是也會犧牲相當(dāng)一部分大的空間问芬。
哈希碰撞
聽著厲害悦析，其實就是 一個以上的鍵值對同時分配到了同一個 HashCode, 這個時候就往這個 HashCode 對應(yīng)的數(shù)組位置里的鏈表里塞，如果是 Java8, 鏈表長度大于8后此衅，就會轉(zhuǎn)化為紅黑樹强戴。
當(dāng)然一個好的 Hash 算法亭螟，應(yīng)該盡量少的避免哈希碰撞，在一定范圍內(nèi)骑歹， 也該盡量平均的分配 HashCode预烙。
源碼分析 Java8
put 過程
public V put(K key, V value) {
//這里調(diào)用了 putVal 方法， 傳入了 HashCode, key, value 等信息道媚。
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
//這兩個 boolean 值我直接引用源碼中的注釋 可以知道 onlyIfAbsent 為 true 則不能覆蓋已經(jīng)存在的值默伍，
//evict 為 false 時 則需要創(chuàng)建新的表，使用時這兩個值與我們無關(guān)衰琐，我們只需要調(diào)用 put 方法就好了。
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)
//如果數(shù)組為空或者數(shù)組長度為0 擴容炼蹦！
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//如果 HashCode 對應(yīng)的位置沒有其它對象羡宙，則創(chuàng)建一個新的 Node
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//（1）如果這個位置有對象，并且 HashCode 和 key 相等掐隐，那么先獲取這個對象的索引狗热，后面用作替換
e = p;
else if (p instanceof TreeNode)
//如果這個Node已經(jīng)被轉(zhuǎn)成紅黑樹的話，那么根據(jù)紅黑樹的規(guī)則插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//遍歷到隊尾虑省，將新的鍵值對放入
p.next = newNode(hash, key, value, null);
//如果當(dāng)前鏈表長度大于最大值（默認是8）匿刮，則轉(zhuǎn)化為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//和注釋（1）中一樣的邏輯
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//如果 onlyIfAbsent 為false，說明可以替換舊值探颈，或者舊值是空值的情況下
//都可以替換
e.value = value;
afterNodeAccess(e);
//返回舊值熟丸，
return oldValue;
}
}
++modCount;
if (++size > threshold)
//如果存儲的鍵值對達到擴容的要求，則擴容
resize();
afterNodeInsertion(evict);
return null;
}
總結(jié) put 流程
首先判斷數(shù)組是否為空或者長度為0伪节，是的話則擴容光羞，再判斷對應(yīng)的數(shù)組位置中是否有值，沒有的話直接為其創(chuàng)建新的 Node 作為鏈表頭放入怀大，如果上述條件不符合
時纱兑，則遍歷該數(shù)組位置中的鏈表，將新鍵值對放在鏈表尾部化借，如果是紅黑樹的話潜慎，則按紅黑樹的規(guī)則插入。
當(dāng)鏈表長度大于8時蓖康，轉(zhuǎn)為紅黑樹铐炫，當(dāng)達到擴容閾值時，會擴容蒜焊，put成功后驳遵，它將返回舊值。
擴容方法 resize
好長好累
final Node<K,V>[] resize() {
//先引用一下舊數(shù)組和舊數(shù)組的長度山涡，容量閾值堤结。
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
// MAXIMUM_CAPACITY的大小是 1 << 30 唆迁，所以這里就是太大了，直接返回最大值給它竞穷，表也不變了唐责。
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果老數(shù)組*2在 HashMap 允許的范圍內(nèi)，那么計算出新數(shù)組的擴容閾值瘾带，就是原來的兩倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
//這里是初始化鼠哥，針對舊數(shù)組為空或者長度為0，但是擴容閾值大于0的情況
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//這里是默認的初始化看政，針對舊數(shù)組為空或者長度為0的情況朴恳。
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 如果擴容閾值為0， 則根據(jù)新的數(shù)組容積和負載因子計算允蚣。
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新 threshold
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//創(chuàng)建一個新的數(shù)組
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//將舊數(shù)組的對象替換為null于颖，help GC
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
//接下來的過程可能比較復(fù)雜，大致是降一個鏈表分為兩條鏈冒晰，
//然后根據(jù)它們對應(yīng)的 HashCode 放到數(shù)組中相應(yīng)的位置同衣。
//這條鏈是應(yīng)放在原位的鏈
Node<K,V> loHead = null, loTail = null;
//這條鏈是應(yīng)放在 原位置+原數(shù)組長度 位置的鏈
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
//引用當(dāng)前鏈表的后續(xù)節(jié)點
next = e.next;
if ((e.hash & oldCap) == 0) {
//位運算為0時，留在原位壶运。
if (loTail == null)
//lo鏈的鏈頭
loHead = e;
else
//lo鏈長度不為0時耐齐，依次添加在尾部
loTail.next = e;
//lo鏈尾部是當(dāng)前節(jié)點，目測主要是為了避免上面if一直執(zhí)行
loTail = e;
}
else {
//如果位運算結(jié)果不為0后蒋情，則將節(jié)點放入hi鏈
//接下來的大致邏輯和上面一樣
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);//遍歷鏈表
if (loTail != null) {
//按原來的位置將lo鏈放到新數(shù)組中
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
//按 原來的位置+原來數(shù)組的容量 的位置將 hi鏈放入數(shù)組中
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//返回新的數(shù)組
return newTab;
}
擴容應(yīng)該算是 HashMap 最為復(fù)雜的方法了蚪缀，當(dāng)然作為 Java8 添加了新特性的 HashMap, 其中引入了紅黑樹作為防止鏈表過長導(dǎo)致的查找時浪費也是很重要的一環(huán)。
這里需要注意的是恕出，任何一個小于2的倍數(shù)的數(shù)與2的倍數(shù) & 運算都是等于 0询枚， 所以可以看擴容方法中的 loHead 鏈 和 hiHead 鏈是根據(jù)元素自身的HashCode與舊數(shù)組大小比較來區(qū)分的。
該部分小結(jié)
通過上面的 put 和 resize 方法的源碼浙巫，可以很好的了解 HashMap 中的的數(shù)據(jù)結(jié)構(gòu)金蜀，同時在這里也和 Java7 的 HashMap 做一些比較(程序員向前看，了解就好的畴，主要還是看 Java8 的代碼渊抄，還是懶)：
- 當(dāng) Hash 碰撞時（多個鍵值對分配到了同樣的 HashCode），Java7 會在鏈表頭插入新鍵值對丧裁，而 Java8 會在尾部插入护桦。
- 擴容后轉(zhuǎn)移數(shù)據(jù)時，Java7 鏈表的順序會顛倒煎娇，而 Java8 依舊保持原來順序
（源碼上就這句注釋醒目）
// preserve order
- Java8 引入了紅黑樹
接下來稍微介紹下紅黑樹
紅黑樹的特性
紅黑樹是一種不嚴格的二叉平衡查找樹二庵，但它的特性又讓它成為一個合格的平衡二叉查找樹贪染。
這里的平衡，可以理解為穩(wěn)定催享，即一個平衡二叉樹在動態(tài)更新的情況下杭隙，還能很好的保持高度在 log2(N) 左右，在不高出太多的情況仍保持一個對數(shù)級的高度因妙。
紅黑樹規(guī)則
一棵樹如果是紅黑樹痰憎，那么它要滿足如下規(guī)則
- 根節(jié)點是黑色的
- 每個葉子節(jié)點都是黑色的空節(jié)點
- 任何紅色節(jié)點的相鄰節(jié)點不能是紅色，即紅色節(jié)點之間需要用黑色節(jié)點隔開
- 每個節(jié)點攀涵，從該節(jié)點到葉子節(jié)點的所有路徑铣耘，其中的黑色節(jié)點數(shù)量都是相等的
為什么說紅黑樹是近似平衡的
如果將紅色節(jié)點都去掉，那么根據(jù)紅黑樹規(guī)則的第四點以故，那么將會得到一顆完全樹蜗细，這時候黑樹的高度是不會高于 log2(N)的。
這時候我們根據(jù)規(guī)則第三點据德，因為每個紅色節(jié)點之間都有黑色節(jié)點隔開，所以紅色節(jié)點的高度也不會超過 log2(N)跷车。
因此紅黑樹的高度將近似于 2log2(N)棘利。2 是一個常數(shù)，所以可以說紅黑樹是近似平衡的朽缴。
