特别說明：由于HashMap底層的紅黑樹結構比較複雜，是以涉及紅黑樹相關的操作，我單獨寫部落格為大家分享，文章最後會加上紅黑樹文章連結！
5.HashMap的成員方法
5.1 put(K key, V value)方法
put方法是比較複雜的，實作步驟大緻如下：
先通過 hash 值計算出 key 映射到哪個桶；
如果桶上沒有碰撞沖突，則直接插入；
如果出現碰撞沖突了，則需要處理沖突：
a 如果該桶使用紅黑樹處理沖突，則調用紅黑樹的方法插入資料；
b 否則采用傳統的鍊式方法插入。如果鍊的長度達到臨界值，則把鍊轉變為紅黑樹；
如果桶中存在重複的鍵，則為該鍵替換新值 value；
如果 size 大于門檻值 threshold，則進行擴容；
具體的方法如下：
public V put(K key, V value) {
// 調用hash(key)計算出key的hash值
return putVal(hash(key), key, value, false, true);
}
說明：
HashMap 隻提供了 put 用于添加元素，putVal 方法隻是給 put 方法調用的一個方法，并沒有提供給使用者使用。 是以我們重點看 putVal 方法。
我們可以看到在 putVal 方法中 key 在這裡執行了一下 hash 方法,來看一下 hash 方法是如何實作的。
static final int hash(Object key) {
int h;
// 如果key為null，則hash值為0,
// 否則調用key的hashCode()方法計算出key的哈希值然後指派給h,
// 後與h無符号右移16位後的二進制進行按位異或得到最後的hash值,
// 這樣做是為了使計算出的hash更分散
// 為什麼要更分散呢？因為越分散，某個桶的連結清單長度就越短，之後生成的紅黑樹越少，效率越高
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
從上面可以得知 HashMap 是支援 key 為空的，而 HashTable 是直接用 Key 來擷取hashCode 是以 key 為空會抛異常。
解讀上述 hash 方法：
我們先研究下 key 的哈希值是如何計算出來的。key 的哈希值是通過上述方法計算出來的。
這個哈希方法首先計算出 key 的 hashCode 指派給 h，然後與 h 無符号右移 16 位後的二進制進行按位異或得到最後的 hash 值。
在 putVal 函數中使用到了上述 hash 函數計算的哈希值：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
...
if ((p = tab[i = (n - 1) & hash]) == null) // 這裡的n表示數組長度16 ，公式
// (length - 1) & hash = 桶位下标 當數組長度為2的n次幂數時，
// 該公式相當于：hash % length 哈希值對數組長度取餘
// 例如：hash % 32 = hash & (32-1)
...
}
計算過程如下所示：
key.hashCode()；傳回散列值也就是 hashcode，假設随便生成的一個值。
n 表示數組初始化的長度是 16。
&（按位與運算）：運算規則：相同的二進制數位上，都是 1 的時候，結果為 1，否則為0。
^（按位異或運算）：運算規則：相同的二進制數位上，數字相同，結果為 0，不同為 1。
後獲得0101==> 下标為5的捅。
簡單來說就是：
高 16bit 不變，低 16bit 和高 16bit 做了一個異或（得到的 hashCode 轉化為 32 位二進制，前 16 位和後 16 位低 16bit 和高 16bit 做了一個異或）。
問題：為什麼要這樣操作呢？
如果當 n 即數組長度很小，假設是 16 的話，那麼 n - 1 即為 1111 ，這樣的值和 hashCode 直接做按位與操作，實際上隻使用了哈希值的後 4 位。如果當哈希值的高位變化很大，低位變化很小，這樣就很容易造成哈希沖突了，是以這裡把高低位都利用起來，進而解決了這個問題。
下面，我們來看看 putVal 方法，看看它到底做了什麼。
主要參數：
hash：key 的 hash 值
key：原始 key
value：要存放的值
onlyIfAbsent：如果 true 代表不更改現有的值
evict：如果為false表示 table 為建立狀态
putVal 方法源代碼如下所示：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;// 如果key是null 則hash值為0,否則調用key的hashCode()方法,并讓高16位參與整個hash異或，如果數組長度比較小的情況下，讓高16位也參與尋址，
// 尋址公式：(length - 1) & hash
// 這樣可以使計算出的結果更分散，不容易産生哈希沖突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
/*
1）transient Node<K,V>[] table; 表示存儲Map集合中元素的數組。
2）(tab = table) == null 表示将空的table指派給tab，然後判斷tab是否等于null，第一次肯定是null。
3）(n = tab.length) == 0 表示将數組的長度0指派給n，然後判斷n是否等于0，n等于0，由于if判斷使用雙或，滿足一個即可，則執行代碼 n = (tab = resize()).length; 進行數組初始化，并将初始化好的數組長度指派給n。
4）執行完n = (tab = resize()).length，數組tab每個空間都是null。
*/
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/*
1）i = (n - 1) & hash 表示計算數組的索引指派給i，即确定元素存放在哪個桶中。
2）p = tab[i = (n - 1) & hash]表示擷取計算出的位置的資料指派給結點p。
3) (p = tab[i = (n - 1) & hash]) == null 判斷結點位置是否等于null，如果為null，則執行代碼：tab[i] = newNode(hash, key, value, null);根據鍵值對建立新的結點放入該位置的桶中。
小結：如果目前桶沒有哈希碰撞沖突，則直接把鍵值對插入空間位置。
*/
if ((p = tab[i = (n - 1) & hash]) == null)
// 建立一個新的結點存入到桶中
tab[i] = newNode(hash, key, value, null);
else {
// 執行else說明tab[i]不等于null，表示這個位置已經有值了
Node<K,V> e; K k;
/*
比較桶中第一個元素(數組中的結點)的hash值和key是否相等
1）p.hash == hash ：p.hash表示原來存在資料的hash值 hash表示後添加資料的hash值 比較兩個hash值是否相等。
說明：p表示tab[i]，即 newNode(hash, key, value, null)方法傳回的Node對象。
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
而在Node類中具有成員變量hash用來記錄着之前資料的hash值的。
2）(k = p.key) == key ：p.key擷取原來資料的key指派給k key 表示後添加資料的key比較兩個key的位址值是否相等。
3）key != null && key.equals(k)：能夠執行到這裡說明兩個key的位址值不相等，那麼先判斷後添加的key是否等于null，如果不等于null再調用equals方法判斷兩個key的内容是否相等。
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
/*
說明：兩個元素哈希值相等，并且key的值也相等，
将舊的元素整體對象指派給e，用e來記錄
*/
e = p;
// hash值不相等或者key不相等；判斷p是否為紅黑樹結點
else if (p instanceof TreeNode)
// 放入樹中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 說明是連結清單結點
else {
/*
1)如果是連結清單的話需要周遊到最後結點然後插入
2)采用循環周遊的方式，判斷連結清單中是否有重複的key
*/
for (int binCount = 0; ; ++binCount) {
/*
1)e = p.next 擷取p的下一個元素指派給e。
2)(e = p.next) == null 判斷p.next是否等于null，等于null，說明p沒有下一個元素，那麼此時到達了連結清單的尾部，還沒有找到重複的key,則說明HashMap沒有包含該鍵，将該鍵值對插傳入連結表中。
*/
if ((e = p.next) == null) {
/*
1）建立一個新的結點插入到尾部
p.next = newNode(hash, key, value, null);
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
注意第四個參數next是null，因為目前元素插入到連結清單末尾了，那麼下一個結點肯定是null。
2）這種添加方式也滿足連結清單資料結構的特點，每次向後添加新的元素。
*/
p.next = newNode(hash, key, value, null);
/*
1)結點添加完成之後判斷此時結點個數是否大于TREEIFY_THRESHOLD臨界值8，如果大于則将連結清單轉換為紅黑樹。
2）int binCount = 0 ：表示for循環的初始化值。從0開始計數。記錄着周遊結點的個數。值是0表示第一個結點，1表示第二個結點。。。。7表示第八個結點，加上數組中的的一個元素，元素個數是9。
TREEIFY_THRESHOLD - 1 --》8 - 1 ---》7
如果binCount的值是7(加上數組中的的一個元素，元素個數是9)
TREEIFY_THRESHOLD - 1也是7，此時轉換紅黑樹。
*/
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 轉換為紅黑樹
treeifyBin(tab, hash);
// 跳出循環
break;
}
/*
執行到這裡說明e = p.next 不是null，不是最後一個元素。繼續判斷連結清單中結點的key值與插入的元素的key值是否相等。
*/
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循環
/*
要添加的元素和連結清單中的存在的元素的key相等了，則跳出for循環。不用再繼續比較了
直接執行下面的if語句去替換去 if (e != null)
*/
break;
/*
說明新添加的元素和目前結點不相等，繼續查找下一個結點。
用于周遊桶中的連結清單，與前面的e = p.next組合，可以周遊連結清單
*/
p = e;
}
}
/*
表示在桶中找到key值、hash值與插入元素相等的結點
也就是說通過上面的操作找到了重複的鍵，是以這裡就是把該鍵的值變為新的值，并傳回舊值
這裡完成了put方法的修改功能
*/
if (e != null) {
// 記錄e的value
V oldValue = e.value;
// onlyIfAbsent為false或者舊值為null
if (!onlyIfAbsent || oldValue == null)
// 用新值替換舊值
// e.value 表示舊值 value表示新值
e.value = value;
// 通路後回調
afterNodeAccess(e);
// 傳回舊值
return oldValue;
}
}
// 修改記錄次數
++modCount;
// 判斷實際大小是否大于threshold門檻值，如果超過則擴容
if (++size > threshold)
resize();
// 插入後回調
afterNodeInsertion(evict);
return null;
}
（1）計算key的hash值；
（2）如果桶（數組）數量為0，則初始化桶；
（3）如果key所在的桶沒有元素，則直接插入；
（4）如果key所在的桶中的第一個元素的key與待插入的key相同，說明找到了元素，轉後續流程（9）處理；
（5）如果第一個元素是樹節點，則調用樹節點的putTreeVal()尋找元素或插入樹節點；
（6）如果不是以上三種情況，則周遊桶對應的連結清單查找key是否存在于連結清單中；
（7）如果找到了對應key的元素，則轉後續流程（9）處理；
（8）如果沒找到對應key的元素，則在連結清單最後插入一個新節點并判斷是否需要樹化；
（9）如果找到了對應key的元素，則判斷是否需要替換舊值，并直接傳回舊值；
（10）如果插入了元素，則數量加1并判斷是否需要擴容；
5.2 擴容方法 resize()
擴容機制：
什麼時候才需要擴容？
當 HashMap 中的元素個數超過數組大小(數組長度)*loadFactor(負載因子)時，就會進行數組擴容，loadFactor 的預設值是 0.75。
HashMap 的擴容是什麼？
進行擴容，會伴随着一次重新 hash 配置設定，并且會周遊 hash 表中所有的元素，是非常耗時的。在編寫程式中，要盡量避免 resize。
HashMap 在進行擴容時，使用的 rehash 方式非常巧妙，因為每次擴容都是翻倍，與原來計算的 (n - 1) & hash 的結果相比，隻是多了一個 bit 位，是以結點要麼就在原來的位置，要麼就被配置設定到 “原位置 + 舊容量” 這個位置。
例如我們從 16 擴充為 32 時，具體的變化如下所示：
是以元素在重新計算 hash 之後，因為 n 變為 2 倍，那麼 n - 1 的标記範圍在高位多 1bit(紅色)，是以新的 index 就會發生這樣的變化。
5 是假設計算出來的原來的索引。這樣就驗證了上述所描述的：擴容之後是以結點要麼就在原來的位置，要麼就被配置設定到 “原位置 + 舊容量” 這個位置。
是以，我們在擴充 HashMap 的時候，不需要重新計算 hash，隻需要看看原來的 hash 值新增的那個 bit 是 1 還是 0 就可以了，是 0 的話索引沒變，是 1 的話索引變成 “原位置 + 舊容量” 。可以看看下圖為 16 擴充為 32 的 resize 示意圖：
正是因為這樣巧妙的 rehash 方式，既省去了重新計算 hash 值的時間，而且同時，由于新增的 1bit 是 0 還是 1 可以認為是随機的，在 resize 的過程中保證了 rehash 之後每個桶上的結點數一定小于等于原來桶上的結點數，保證了 rehash 之後不會出現更嚴重的 hash 沖突，均勻的把之前的沖突的結點分散到新的桶中了。
源碼 resize 方法的解讀
下面是代碼的具體實作：
正是因為這樣巧妙的 rehash 方式，既省去了重新計算 hash 值的時間，而且同時，由于新增的 1bit 是 0 還是 1 可以認為是随機的，在 resize 的過程中保證了 rehash 之後每個桶上的結點數一定小于等于原來桶上的結點數，保證了 rehash 之後不會出現更嚴重的 hash 沖突，均勻的把之前的沖突的結點分散到新的桶中了。
源碼 resize 方法的解讀
下面是代碼的具體實作：
————————————————
版權聲明：本文為CSDN部落客「興趣使然的草帽路飛」的原創文章，遵循CC 4.0 BY-SA版權協定，轉載請附上原文出處連結及本聲明。
原文連結：https://blog.csdn.net/weixin_43591980/article/details/109496637 （1）如果使用是預設構造方法，則第一次插入元素時初始化為預設值，容量為16，擴容門檻為12；
（2）如果使用的是非預設構造方法，則第一次插入元素時初始化容量等于擴容門檻，擴容門檻在構造方法裡等于傳入容量向上最近的2的n次方；
（3）如果舊容量大于0，則新容量等于舊容量的2倍，但不超過最大容量2的30次方，新擴容門檻為舊擴容門檻的2倍；
（4）建立一個新容量的桶；
（5）搬移元素，原連結清單分化成兩個連結清單，低位連結清單存儲在原來桶的位置，高位連結清單搬移到原來桶的位置加舊容量的位置；
5.3 删除方法 remove()
删除方法就是首先先找到元素的位置，如果是連結清單就周遊連結清單找到元素之後删除。如果是用紅黑樹就周遊樹然後找到之後做删除，樹小于 6 的時候要轉連結清單。
删除 remove() 方法：
// remove方法的具體實作在removeNode方法中，是以我們重點看下removeNode方法
// 根據key删除
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
// 根據key,value 删除
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
removeNode() 方法：
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// 參數：
// matchValue 當根據 key和value 删除的時候該參數為true
// movable 可以先不用考慮這個參數
// tab：引用目前haashMap中的散清單
// p：目前node元素
// n：目前散清單數組長度
// index：表示尋址結果
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 根據hash找到位置
// 如果目前key映射到的桶不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
// 進入這個if判斷内部，說明桶位是有資料的，需要進行查詢操作，并且執行删除
// node：通過查找得到的要删除的元素
// e：表示目前node的下一個元素
// k,v 鍵 值
Node<K,V> node = null, e; K k; V v;
// 第一種情況：目前桶位中的元素 即為我們要删除的元素
// 如果桶上的結點就是要找的key，則将node指向該結點
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 如果桶位中的頭一個元素不是我們要找的元素，且桶位中的e = p.next不為null
// 說明該桶位中的節點存在下一個節點
else if ((e = p.next) != null) {
// 說明：目前桶位，要麼是 連結清單，要麼是 紅黑樹
// 第二種情況：判斷桶位中是否已經形成了紅黑樹
if (p instanceof TreeNode)
// 說明是以紅黑樹來處理的沖突，則擷取紅黑樹要删除的結點
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
// 第三種情況：桶位中已經形成連結清單
else {
// 判斷是否以連結清單方式處理hash沖突
// 是的話則通過周遊連結清單來尋找要删除的結點
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 比較找到的key的value和要删除的是否比對
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 第一種情況：如果桶位中是紅黑樹，通過調用紅黑樹的方法來删除結點
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 第二種情況：如果桶位中是連結清單
else if (node == p)
// 連結清單删除
tab[index] = node.next;
// 如果桶位中
else
// 第三種情況：将目前元素p的下一個元素設定為 要删除元素的 下一個元素
p.next = node.next;
// 記錄修改次數
++modCount;
// 變動的數量
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
5.4 查找元素方法 get()
查找方法，通過元素的 key 找到 value。
代碼如下：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
get 方法主要調用的是 getNode 方法，代碼如下：
final Node<K,V> getNode(int hash, Object key) {
// tab：引用目前hashMap的散清單
// first：桶位中的頭元素
// e：臨時node元素
// n：table數組的長度
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 如果哈希表不為空，并且key對應的桶不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
/*
判斷數組元素是否相等
根據索引的位置檢查第一個元素
注意：總是檢查第一個元素
*/
// 第一種情況：定位出來的桶位元素 就是我們要get的資料
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 桶位第一個元素不是我們要找的目标元素，且first.next不為null
// 說明目前桶位不止一個元素，可能是連結清單，也可能是紅黑樹
if ((e = first.next) != null) {
// 第二種情況：桶位已經更新成了紅黑樹
// 判斷是否是紅黑樹，是的話調用紅黑樹中的getTreeNode方法擷取結點
if (first instanceof TreeNode)
// 調用與樹相關的方法得到目标元素
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 第三種情況：桶位已經形成連結清單
do {
// 不是紅黑樹的話，那就是連結清單結構了
// 通過循環的方法判斷連結清單中是否存在該key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 如果沒找到傳回null
return null;
}
小結：
get 方法實作的步驟：
a. 通過 hash 值擷取該 key 映射到的桶
b. 桶上的 key 就是要查找的 key，則直接找到并傳回
c. 桶上的 key 不是要找的 key，則檢視後續的結點：
如果後續結點是紅黑樹結點，通過調用紅黑樹的方法根據 key 擷取 value
如果後續結點是連結清單結點，則通過循環周遊連結清單根據 key 擷取 value
6. 周遊HashMap的幾種方式
分别周遊 Key 和 Values
for (String key : map.keySet()) {
System.out.println(key);
}
for (Object vlaue : map.values() {
System.out.println(value);
}
使用 Iterator 疊代器疊代
Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Object> mapEntry = iterator.next();
System.out.println(mapEntry.getKey() + "---" + mapEntry.getValue());
}
通過 get 方式（不建議使用）
Set<String> keySet = map.keySet();
for (String str : keySet) {
System.out.println(str + "---" + map.get(str));
}
根據阿裡開發手冊，不建議使用這種方式，因為疊代兩次。keySet 擷取 Iterator一次，還有通過 get 又疊代一次，降低性能。
- jdk8 以後使用 Map 接口中的預設方法：
default void forEach(BiConsumer<? super K,? super V> action)
// BiConsumer接口中的方法：
void accept(T t, U u) 對給定的參數執行此操作。
參數
t - 第一個輸入參數
u - 第二個輸入參數
周遊代碼：
HashMap<String,String> map = new HashMap();
map.put("001", "zhangsan");
map.put("002", "lisi");
map.forEach((key, value) -> {
System.out.println(key + "---" + value);
});
7.總結
（1）HashMap是一種散清單，采用（數組 + 連結清單 + 紅黑樹）的存儲結構；
（2）HashMap的預設初始容量為16（1<<4），預設裝載因子為0.75f，容量總是2的n次方；
（3）HashMap擴容時每次容量變為原來的兩倍；
（4）當桶的數量小于64時不會進行樹化，隻會擴容；
（5）當桶的數量大于64且單個桶中元素的數量大于8時，進行樹化；
（6）當單個桶中元素數量小于6時，進行反樹化；
（7）HashMap是非線程安全的容器；
（8）HashMap查找添加元素的時間複雜度都為O(1)；
關于HashMap紅黑樹操作，相關知識，之後很快就會更新…