HashMap----源碼解讀

源碼分析：

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable

在類的開頭聲明了幾個常量，以下是較為重要的：

/*** 定義初始容量大小為16*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 
?
/*** 定義最大容量為2^30*/
static final int MAXIMUM_CAPACITY = 1 << 30;
?
/*** 定義加載因子，與數組實時容量相乘會得到一個擴容閾值（threshold），當到達這個閾值時，將會進行擴容。*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
?
/*** 當鏈表元素增加到8時，轉化為紅黑樹提升查找效率
*/
?
static final int TREEIFY_THRESHOLD = 8;
?
/*** 當紅黑樹元素減少到6時，退化為鏈表
*/
static final int UNTREEIFY_THRESHOLD = 6;
?
/*** 只有當哈希表的總容量至少為64時，才可能將鏈表轉換為紅黑樹。
*/
static final int MIN_TREEIFY_CAPACITY = 64;

以下是定義的一些成員變量：

/*** 這是HashMap存儲數據的哈希表，它是一個數組，每個元素是一個鏈表的頭節點或者紅黑樹的*/
transient Node<K,V>[] table;
?
/*** 這是一個緩存，用于存儲HashMap中所有鍵值對（Entry）的集合視圖。*/
transient Set<Map.Entry<K,V>> entrySet;
?
/*** 這個字段表示HashMap中鍵值對的總數。*/
transient int size;
?
/*** 這個字段記錄了HashMap結構上被修改的次數，包括添加、刪除操作，或者重新哈希（rehash）等。* 它用于實現快速失敗（fail-fast）機制，當HashMap在迭代過程中被修改時，會拋出*/
transient int modCount;
?
/**
這個字段表示HashMap能夠容納的最大元素數量，達到這個數量時，HashMap會進行擴容（resize）。它等于數組的容量乘以加載因子（load factor）。如果哈希表還沒有被分配，這個字段可以表示初始數組容量或0，0代表使用默認的初始容量。*/
int threshold;
?
/**
這個字段是HashMap的加載因子，它決定了HashMap何時進行擴容操作。加載因子是HashMap中元素數量與數組長度的比例。當HashMap中的元素數量超過了capacity * loadFactor時，HashMap會進行擴容。默認的加載因子是0.75，這是一個空間和時間成本之間的折中。*/
final float loadFactor;

對于鏈表元素，會將其存儲在一個叫Node的內部類中，對于紅黑樹元素，會被存儲與TreeNode內部類中：

static class Node<K,V> implements Map.Entry<K,V> {final int hash;//hash值final K key;//鍵V value;//值Node<K,V> next;//指向下一個元素...
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent;// 父節點TreeNode<K,V> left;//左子樹TreeNode<K,V> right;//右子樹TreeNode<K,V> prev;// 這是一個指向當前節點的前一個節點的引用。這個字段主要用于在刪除節點時，能夠從雙向鏈表中移除當前節點。由于HashMap中的紅黑樹節點也是雙向鏈表的一部分，所以這個字段是必要的。boolean red;//是否轉為紅色...
}

在初始化的時候，我們查看其中的一個無參構造：

public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // 在調用無參構造，只對加載因子做了初始化，其他都沒有初始化。
}

當我們進行插入元素時，我們會調用put方法進行添加元素，傳入鍵值對：

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);//依次參數是// 1.對鍵進行hash（計算鍵的哈希值以確定它應該存儲在哪個桶中）// 2.鍵// 3.值// 4.是否保留（false時重復會進行覆蓋）// 5.這個布爾值參數用于LinkedHashMap，它指示在插入后是否需要執行額外的操作。在HashMap中，這個參數通常被忽略，因為它不是用來控制標準HashMap行為的。在LinkedHashMap中，這個參數用于確定是否在插入后移除最舊的條目
}

