HashMap詳細解釋+全站最硬核手撕原始碼分析
1.HashMap基礎入門
1.陣列的優勢/劣勢
優勢：
1.按照索引查詢元素速度很快
2.能存盤大量資料
3.按照索引遍歷陣列方便
劣勢：
1.根據內容查詢元素速度慢
2.陣列的大小一旦給定就不能改變
3.陣列只能存盤一種型別的資料
4.增加、洗掉元素效率慢
2.鏈表的優勢/劣勢
優勢：
1.插入洗掉速度快
2.內容利用率高，不會浪費記憶體
3.大小不固定，擴展性靈活
劣勢：
1.不支持隨即查找，必須從第一個開始遍歷，查找效率低
2.鏈表中存盤元素需要更多的記憶體，因為在鏈表中每個結點都包含一個指標，他需要額外的記憶體
3.有沒有一種方式整合兩種資料結構的優勢？
散串列
4.什么是散串列？散串列有什么特點？
? 散串列（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的資料結構，也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度，這個映射函式叫做散列函式，存放記錄的陣列叫做散串列，
給定表M，存在函式f(key)，對任意給定的關鍵字值key，代入函式后若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函式f(key)為哈希(Hash) 函式，
特點：
1.訪問速度很快：由于散串列有散列函式，可以將指定的 Key 都映射到一個地址上，所以在訪問一個 Key（鍵）對應的 Value（值）時，根本不需要一個一個地進行查找，可以直接跳到那個地址，所以我們在對散串列進行添加、洗掉、修改、查找等任何操作時，速度都很快，
2.需要額外的空間：首先，散串列實際上是存不滿的，如果一個散串列剛好能夠存滿，那么肯定是個巧合，而且當散串列中元素的使用率越來越高時，性能會下降，所以一般會選擇擴容來解決這個問題，另外，如果有沖突的話，則也是需要額外的空間去存盤的，比如鏈地址法，不但需要額外的空間，甚至需要使用其他資料結構，
3.無序：散串列還有一個非常明顯的特點，那就是無序，為了能夠更快地訪問元素，散串列是根據散列函式直接找到存盤地址的，這樣我們的訪問速度就能夠更快，但是對于有序訪問卻沒有辦法應對，
4.可能會產生碰撞(沖突)：沒有完美的散列函式，無論如何總會產生沖突，這時就需要采用沖突解決方案，這也使散串列更加復雜，通常在不同的高級語言的實作中，對于沖突的解決方案不一定一樣，
5.什么是哈希？哈希的特點
核心理論：Hash也稱散列、哈希，對應的英文都是Hash，基本原理就是把任意長度的輸入，通過Hash演算法變成固定長度的輸出，這個映射的規則就是對應的Hash演算法，而原始資料映射后的二進制串就是哈希值，
特點：
1.從hash值不可以反向推導出原始的資料
2.輸入資料的微小變化會得到完全不同的hash值，相同的資料會得到相同的值
3.哈希演算法的執行效率要高效，長的文本也能快速地計算出哈希值
4.hash演算法的沖突概率要小
注：由于hash的原理是將輸入空間的值映射成hash空間內，而hash值的空間遠小于輸入的空間，根據抽屜原理，一定會存在不同的輸入被映射到相同的輸出的情況，
2.HashMap原理講解
1.HashMap的繼承體系是什么樣的？
2.Node資料結構分析
Node類是HashMap的一個靜態內部類，實作了 Map.Entry<K,V>介面，在呼叫put方法創建一個新的鍵值對時，會呼叫newNode方法來創建Node物件，
node中包含一個next變數，這個就是鏈表的關鍵點，hash結果相同的元素就是通過這個next進行關聯的，
static class Node<K,V> implements Map.Entry<K,V> {
//繼承自Entry，Entry主要有getKey():K,getValue():V,setValue(V):V
final int hash;
final K key;
V value;
Node<K,V> next;//建構式Hash值 鍵 值 下一個節點
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//判斷兩個node是否相等,若key和value都相等，回傳true，可以與自身比較為true
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
3.底層存盤結構介紹
4.put資料原理分析
5.什么是Hash沖突?
哈希是通過對資料進行再壓縮，提高效率的一種解決方法，但由于通過哈希函式產生的哈希值是有限的，而資料可能比較多，導致經過哈希函式處理后仍然有不同的資料對應相同的值，這時候就產生了哈希沖突，
6.拉鏈法
解決沖突的方法有很種，拉鏈法是其中之一，
拉鏈法解決沖突的做法是： 將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中 ，若選定的散串列長度為m，則可將散串列定義為一個由m個頭指標組成的指標數 組T[0…m-1]，凡是散列地址為i的結點，均插入到以T[i]為頭指標的單鏈表中，T中各分量的初值均應為空指標，在拉鏈法中，裝填因子α可以大于 1，但一般均取α≤1，
7.HashMap在jdk8為什么引入紅黑樹?
在jdk1.8版本后，Java對HashMap做了改進，在鏈表長度大于8的時候，將后面的資料存在紅黑樹中，以加快檢索速度，
紅黑樹的插入、洗掉、查找各種操作性能都比較穩定，使得鏈表（記憶體使用率高）+紅黑樹（高校檢索）這種資料結構很強大，
紅黑樹的具體內容較多，后續可能會專門更新我對紅黑樹的理解，
8.HashMap擴容原理
我們都知道Java中陣列是無法自動擴容的，HashMap的方法是使用一個新的陣列代替原有的陣列，對原陣列的所有資料進行重新計算插入新陣列，之后指向新陣列；如果擴容前陣列已經達到最大了，那么將直接將閾值設定成最大整形return，擴容是為了使查找的均攤復雜度將為O(1)，
HashMap每次擴容增長一倍，例如HashMap初始容量為16，加載因子0.75，當容量達到12的時候進行擴容，擴容到2的5次冪，
3.HashMap構造方法原始碼分析
//我們首先需要弄清楚幾個定義值的含義
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//16
//默認table大小為16
static final int MAXIMUM_CAPACITY = 1 << 30;//1073741824
//table最大長度：1 073 741 824
/*
左移的運算規則：按二進制形式把所有的數字向左移動對應的位數，高位移出（舍棄），低位的空位補零，
計算1<<30,首先把1轉為二進制數字 0000 0000 0000 0000 0000 0000 0000 0001
然后將上面的二進制數字向左移動30位后面補0得到 0010 0000 0000 0000 0000 0000 0000 0000
二進制再轉化為十進制得到1 073 741 824
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//默認負載因子大小：0.75
static final int TREEIFY_THRESHOLD = 8;
//樹化閾值
static final int UNTREEIFY_THRESHOLD = 6;
//樹降級成為鏈表的閾值
static final int MIN_TREEIFY_CAPACITY = 64;
//樹化的另一個引數：陣列長度達到64時（桶的數量）
transient int size;//當前哈希表種元素個數
transient int modCount;//當前哈希表結構修改次數
int threshold;//擴容閾值，當你的哈希表中的元素超過閾值時，就會觸發擴容
final float loadFactor;//負載因子 threshold = capacity * loadFactor
//在jdk1.8版本中HashMap有四個構造方法，根據引數內容我們可以發現實質上就是一個套娃
public HashMap(int initialCapacity, float loadFactor) {
//做了一些邏輯校驗，capacity必須大于0&&最大值不可以超過MAXIMUM_CAPACITY
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//loadFactor（負載因子）必須大于零&&必須是個數不能是NaN
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;//初始化填充因子
this.threshold = tableSizeFor(initialCapacity);
//分析tableSizeFor方法的原始碼可以知道（有興趣的小伙伴可以自己試著分析下，里面主要運用到了移位運算子），該方法的回傳值必須是一個大于等于當前引數的一個數字并且這個數字一定是2的次方數(這樣的數有助于提高hash函式的執行效率)，如傳入7會回傳8(2的三次方)，傳入9會回傳16(2的4次方)，
}
--------------------------------------------------------------------------------public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
--------------------------------------------------------------------------------public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 所有其他欄位均為默認值
}
--------------------------------------------------------------------------------public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
//putMapEntries(Map<? extends K, ? extends V> m, boolean evict)函式將m的所有元素存入本HashMap實體中，
4.HashMap put方法原始碼分析
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
---------------------------------------------------------------------------------
static final int hash(Object key) {
/*擾動函式：讓key的hash值的高16位也參與路由運算(上圖左下角有具體運算方法)
作用：減少哈希沖突的概率
異或：相同回傳0，不同回傳1
h = 0b 0010 0101 1010 1100 0011 1111 0010 1110
0b 0010 0101 1010 1100 0011 1111 0010 1110
^
0b 0000 0000 0000 0000 0010 0101 1010 1100
=> 0010 0101 1010 1100 0001 1010 1000 0010
*/
//簡單來說：讓高位參與運算后，再 & length-1 讓 index 更加均勻散列，這樣就可以減少沖突
int h;
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; //參考當前hashMap的散串列
Node<K,V> p; //表示當前散串列的元素
int n, i;//n表示散串列陣列的長度，i表示路由尋址 結果
if ((tab = table) == null || (n = tab.length) == 0)//延遲初始化邏輯，第一次呼叫putVal時會初始化hashMap物件中的最耗費記憶體的散串列
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)//最簡單的一種情況：尋址找到的桶位剛好是null，這個時候，直接將當前的node扔進去就行了，
tab[i] = newNode(hash, key, value, null);
else {
//e:不為null的話，找到一個與當前要插入的key-value一致的key的元素，k：表示臨時的一個key
Node<K,V> e; K k;
//表示桶位中的該元素，與你當前插入的元素的key完全一致，后續需要替換操作
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 {//鏈表的情況，而且鏈表的頭元素與我們要插入的key不一致，（尾插法）
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);//前面有8個元素，要樹化了~
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//條件成立的話，說明找到了相同key的node元素，需要進行替換操作
p = e;
}
}
if (e != null) {
// e！=null，條件成立說明，找到了一個與你插入元素key完全一致的資料，需要進行替換，
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//表示散串列結構被修改的次數，替換node元素的value不計數
if (++size > threshold)//假如容量不夠，就擴容
resize();
afterNodeInsertion(evict);
return null;
}
附一張流程圖：
圖片轉載自：
[https://www.cnblogs.com/xiaoxi/p/7233201.html]:
5.HashMap resize擴容方法原始碼分析
為什么需要擴容：為了解決哈希沖突導致的鏈化影響查詢效率（空間換時間）極限思維：假如桶的數量很少，而存入的內容又很多，那么在查找的時候就和在鏈表中查找沒啥區別了，所以一定要擴容，增加桶的數量，減少擁擠，
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//oldTab：參考擴容前的哈希表
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//oldCap表示擴容之前table陣列的長度
int oldThr = threshold;//表示擴容之前的擴容閾值，觸發本此擴容的閾值
int newCap, newThr = 0;//newCap表示擴容之后table陣列的小大
//newThr：擴容之后，下次再次觸發擴容的條件
//條件如果成立說明 hashmap中的散串列已經初始化過了，是一次正常的擴容
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
//比最大的長度還大，無法擴容
threshold = Integer.MAX_VALUE;
return oldTab;
}
//newCap = oldCap << 1 左移一位實作數值翻倍，并且賦值給newCap，newCap小于陣列最大值限制且擴容之前的閾值>=16，這種情況下，則下一次擴容的閾值等于當前閾值翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; //閾值跟著翻倍
}
//oldCap==0，說明hashmap中的散串列是null
else if (oldThr > 0)
newCap = oldThr;
//oldCap==0
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//newThr為零時，通過newCap和loadFactor計算出一個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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//說明，hashmap本此擴容之前，table不為null
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;//當前node節點
if ((e = oldTab[j]) != null) {
//說明當前桶位中有資料，但是資料具體是單個資料，鏈表，紅黑樹，還不知道，
oldTab[j] = null;//置空，方便JVM GC回收記憶體
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 { // 鏈表情況
//低位鏈表：存放在擴容之后的陣列的下標位置與當前陣列的下標位置一致
//高位鏈表：存放在擴容之后的陣列的下標位置為當前陣列下標位置+擴容之前的陣列長度
//舉個例子：當前容量為16 則擴容后對應的容量為32，而原本15號位置（最后一個，因為從0開始）的鏈表中的資料在新哈希表中可能位于15(低位鏈表),可能位于31(15+16高位鏈表)，具體用到的還是位運算子，有興趣的讀者可以自己研究一下，
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//oldCap高位一定是1，這里依據hash高位值來判斷呼叫哪個陳述句，假如是1，就呼叫else 是0 就呼叫if（這里需要想一下，有點不好理解）
if ((e.hash & oldCap) == 0) {
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;//設定為null是因為低位的下一個是高位，需要設定位null
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
6.HashMap get方法和remove方法原始碼分析
get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; //tab：參考當前hashMap的散串列
Node<K,V> first, e;//first：桶位中的頭元素 e是一個臨時node元素
int n; K k;//n：table陣列長度
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {//有資料
if (first.hash == hash && // 第一種情況：定位出來的桶位元素 即為我們需要get的資料
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//說明當前桶位不止一個元素，可能是鏈表也可能是紅黑樹
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;
}
remove方法
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
//matchValue：僅在value，key均匹配才洗掉
Node<K,V>[] tab; //tab：參考當前hashmap中的散串列
Node<K,V> p; //p：當前node元素
int n, index;//n:表示散串列陣列長度 index表示尋址結果
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//有資料才洗掉，沒資料就呵呵
//p是指向某個桶位
Node<K,V> node = null, e; //node表示查找到的結果 e表示當前node的下一個元素
K k; V v;
//第一種情況：當前桶位中的元素 即為 你要洗掉的元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//第二種情況：當前桶位后面有鏈表或者紅黑樹
else if ((e = p.next) != null) {
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;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//洗掉相關邏輯
//判斷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)//第二種情況：當前桶位元素即為洗掉元素
tab[index] = node.next;
else//第三種情況：鏈表中的洗掉，不懂的小伙伴自己復習下鏈表的洗掉
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
7.HashMap replace方法原始碼分析
沒啥可撕的，原代碼如下：
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
今天的分享就到這里了，歡迎大家在評論區討論，如果覺得本文寫的不錯，給個三連叭~
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/267365.html
標籤：java
下一篇：反射機制