不可不知的哈希映射
引言
hashmap這個東西呢，太老生常談了
開發中常用、面試中常問
總之，很重要。。。。。
接下來呢
咱們就一起來看下，裏面到底有哪些解不開的東西2.1 HashMap數據結構
目標：
HashMap 概念、數據結構回顧（JDK8和JDK7） & 為什麼1.8使用紅黑樹？
概念：
HashMap 是一個利用散列表（哈希表）原理來存儲元素的集合，是根據Key value而直接進行訪問的數據結構
在 JDK1.7 中，HashMap 是由 數組+鏈表構成的。
在 JDK1.8 中，HashMap 是由 數組+鏈表+紅黑樹構成
回顧： 數組、鏈表（優勢和劣勢）
數組: 優勢：數組是連續的內存，查詢快（o1） 劣勢：插入刪除O(N)
鏈表: 優勢：不是連續的內存，隨便插入（前、中間、尾部） 插入O(1) 劣勢：查詢慢O(N)
思考？
為什麼是JDK1.8 是數組+鏈表+紅黑樹？？？HashMap變化歷程
1.7的數據結構：鏈表變長，效率低 了！！！
1.8的數據結構：
數組+鏈表+紅黑樹
鏈表--樹（鏈長度>8、數組長度大於64）
備註：現在重點講map，不講樹的操作。樹在算法課裏有詳細學習
總結：
JDK1.8使用紅黑樹，其實就是為了提高查詢效率
因為，1.7的時候使用的數組+鏈表，如果鏈表太長，查詢的時間複雜度直接上升到了O(N)
2.2 HashMap繼承體系
目標：梳理map的繼承關係
<img src="assets/image-20201205220552037-1609839160181.png" alt="image-20201205220552037" style="zoom: 67%;" />
總結
HashMap已經繼承了AbstractMap而AbstractMap類實現了Map接口
那為什麼HashMap還要在實現Map接口呢？
據 java 集合框架的創始人Josh Bloch描述，這樣的寫法是一個失誤。
在java集合框架中，類似這樣的寫法很多，最開始寫java集合框架的時候，他認為這樣寫，在某些地方可能是有價值的，直到他意識到錯了。
顯然的，JDK的維護者，後來不認為這個小小的失誤值得去修改，所以就這樣存在下來
- Cloneable 空接口，表示可以克隆
- Serializable 序列化
- AbstractMap 提供Map實現接口
2.3 HashMap源碼深度剖析
1）目標：
通過閲讀HashMap（since1.2）源碼，我們可以知道以下幾個問題在源碼是如何解決的
（1）HashMap的底層數據結構是什麼？
（2）HashMap中增刪改查操作的底部實現原理是什麼？
（3）HashMap是如何實現擴容的？
（4）HashMap是如何解決hash衝突的？
（5）HashMap為什麼是非線程安全的？
2）測試代碼如下
package com.mmap;
import org.openjdk.jol.info.ClassLayout;
import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
public class MMapTest {
public static void main(String[] args) {
HashMap<Integer, String> m = new HashMap<Integer, String>();//尾插
//斷點跟蹤put
m.put(1, "001");
m.put(1, "002");
m.put(17, "003");//使用17可hash衝突（存儲位置相同）
System.out.println(ClassLayout.parseInstance(m).toPrintable());
//斷點跟蹤get
System.out.println(m.get(1));//返回002（數組查找）
System.out.println(m.get(17));//返回003（鏈表查找）
//斷點跟蹤remove
m.remove(1);//移除
System.out.println(m);
m.remove(1, "002");//和上面的remove走的同一個代碼
}
}
3）關於hashMap基本結構的驗證
先來個小驗證，幾乎地球人都知道map是 數組 + 鏈表 結構，那我們先來驗證一下
再來看debug結果：
驗證了基本結構，那為啥1和17就在一塊了？到底誰和誰放在一個鏈上呢？內部到底怎麼運作的？往下看 ↓
2.3.1 成員變量與內部類
目標：先了解一下它的基本結構
回顧：位運算（下面還會頻繁用到）
1<<4
二進制相當於1右邊補4個0：10000
十進制相當於1 x 2的4次方 ， 也就是 16
二進制運算是因為它的計算效率高
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //16，默認數組容量：左位移4位，即16
static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量：即2的30次冪
static final float DEFAULT_LOAD_FACTOR = 0.75f;//負載因子：擴容使用，統計學計算出的最合理的
static final int TREEIFY_THRESHOLD = 8;//鏈表轉紅黑樹閾值
static final int UNTREEIFY_THRESHOLD = 6;//當鏈表的值小<6, 紅黑樹轉鏈表
……
transient Node<K,V>[] table;//HashMap中的數組,中間狀態數據
transient Set<Map.Entry<K,V>> entrySet;//用來存放緩存,中間狀態數據;
transient int size;//size為HashMap中K-V的實時數量（重點）,注意！不是table的長度！
transient int modCount;//用來記錄HashMap的修改次數，幾個集合裏都有它
int threshold;//擴容臨界點；(capacity * loadFactor)（重點）
final float loadFactor;//負載因子 DEFAULT_LOAD_FACTOR = 0.75f賦值具體的key，value放在哪裏呢？答案是一個靜態內部類（1.8前是Entry）
static class Node<K,V> implements Map.Entry<K,V> {//數組和鏈表上的節點，1.8前叫Entry
final int hash;//擾動後的hash
final K key;//map的key
V value;//map的value
Node<K,V> next;//下個節點
Node(int hash, K key, V value, Node<K,V> next) { //構造函數，沒啥説的
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;//鏈表下一個
}
}
2.3.2 HashMap構造器
1）目標：學習下面的三個構造器，它們都幹了哪些事情？
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 負載因子DEFAULT_LOAD_FACTOR = 0.75f
} public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
} public HashMap(int initialCapacity, float loadFactor) {
//賦值，多了一些邊界判斷
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity); // 注意，map裏是沒有capacity這個類變量的！
}map的構造函數就做了幾個賦值這麼點事？這麼簡單？錯！接着往下看
2）無參構造函數驗證
第一步：添加以下debug變量
第二步：使用默認構造函數時，在put之前和之後分別debug以上變量信息對比看看
put之前：
<img src="pic/image-20210507164837142.png" alt="image-20210507164837142" style="zoom:50%;" />
之後
<img src="pic/image-20210507165029294.png" alt="image-20210507165029294" style="zoom:50%;" />
毫無違和感，那麼，我們接着往下！
3）自定義初始化參數驗證
接下來我們胡搞一下，讓容量=15，因子=0.5，猜一猜會發生什麼？
調試到put之後，再來看：
源碼剖析：
在有參數構造時，最終tableSizeFor
//capacity函數，初始化了table，就是table的length，否則取的是threshold
final int capacity() {
return (table != null) ? table.length :
(threshold > 0) ? threshold :
DEFAULT_INITIAL_CAPACITY;
}
//帶參數的初始化，其實threshold調用的是以下函數：
//這是什麼神操作？？？
//其實是將n轉成2進制，右移再和自己取或，相當於把裏面所有的0變成了1
//最終目的：找到>=n的，1開頭後面全是0的數。如果n=111 ， 那就是 1000 ； 如果n=100，那就是它自己
//而這個數，恰好就是2的指數，為後面的擴容做鋪墊
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; //到這一步n已經各個位都是1了。
//範圍校驗，小於0返回1，大於最大值返回最大值，絕大多數正常情況下，返回n+1，也就是10000……
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
調試案例：
package com.mmap;
public class TableSizeTest {
public static void main(String[] args) {
System.out.println(tableSizeFor(9)); //9的二進制更能看出以下變化
}
static final int tableSizeFor(int cap) {
System.out.println(Integer.toBinaryString(cap)); //1001
int n = cap - 1;
System.out.println(Integer.toBinaryString(n)); //1000
n |= n >>> 1; //無符號右移，前面補0
System.out.println(Integer.toBinaryString(n)); //右移再或，1100
n |= n >>> 2;
System.out.println(Integer.toBinaryString(n)); //再移動2位， 1111
n |= n >>> 4;
System.out.println(Integer.toBinaryString(n)); //就這麼長，再遷移也是1111
n |= n >>> 8;
System.out.println(Integer.toBinaryString(n));
n |= n >>> 16;
System.out.println(Integer.toBinaryString(n)); //Integer的最大長度32位，16折半後遷移全覆蓋
System.out.println(Integer.toBinaryString(n+1));
return n + 1; //+1後變為 10000 ，也就是16 ， 2的4次方
}
}
4）總結：
map的構造函數沒有你想象的那麼簡單！
- 無參構造時，容量=16，因子=0.75。第一次插入數據時，才會初始化table、閾值等信息
- 有參構造時，不會容忍你胡來，會取大於但是最接近你容量的2的指數倍（想一下為什麼？提示：和擴容規則有關）
- 無論哪種構造方式，擴容閾值最終都是 =（容量*因子）
2.3.3 HashMap插入方法
目標：圖解+代碼+斷點分析put源碼
1）先了解下流程圖
<img src="assets/map-put-1609730434509-1609839160182.jpg" alt="map-put" style="zoom:150%;" />
2）關於key做hash值的計算
當我們調用put方法添加元素時，實際是調用了其內部的putVal方法，第一個參數需要對key求hash值
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);//調用Map的putVal方法
}小提問：map裏所謂的hash是直接用的key的hashCode方法嗎？
static final int hash(Object key) {
int h;
//【知識點】hash擾動
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
圖解：
<img src="pic/Center.png" alt="img" style="zoom: 150%;" />
結論：使用移位和異或做二次擾動，不是直接用的hashCode！
3）核心邏輯
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {//onlyIfAbsent：true不更改現有值；evict：false表示table為創建狀態
//幾個臨時變量：
//tab=數組，p=插槽指針，n=tab的長度，i數組下標
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)//數組是否null或者==0，第1次put為空
//初始化數組(or擴容)，所以table是在這裏初始化的，不是new的時候！
//初始時，n=16
n = (tab = resize()).length; // resize，下面單獨講擴容
//【知識點】為何1 與 17 在一個槽上！秘密就藏在尋址這裏
if ((p = tab[i = (n - 1) & hash]) == null)//尋址：(n - 1) & hash（重要！）
tab[i] = newNode(hash, key, value, null);//當前插槽沒有值，空的！將新node直接扔進去
else { //有值，説明插槽上發生了碰撞，需要追加成鏈表了！
//還是臨時變量
//e=是否找到與當前key相同的節點，找到説明是更新，null説明是新key插入
//k=臨時變量，查找過程中的key在這裏暫存用
Node<K,V> e; K k;
if (p.hash == hash && //如果正好，插槽第一個節點（p），跟插入的key相同
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //就將它賦值給e，注意！這時候還沒覆蓋上去，只是標記到e，發現了相同key的節點！
else if (p instanceof TreeNode) //如果不是這個key，但是類型是一個紅黑樹節點
//這説明當前插槽的鏈很長，已經變成紅黑樹了，就調putTreeVal，扔到這顆樹上去
//樹的插入，這裏不贅述，在數據結構課中有
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);//然後把key封裝成新node追加到尾巴上
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，break跳出for循環，執行後面的邏輯
p = e;
}
}
if (e != null) { // 如果e非空，説明前面一頓猛如虎的操作後，找到了相同的key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;// 看看onlyIfAbsent，如果讓覆蓋那就覆蓋，不讓那就算了
afterNodeAccess(e);
return oldValue;// 返回覆蓋前的value值，也就是put方法的返回值
}
}
++modCount;//用來記錄HashMap的修改次數
if (++size > threshold)//key的數量是否大於閾值
resize();//如果size大於threshold，就需要進行擴容
afterNodeInsertion(evict);
return null;
}4）重點（尋址計算）：
接上文，關於hash值取得後，放入tab的哪個插槽，也就是所謂的尋址我們重點來講
(n - 1) & hash我們還是以開始的例子，1和17為例，他們的hash計算後正好是1和17本身，我們可以驗證一下
Integer i = new Integer(1);
Integer j = new Integer(17);
System.out.println(i.hashCode() ^ i.hashCode()>>16); //1
System.out.println(j.hashCode() ^ j.hashCode()>>16); //17開始位運算
默認n=16，n-1也就是15，二進制是 1111
那麼 15 & 1
1 1 1 1
0 0 0 1
與運算後 = 1
再來看15 & 17，17是 10001
1 1 1 1
1 0 0 0 1
與運算後 = 1
所以，1和17肯定會落在table的1號插槽上！兩者會成為鏈表，解釋了我們前面的案例
原理：不管你算出的hash是多少，超出tab長度的高位被抹掉，低位是多少就是你所在的槽的位置，也就是table的下標思考：為什麼不用mod（模運算）進行尋址？mod也能保證不會超出數組邊界，豈不是更簡單直觀？
package com.mmap;
public class CMod {
public static void main(String[] args) {
bit();
mod();
}
public static void bit() {
int a ;
long start = System.currentTimeMillis();
//同樣的計算次數，先位運算，後取餘
for (int i = 1; i < Integer.MAX_VALUE; i++) {
a = 1 & i;
}
long end = System.currentTimeMillis();
System.out.println("BIT耗時>>" + (end - start));
}
public static void mod() {
int a ;
long start = System.currentTimeMillis();
for (int i = 1; i < Integer.MAX_VALUE; i++) {
a = 1 % i;
}
long end = System.currentTimeMillis();
System.out.println("MOD耗時>>" + (end - start));
}
}跑一下試試？
結論：
一切為了性能
2.3.4 HashMap擴容方法
目標：圖解+代碼（map擴容與數據遷移）
注意：擴容複雜、繞、難
備註：線程不安全的
圖解： 假設我們 new HashMap(8)
遷移前：長度8 擴容臨界點6（8*0.75）
遷移過程
核心源碼resize方法
//注意！該方法兼容了初始化和擴容，所以比較難理清楚！
//需要對照上面的圖例來同步講解。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //舊的數組先拿出來
int oldCap = (oldTab == null) ? 0 : oldTab.length;//舊數組是null，那就是初始化咯
int oldThr = threshold;//擴容臨界點(舊)
int newCap, newThr = 0;//臨時變量，數組容量（新）、擴容臨界點(新)
if (oldCap > 0) {
// 擴容的時候調用
if (oldCap >= MAXIMUM_CAPACITY) { //如果舊值達到上限
threshold = Integer.MAX_VALUE; //擴容閾值也調到最大，從此再無意義
return oldTab; //不擴了，直接返回舊的。上限了還擴什麼擴
}
//如果沒到上限就計算新容量，注意這時候還沒發生實際的數組擴容，真正的擴容遷數據操作在下面
//將舊容量左移1位，也就是乘以2作為新容量，所以map是每次擴到之前的2倍
//鏈表是右移1位再加上舊長度，也就是擴為原來的1.5倍，注意區別
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 同時，閾值也乘以2，為下次擴容做準備
}
else if (oldThr > 0)
// HashMap(int initialCapacity, float loadFactor)初始化的時候調用
// 將cap和thres相等，約定
newCap = oldThr;
else {
// HashMap() 初始化的時候調用，注意前面驗證過了，是在第一次put的時候調的
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {//如果新閾值為0，根據負載因子設置新閾值
float ft = (float)newCap * loadFactor; // put之後的變化就在這裏
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) { //如果舊數組不為空，説明有數據要遷移
for (int j = 0; j < oldCap; ++j) { //遍歷數組
Node<K,V> e; //臨時變量，記錄當前指向的node
if ((e = oldTab[j]) != null) {
oldTab[j] = null;//gc處理
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;//只一個節點，賦值到新數組的索引下即可
else if (e instanceof TreeNode)// 如果變成了樹，拆成倆拼到新table上去
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //如果是鏈表，拆成兩個（重點！！！）
Node<K,V> loHead = null, loTail = null;//低位鏈表（原位置i）
Node<K,V> hiHead = null, hiTail = null;//高位鏈表（i+n位置）
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { //oldCap=8，2進製為1000
// 如果為0，説明e的hash沒超出舊cap長度去，在低位不動即可
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;//下標：原位置+原數組長度 （重點！）
//這地方詮釋了為什麼map要兩倍擴容，對應位置位運算後，加上原長度就行了
}
}
}
}
}
return newTab;//返回新數組
}
總結（擴容與遷移）：
1、擴容就是將舊錶的數據遷移到新表
2、遷移過去的值需要重新計算下標，也就是他的存儲位置
3、關於位置可以這樣理解：比如舊錶的長度8、新表長度16
舊錶位置4有6個數據，假如前三個hashCode是一樣的，後面的三個hashCode是一樣的
遷移的時候；就需要計算這6個值的存儲位置
4、如何計算位置？採用低位鏈表和高位鏈表；如果位置4下面的數據e.hash & oldCap等於0，
那麼它對應的就是低位鏈表，也就是數據位置不變
5、 e.hash & oldCap不等於0呢?就要重寫計算他的位置也就是j + oldCap，（4+8）= 12，就是高位鏈表位置（新數組12位置）
2.3.5 HashMap獲取方法
目標：圖解 （這個簡單！）
獲取流程
<img src="assets/map查找流程-1607499200869.jpg" alt="map查找流程" style="zoom:80%;" />
get主方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;// 重點在getNode
}getNode方法
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //一堆臨時變量，不管他
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 如果table對應的索引位置上有值
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;// 看下第一個元素的key是不是要查找的那個，是的話，返回即可
if ((e = first.next) != null) {//如果後面還有數據，那就繼續遍歷
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);//樹查找
do { //鏈表查找!!!!!
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}總結：
查詢思路比較簡單，如果是數組直接返回、如果是紅黑實例，就去樹上去找，最後，去做鏈表循環查找
2.3.6 HashMap移除方法
目標：圖解+斷點分析remove源碼
移除流程
tips：
兩個移除方法，參數上的區別
走的同一個代碼
移除方法：一個參數
public V remove(Object key) {
Node<K,V> e;//// 定義一個節點變量，用來存儲要被刪除的節點（鍵值對
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}移除方法：二個參數
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}核心方法removeNode
/**
* Implements Map.remove and related methods
*
* @param hash 擾動後的hash值
* @param key 要刪除的鍵值對的key，要刪除的鍵值對的value，該值是否作為刪除的條件取決於matchValue是否為true
* @param value key對應的值
* @param matchValue 為true，則當key對應的值和equals(value)為true時才刪除；否則不關心value的值
* @param movable 刪除後是否移動節點，如果為false，則不移動
* @return 返回被刪除的節點對象，如果沒有刪除任何節點則返回null
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) { //注意，p是當前插槽上的頭節點！
//第一步：查，和上面的get操作一毛一樣
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;// 如果key相同，説明是頭結點，將它賦給node
else if ((e = p.next) != null) {
//否則，沿着next一直查找
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);//紅黑查找
else {
do { //鏈表查找
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e; //如果找到，賦值給node，並終止
break;
}
p = e; // 如果沒找到，賦值給p，繼續下一輪。
} while ((e = e.next) != null);
// 最終while結束的時候，p（前置）-> node(要被刪)
}
}
//第二步：刪
//如果node不為空，説明根據key匹配到了要刪除的節點
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)// 不是樹，那如果 node == p 的意思是該node節點就是首節點
tab[index] = node.next;// 刪掉頭節點，第二個節點上位到數組槽上
else // p是node的前置，説明上面查找的時候走的do while
p.next = node.next;//如果不是，那就將p的後指針指向node的後指針，幹掉node即可
++modCount;//HashMap的修改次數遞增
--size;// HashMap的元素個數遞減
afterNodeRemoval(node);
return node;//返回刪除後的節點
}
}
return null;//找不到刪除的node，返回null
}
總結：
- 移除和查詢路線差不多，找到後直接remove
- 注意他的返回值，是刪除的那個節點的值
拓展：
為什麼説HashMap是線程不安全的
我們從前面的源碼分析也能看出，它的元素增刪改的時候，沒有任何加鎖或者cas操作。
而這裏面各種++和--之類的操作，顯然多線程下並不安全
那誰安全呢？下節課我們分析
本文由傳智教育博學谷 - 狂野架構師教研團隊發佈，轉載請註明出處！
如果本文對您有幫助，歡迎關注和點贊；如果您有任何建議也可留言評論或私信，您的支持是我堅持創作的動力
