HashMap原理
1. HashMap 的底層結構
- Java7 : 數組 + 鏈表
- Java8: 數組 + 鏈表 + 紅黑樹 (鏈表超過8則轉為紅黑樹，小於6則變會鏈表) >> 加快查詢.
2.HashMap參數
源碼如下：
參數解釋：
DEFAULT_INITIAL_CAPACITY : 默認初始容量（16）， 必須是2的冪。（ 1 >> 4 也就是轉化為 2進位後 0000 0001 左移4位 也就是 0001 0000， 也就是16）
DEFAULT_LOAD_FACTOR： 默認負載因子0.75，（超過 容量與負載因子的乘積會擴容）
TREEIFY_THRESHOLD : 大小為8及以上時鏈表會轉化為紅黑樹 的閾值。
UNTREEIFY_THRESHOLD ： 大小為6及以下會轉化為 鏈表 的閥值。
Hashmap中的鏈表大小超過八個時會自動轉化為紅黑樹，當刪除小於六時重新變為鏈表，為啥呢？
根據泊松分布，在負載因子默認為0.75的時候，單個hash槽內元素個數為8的概率小於百萬分之一，所以將7作為一個分水嶺，等於7的時候不轉換，大於等於8的時候才進行轉換為紅黑樹，小於等於6的時候就化為鏈表。
3. put()的實現
put函數大致的思路為：
1）對key的hashCode()做hash，然後再計算index;
2）如果沒碰撞直接放到 tab[i]里；
3）如果碰撞了，以鏈表的形式存儲， （結合第一章節的圖， 化學與數學的hash衝撞後， 轉為鏈表存在數學的下一個節點處。）；
4）如果碰撞導致鏈表過長(大於等於TREEIFY_THRESHOLD)，就把鏈錶轉換成紅黑樹；
5）如果節點已經存在就替換old value(保證key的唯一性)
6）當容量將超過 負載因子與初始容量的乘積 （load factor*current capacity)，就要resize。
程式碼實現如下：
public V put(K key, V value) {
// 對key的hashCode()做hash
return putVal(hash(key), key, value, 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;
// tab為空則創建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 計算index，並對null做處理,
if ((p = tab[i = (n - 1) & hash]) == null)
//直接構造一個Node 存進 tab 以 hash運算後的為下標 里。
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))))
e = p;
// 該鏈為樹
else if (p instanceof TreeNode)
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);
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))))
break;
p = e;
}
}
// 寫入
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超過load factor*current capacity，resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
put()實現
4. get()函數實現
在理解了put之後，get就很簡單了。大致思路如下：
整個HashMap 稱之為bucket （桶）
bucket里的第一個節點，直接命中；
如果有衝突，則通過key.equals(k)去查找對應的entry
若為樹，則在樹中通過key.equals(k)查找，O(logn)；
若為鏈表，則在鏈表中通過key.equals(k)查找，O(n)。
具體程式碼的實現如下：
1 public V get(Object key) {
2 Node<K,V> e;
3 return (e = getNode(hash(key), key)) == null ? null : e.value;
4 }
5
6 final Node<K,V> getNode(int hash, Object key) {
7 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
8 if ((tab = table) != null && (n = tab.length) > 0 &&
9 (first = tab[(n - 1) & hash]) != null) {
10 // 直接命中
11 if (first.hash == hash && // always check first node
12 ((k = first.key) == key || (key != null && key.equals(k))))
13 return first;
14 // 未命中
15 if ((e = first.next) != null) {
16 // 在樹中 getTreeNode() 不做深究
17 if (first instanceof TreeNode)
18 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
19 // 在鏈表中 通過.next() 循環獲取，知道找到滿足條件的key為止
20 do {
21 if (e.hash == hash &&
22 ((k = e.key) == key || (key != null && key.equals(k))))
23 return e;
24 } while ((e = e.next) != null);
25 }
26 }
27 return null;
28 }
get()程式碼實現
5. hash() 的實現
在對hashCode()計算hash時具體實現是這樣的：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
在get和put的過程中，計算下標時，先對hashCode進行hash操作，然後再通過hash值進一步計算下標，如下圖所示：
6.RESIZE的實現
當put時，如果發現目前的bucket佔用程度已經超過了Load Factor所希望的比例，那麼就會發生resize。在resize的過程，簡單的說就是把bucket擴充為2倍，之後重新計算index，把節點再放到新的bucket中。resize的注釋是這樣描述的：
Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.
大致意思就是說，當超過限制的時候會resize，然而又因為我們使用的是2次冪的擴展(指長度擴為原來2倍)，所以，元素的位置要麼是在原位置，要麼是在原位置再移動2次冪的位置。
7.總結
我們現在可以回答開始的幾個問題，加深對HashMap的理解：
1） 什麼時候會使用HashMap？他有什麼特點？
是基於Map介面的實現，存儲鍵值對時，它可以接收null的鍵值，是非同步的，HashMap存儲著Entry(hash, key, value, next)對象。
2） 你知道HashMap的工作原理嗎？
通過hash的方法，通過put和get存儲和獲取對象。存儲對象時，我們將K/V傳給put方法時，它調用hashCode計算hash從而得到bucket位置，進一步存儲，HashMap會根據當前bucket的佔用情況自動調整容量(超過Load Facotr則resize為原來的2倍)。獲取對象時，我們將K傳給get，它調用hashCode計算hash從而得到bucket位置，並進一步調用equals()方法確定鍵值對。如果發生碰撞的時候，Hashmap通過鏈表將產生碰撞衝突的元素組織起來，在Java 8中，如果一個bucket中碰撞衝突的元素超過某個限制(默認是8)，則使用紅黑樹來替換鏈表，從而提高速度。
3） 你知道get和put的原理嗎？equals()和hashCode()的都有什麼作用？
通過對key的hashCode()進行hashing，並計算下標( n-1 & hash)，從而獲得buckets的位置。如果產生碰撞，則利用key.equals()方法去鏈表或樹中去查找對應的節點
4） 你知道hash的實現嗎？為什麼要這樣實現？
在Java 1.8的實現中，是通過hashCode()的高16位異或低16位實現的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、品質來考慮的，這麼做可以在bucket的n比較小的時候，也能保證考慮到高低bit都參與到hash的計算中，同時不會有太大的開銷。
5） 如果HashMap的大小超過了負載因子(load factor)定義的容量，怎麼辦？
如果超過了負載因子(默認0.75)，則會重新resize一個原來長度兩倍的HashMap，並且重新調用hash方法。
關於Java集合的小抄中是這樣描述的：
以上部分參考：//blog.csdn.net/weixin_41272626/article/details/107629037
