【後端面經-Java】HashMap詳解
2023-06-25 21:01:12
目錄
1. HashMap的家族定位
介面java.util.Map有四個常用的實現類，如圖是它們之間的類繼承關係。
下面我將一一介紹其效能特點。
HashMap：- 最常用的Map實現類，通過使用Hash表結構，提高查詢速度；
- 使用鍵值對作為儲存節點，只允許一個key值為
null，允許多個value值為null； - 執行緒不安全，對於執行緒安全有要求的程式，可以考慮使用：sychronizedMap或者ConcurrentHashMap；
HashTable- 同樣使用Hash表結構，提高查詢效率；
- 執行緒安全，但是安全層級低於ConcurrentHashMap，不常用。
LinkedHashMap- 繼承自HashMap，使用Hash表結構，提高查詢效率；
- 連結串列插入維持插入順序。
TreeMap- sortedMap介面的實現類，可使用特定的排序規則對鍵值對進行排序；
對四種常見的實現類的效能比較如下圖所示：
2. HashMap的資料結構
2.1 Hash表的基本概念
Hash表是資料結構和演演算法課程中學習到的一種重要的資料結構。主要設計思想是：
- 使用一個長度為
n的陣列儲存相關資料。 - 使用
hash函數實現內容和陣列下標的對應，也就是hash函數的函數值為0~n之間。hash函數相同的輸入引數一定會產生相同函數值，不同內容儘量做到函數值分散。
- 在hash函數值對應的下標寫入該內容。
- 下次查詢某元素的時候，先根據
hash函數生成下標，然後再隨機存取陣列，這樣查詢效率大大提高了。
類似於一個叫賈斯汀·費爾蘭德·亨利皮特潘（複雜內容）的人，在酒店前臺（hash函數）入住酒店的房間編號是1004（hash函數值/陣列下標）。需要找他的人，只需要去酒店前臺查詢他住在1004房間，直接去1004房間找人就可以了，不需要一個一個房間去找。
2.2 Hash衝突
在上面的流程說明中，我們可以發現Hash表的實現關鍵就在於Hash函數，一個好的hash函數應該保證不同的輸入內容儘量分散其函數值。
當存入的資料過多，hash函數效能較差的時候，可能會出現hash衝突：
A和B是兩個不同的儲存內容，但是經過hash函數計算，得到的hash函數值相同，因此兩個內容儲存在陣列的同一位置。- 例如：
賈斯汀·費爾蘭德·亨利皮特潘和特朗普·懂王·建國同志兩個人在酒店前臺分配到的房間號都是1004，但是房間只有一張床，這時兩個人就會發生衝突。
解決衝突主要有兩種思路：
- 開放定址法：發生衝突的時候，後到來的元素放棄已被佔用的位置，尋找新的插入位置。（再找）
- 鏈地址法：發生衝突的時候，後到來的元素在原有位置的基礎上，使用連結串列的方式儲存。（排隊）
- HashMap使用的就是
鏈地址法。
- HashMap使用的就是
2.3 HashMap資料結構
-
節點Node
Node是HashMap的一個基本儲存單元，從原始碼中可見Node實現了Map.Entry介面，存放的是鍵值對。在JDK1.8中的原始碼中，Node的定義如下所示：static class Node<K,V> implements Map.Entry<K,V> { final int hash; //用來定位陣列索引位置 final K key; V value; Node<K,V> next; //連結串列的下一個node Node(int hash, K key, V value, Node<K,V> next) { ... } public final K getKey(){ ... } public final V getValue() { ... } public final String toString() { ... } public final int hashCode() { ... } public final V setValue(V newValue) { ... } public final boolean equals(Object o) { ... } } -
JDK1.7的HashMap資料結構
陣列+連結串列-
如圖所示
-
使用鏈地址方式解決hash衝突。
-
-
JDK1.8的HashMap資料結構
陣列+連結串列+紅黑樹-
如圖所示
-
對紅黑樹的學習可參考此部落格。
-
連結串列和紅黑樹的轉換根據連結串列長度閾值判斷，閾值為8，即連結串列長度大於8時，由連結串列轉換為紅黑樹，小於6時，由紅黑樹轉換為連結串列。
-
紅黑樹的引入目的：在連結串列長度較長的情況下，優化查詢效率。
-
3. HashMap的重要變數
3.1 常數
DEFAULT_INITIAL_CAPACITY- 預設的陣列初始容量，值為
2^4=16。 - 如果沒有指定初始陣列的容量的話，就會使用這個預設值。
- 預設的陣列初始容量，值為
MAXIMUM_CAPACITY- 最大的陣列容量，值為
2^30。 - 在擴容的時候，如果擴容後的容量大於這個值，就會使用這個值作為新的容量。
- 之後如果資料再增加，不再進行擴容，而是直接連結串列儲存或者轉為紅黑樹。
- 最大的陣列容量，值為
DEFAULT_LOAD_FACTOR- 預設負載因子，值為
0.75。 - 在HashMap中，擴容的臨界值計算公式為：
臨界值（threshold） = 負載因子（loadFactor） * 容量（capacity） - 負載因子可以設定為任意值，但是需要注意的是：
- 負載因子變大，hash衝突的概率就會變大，查詢效率就會降低。【犧牲時間】
- 負載因子過小，會導致陣列空間利用率低，浪費記憶體空間。【犧牲空間】
- 預設負載因子，值為
TREEIFY_THRESHOLD- 連結串列轉化為紅黑樹的閾值，值為
8。 - 當一個陣列節點所帶著的連結串列長度大於8時，連結串列會轉化為紅黑樹。
- 連結串列轉化為紅黑樹的閾值，值為
UNTREEIFY_THRESHOLD- 紅黑樹轉化為連結串列的閾值，值為
6。 - 當一個陣列節點的紅黑樹節點小於6時，紅黑樹會轉化為連結串列。
- 紅黑樹轉化為連結串列的閾值，值為
MIN_TREEIFY_CAPACITY- 轉換為紅黑樹的最小容量，值為
64。 - 這個變數的意思是，在HashMap不斷增加新元素的過程中，如果此時陣列中的元素個數小於64，那麼就選擇擴容。當陣列元素個數大於64的時候才會考慮樹化。
- 轉換為紅黑樹的最小容量，值為
3.2 變數
size- HashMap中儲存的鍵值對個數。
modCount- 對HashMap進行修改的次數記錄，每次增刪則加一。
threshold- 擴容的臨界值，計算公式為：
threshold = loadFactor * capacity。其中capacity為陣列總長度，通常為了提高閾值，會使用擴容增加capacity，而對於負載因子loadFactor，一般不會修改。
- 擴容的臨界值，計算公式為：
loadFactor- 負載因子，使用者可自行設定其值，否則等於預設值
0.75。
- 負載因子，使用者可自行設定其值，否則等於預設值
3.3 辨析size、capacity、threshold
size:實際儲存的鍵值對個數
capacity:陣列的總長度
threshold:擴容的臨界值
treeify_threshold/untreeify_threahold:連結串列和紅黑樹相互轉化的閾值
4. HashMap重要方法和原始碼解析
4.1 構造方法
- HashMap()
無參構造，使用預設的初始容量2^4和負載因子0.75，構造一個空的HashMap。
// 構造一個空的 HashMap，初始容量為 16，負載因子為預設值 0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
- HashMap(int initialCapacity)
指定初始容量，使用預設的負載因子0.75。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);//一次性實現容量和負載因子的賦值
}
- HashMap(int initialCapacity, float loadFactor)
指定初始容量和負載因子，構造一個空的HashMap。
public HashMap(int initialCapacity, float loadFactor) {
// 如果初始容量為負數，丟擲非負異常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
// 初始容量大於最大值時1<<30，則取最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 負載因子不能小於 0，並且必須是數位，否則拋異常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
//數值判斷合法之後，賦值
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);//tableSizeFor() 方法返回一個值，比initialCapacity大的最小2的冪。
}
- HashMap(Map<? extends K, ? extends V> m)
構造一個非空的HashMap，將m中的鍵值對存入HashMap中，預設的負載因子 0.75，使用預設的初始容量2^4。
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 將 Map 中的 key-value 賦值到新的 Map 中去
putMapEntries(m, false);
}
4.2 resize方法
當HashMap中陣列的使用量超過閾值的時候，就需要進行擴容。JDK1.8的原始碼如下所示：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;// 當前 table
int oldCap = (oldTab == null) ? 0 : oldTab.length;// 當前table的大小
int oldThr = threshold;// 當前 table 的 threshold
int newCap, newThr = 0;// 新的 table 的大小和閥值暫時初始化為 0
// 下面就是開始計算新的 table 的大小和閥值
// 第一種情況：當前 table 的大小大於 0，則意味著當前的 table 肯定是有資料的
if (oldCap > 0) {//
if (oldCap >= MAXIMUM_CAPACITY) {//原始容量大於最大容量，不再擴容，直接返回原始table
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)//翻倍之後不超過最大容量，原始容量小於最大容量，且大於預設容量，那麼容量翻倍，閾值也對應翻倍
newThr = oldThr << 1;
}
// 第二種情況：當前的 table 中無資料，但是閥值不為零，說明初始化的時候指定過容量或者閥值，但是沒有被 put 過資料，
else if (oldThr > 0)
newCap = oldThr;//此時的閥值就是陣列的大小，所以直接把當前的閥值當做新 table 的陣列大小即可。threshold = tableSizeFor(t);
// 第三種情況，這種情況就代表當前的 table 是呼叫的空參構造來初始化的，所有的資料都是預設值。
else {//初始閾值為0，表示使用預設值，新的 table 也只要使用預設值即可
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的閥值是 0，那麼就簡單計算一遍就行了
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 根據上文中計算的新表容量和閾值，初始化新的 table
// 這個 newTab 就是新的 table，陣列大小就是上面這一堆邏輯所計算出來的
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 遍歷當前 table，處理每個下標處的 bucket，將其處理到新的 table 中去
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 釋放當前 table 陣列的物件參照（for迴圈後，當前 table 陣列不再參照任何物件）
oldTab[j] = null;
// a、只有一個 Node，則直接 rehash 賦值即可
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// b、當前的 bucket 是紅黑樹，直接進行紅黑樹的 rehash 即可
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// c、當前的 bucket 是連結串列
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍歷連結串列中的每個 Node，分別判斷是否需要進行 rehash 操作
// (e.hash & oldCap) == 0 演演算法是精髓，充分運用了上文提到的 table 大小為 2 的冪次方這一優勢，下文會細講
do {
next = e.next;
// 根據 e.hash & oldCap 演演算法來判斷節點位置是否需要變更
// 索引不變
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原 bucket 位置的尾指標不為空(即還有 node )
if (loTail != null) {
// 連結串列末尾必須置為 null
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
// 連結串列末尾必須置為 null
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
- 為什麼要*2擴容？或者說，為什麼HashMap的陣列大小為2的冪
在理論學習中，Hash表的大小最好是素數，因為素數能夠有效降低hash碰撞。但是HashMap並沒有採用這種做法。
在上面的原始碼中，我們可以看到，HashMap在擴容的時候，陣列的大小都是原來的兩倍，這是因為在計算索引的時候，我們使用的是size-1的n個全1二進位制串和hash值進行與運算，這樣可以保證計算出來的索引值一定在0~size-1之間，不會越界。如圖所示：
當HashMap值為2的冪的時候，size-1為全1二進位制字串，且擴容之後，原本有衝突的兩個元素會找到各自的新索引位置。如圖所示：
在程式碼中，這個步驟被進一步簡化。如程式碼片段所示：
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
因為hash值是一個整數，所以hash & oldCap的結果要麼是0，要麼是oldCap。所以，hashMap的擴容，實際上是將原來的陣列分成兩部分，一部分的索引不變，一部分的索引變為原索引+oldCap。這樣就保證了原來的兩個元素，擴容之後，一定不會在同一個索引位置上。具體解釋如圖所示：
4.3 hash方法
也就是之前在理論部分所說的hash函數部分，將關鍵字key的值轉換為唯一hash值，JDK1.8原始碼如下:
static final int hash(Object key) {
int h;
// 高 16 位與低 16 位進行互斥或運算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hashCode()函數通常和equals()函數進行比較，hashCode()函數是根據物件的記憶體地址生成一個特定的數，因此，hashCode值相同的物件不一定相同，hashCode值不同的物件一定不相同。
一般判斷兩個物件是否相等，先使用hashCode()函數判斷記憶體地址，如果hashCode()函數值相同，再使用equals()函數判斷記憶體中的內容，如果hashCode()函數值不同，就不需要再使用equals()函數判斷了。
這裡h先設定成key值的hashCode，然後右移16位元，再和原來的h進行互斥或運算，這樣做的目的是為了減少hash碰撞，提高查詢效率。
之後如何從hash值對映到陣列下標，在JDK1.7的原始碼如下所示:
static int indexFor(int h, int length) {
return h & (length-1);
}
這裡也解釋了為什麼HashMap的陣列大小為2的冪，因為這樣可以保證length-1為全1的二進位制串，與操作之後計算出來的索引值一定在0~size-1之間，不會越界，具體操作如圖所示：
4.4 put方法
put方法主要是在HashMap中儲存鍵值對，JDK1.8原始碼如下所示：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);//重點在於putVal方法
}
// 引數 onlyIfAbsent,針對已經存在的value，值為true表示不修改；否則表示會替換原本的value值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// ① 如果當前 table 為空則進行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash 計算得到索引 i，演演算法在上文有提到，然後檢視索引處是否有資料
// ② 如果沒有資料，則新建一個新的 Node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 索引處有資料
else {
Node<K,V> e; K k;
// ③ 索引處的第一個 Node 的 key 和引數 key 是一致的，所以直接修改 value 值即可（修改的動作放在下面）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// ④ 索引處的 bucket 是紅黑樹，按照紅黑樹的邏輯進行插入或修改
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// ⑤ 索引處的 bucket 是連結串列
else {
// 遍歷連結串列上面的所有 Node
for (int binCount = 0; ; ++binCount) {
// 索引處的 Node 為尾鏈
if ((e = p.next) == null) {
// 直接新建一個 Node 插在尾鏈處
p.next = newNode(hash, key, value, null);
// 判斷是否需要轉換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 連結串列轉換為紅黑樹，此方法在上文中也有介紹
treeifyBin(tab, hash);
break;
}
// 當前 Node 的 key 值和引數 key 是一致的，即直接修改 value 值即可（修改的動作放在下面）
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 找到了相同 key 的 Node，所以進行修改 vlaue 值即可
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 修改 value 值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 修改操作，直接 return 結束掉程式碼邏輯
return oldValue;
}
}
// 記錄結構發生變化的次數
++modCount;
// ⑥ 判斷是否需要擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
// 新增的 Node，返回 null
return null;
}
原始碼所抽象出來的具體的put流程可如下圖所示：
在JDK1.7中，連結串列插入使用頭插法，而在JDK1.8中，連結串列插入使用尾插法，
- JDK1.7 使用頭插法的原因：考慮到熱點資料，後面插入的元素更有可能被最近使用，因此使用頭插法。
- 頭插法會使連結串列上 Node 的順序調轉，而尾插法則不會，另外，頭插法也會造成環形鏈死迴圈等問題，