接著我們進入putVal方法查看：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//由于table是成員變量放在堆中，而方法在棧中，所以定義一個局部變量（同樣存在于棧中）提高效率Node<K,V>[] tab; //指向當前數組位置Node<K,V> p; //n為數組容量，i為以hash值與數組長度運算得到的插入位置索引（桶索引）int n, i;//對tab進行賦值并且判斷是否為空，其實就是對我們的數組判斷是否為空（還沒初始化），調用resize函數進行初始化：if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//判斷在數組中，該位置是否為空，為空直接插入if ((p = tab[i = (n - 1) & hash]) == null)//將我們的元素插入到數組中。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，后續可以用來更新該節點的值。e = p;//如果存在的元素的類型是紅黑樹節點else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//在原來元素的基礎上進行鏈表插入的操作else {//這里開始了一個無限循環，binCount用于記錄當前桶中的節點數量。循環將遍歷鏈表中的節點，直到找到合適的插入位置。for (int binCount = 0; ; ++binCount) {
//在循環內部，首先檢查當前節點p的下一個節點e是否為null。如果是null，說明已經到達鏈表的末尾，可以在這里插入新的節點。if ((e = p.next) == null) {//在存在元素上使用尾插法進行插入新元素p.next = newNode(hash, key, value, null);//達到樹化閾值，對當前哈希桶轉換為紅黑樹if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);//插入超過即breakbreak;}
//在遍歷鏈表的過程中，如果找到了一個具有相同哈希值和鍵的節點，這意味著找到了一個已經存在的鍵。
//如果鍵相等（通過==比較或者equals方法），循環會通過break終止。if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;//如果沒有找到相等的鍵，或者還沒有到達鏈表末尾，p會更新為下一個節點e，繼續循環。p = e;}}//經過上訴操作之后，如果e不為null則說明已經找到了重復元素if (e != null) { // existing mapping for keyV oldValue = e.value;//判斷是否要進行覆蓋，因為重復時e指向的是重復元素，此時進行重復元素value的覆蓋if (!onlyIfAbsent || oldValue == null)e.value = value;//這個方法在HashMap類中是空的，用于LinkedHashMap的位置調整，因為有重復元素覆蓋則涉及一個插入順序打亂afterNodeAccess(e);//返回舊值return oldValue;}}++modCount;//大于閾值則調用resize準備擴容if (++size > threshold)resize();//它在節點被插入后調用。這個方法在HashMap類中是空的，但在LinkedHashMap中會被覆蓋以維護節點的插入順序。afterNodeInsertion(evict);//正常插入返回nullreturn null;
}

在resize方法中，由于我們的容量等于零，所以他會執行其中的：

{ ? ? ? ? ? ? ? newCap = DEFAULT_INITIAL_CAPACITY;//給我們的容量賦值默認容量16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//給我們的閾值賦值為容量乘以加載因子
}
threshold = newThr;//賦值給成員變量
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//此時才開始初始化存放鏈表或者紅黑樹的數組table = newTab;//將其賦值給成員變量table
...
return newTab;最后將我們的新數組進行返回。

以上是其中的一種情況，在resize中有三種情況，以下是其他兩種：

//當舊容量大于0，此時調用到resize則說明需要進行擴容操作
if (oldCap > 0) {//判斷舊容量有沒有超過最大，超過則設置閾值為Int最大，表示再也不會擴容了。if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//開始擴容，讓新容量左移一位即為2倍操作，并進行判斷新容量有沒有超過閾值。else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)//如果以上判斷通過則將新閾值變為舊閾值的兩倍newThr = oldThr << 1; // double threshold
}
//當舊閾值大于零且不滿足舊容量大于零（以上情況），則說明在創建hashMap時進行了初始化容量，當插入元素時會調用resize來到這個if
else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;

當擴容之后我們會對對應的成員變量進行賦值，并且讓舊數組的元素拷貝到新數組中去：

//閾值更新，即下一次擴容時機
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//創建新數組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//將成員變量table賦值新數組
table = newTab;
//這里判斷，只要不是初始化就要快開始數組拷貝
if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {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 orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;//低位：落在新容量的（0，舊容量大小）區域//高位：落在新容量的（舊容量大小，兩倍舊容量）區域//先使用其hash值判斷它在高位區還是低位區，hash與舊容量相與等于零則說明其在低位。//判斷后，就可以把j索引下的一整條鏈表進行復制//復制過程就是自己造一條新鏈表，如落在低位時：//先使用lohead將頭節點保存，其次用lotail.next在循環中將整條鏈表進行連接//整條鏈表復制好了，即走完了dowhile，此時再一次判斷是高位還是低位（判斷高或低有沒有為空）不為空則為高或低位。//如果是低位直接將頭節點插入到新容量數組的j索引處，如果是高位則將頭節點插入在新容量（j+舊容量大小）索引處do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;}}}}
}
return newTab;