HashMap#
一、基礎概念#
在 JDK8 及以後的版本中，HashMap 引入了紅黑樹結構，其底層的資料結構變成了由
數組+鏈表變成數組+鏈表和數組+紅黑樹
HashMap 整體結構:
JDK1.8 後 HashMap 的紅黑樹結構
紅黑樹的轉換#
參考: https://juejin.im/entry/5839ad0661ff4b007ec7cc7a
幾個參數:
//一個桶的樹化閾值, 當桶中元素個數超過這個值時，需要使用紅黑樹節點替換鏈表節點
static final int TREEIFY_THRESHOLD = 8;
//一個樹的鏈表還原閾值, 當擴容時，桶中元素個數小於這個值，就會把樹形的桶元素 還原（切分）為鏈表結構
static final int UNTREEIFY_THRESHOLD = 6;
//哈希表的最小樹形化容量, 當哈希表中的容量大於這個值時，表中的桶才能進行樹形化,否則桶內元素太多時會擴容，而不是樹形化
//為了避免進行擴容、樹形化選擇的衝突，這個值不能小於 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
添加元素時，默認如果桶中鏈表個數超過 7，鏈表會嘗試轉換成紅黑樹：
// 如果HashMap容量小於64，會選擇擴容而不是直接將其轉變成紅黑樹
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
resize();
}
// TREEIFY_THRESHOLD 默認為8
if (binCount >= TREEIFY_THRESHOLD - 1) {
treeifyBin(tab, hash);
}
當調用 risize 方法 () 擴容時，如果當前桶中元素結構是紅黑樹，並且元素個數小於鏈表還原閾值 UNTREEIFY_THRESHOLD （默認為 6），就會調用 split () 方法把桶中的樹形結構縮小或者直接還原（切分）為鏈表結構:
if (lc <= UNTREEIFY_THRESHOLD) {
tab[index] = loHead.untreeify(map);
}
二、HashMap 的默認參數理解#
為什麼 HashMap 的 Entry 數組長度默認為 16 呢？為什麼數組長度一定要是 2 的 n 次幂呢？#
首先看 HashMap 計算 hashcode 的方法獲取存儲的位置方法：
static int indexFor(int h, int length) {
return h & (length-1);
}
長度 16 或者其他 2 的幂，length - 1 的值是所有二進制位全為 1, 這種情況下，index 的結果等同於 hashcode 後幾位的值，只要輸入的 hashcode 本身分佈均勻，hash 算法的結果就是均勻的
所以：HashMap 的默認長度為 16 和規定數組長度為 2 的幂，是為了降低 hash 碰撞的幾率
HashMap 擴容限制的負載因子為什麼是 0.75？#
HashMap 中擴容方式是通過新建一個長度為之前數組 2 倍的新的數組，然後將當前的 Entry 數組中的元素全部傳輸過去，擴容後的新數組長度為之前的 2 倍，所以擴容相對來說是個耗資源的操作
擴容的觸發條件是: 臨界值 = 數組默認的長度 x 負載因子
- 如果負載因子為 0.5 甚至更低的可能的話，最後得到的臨時臨界值明顯會很小，這樣的情況就會造成分配的內存的浪費，存在多餘的沒用的內存空間，也不滿足了哈希表均勻分佈的情況
- 如果負載因子達到了 1 的情況，也就是 Entry 數組存滿了才發生擴容，這樣會出現大量的哈希衝突的情況，出現鏈表過長，影響 get 查詢數據的效率
- 因此選擇了 0.5~1 的折中數也就是 0.75，均衡解決了上面出現的情況
三、HashMap 的基本操作#
get 操作#
/**
* 透過 hash(key) 方法計算 key 的哈希值
* 透過 getNode() 方法獲取 node
* 如果 node 為 null, 返回null, 否則返回 node.value
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* getNode 可以分為以下幾步:
* 1. 如果哈希表為空，或 key 對應的桶為空，返回 null
* 2. 不為空的話，如果桶中第一個節點就和指定參數hash和key匹配上了，直接返回這個節點
* 3. 第一個節點沒匹配上的話進行後續查找:
* 3.1、如果當前的桶採用紅黑樹，調用紅黑樹的 getTreeNode 去獲取節點值
* 3.2、 如果為鏈表結構，直接遍歷鏈表查詢查找
* 4. 找到節點返回 value, 否則返回 null
*/
final Node<K,V> getNode(int hash, Object key) {
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) {
// 優化點 1: 減少不必要的查詢
// 如果桶中第一個節點就和指定參數hash和key匹配上了，直接返回這個節點
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 第一個節點沒匹配上的話進行後續查找
if ((e = first.next) != null) {
// 如果當前的桶採用紅黑樹，調用紅黑樹的 getTreeNode 去獲取節點值
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;
}
put 操作#
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* putVal方法可以分為以下幾個步驟
* 1. 如果哈希表為空，調用 resize 方法創建
* 2. 如果指定 key 值不衝突，即不存在哈希衝突的情況直接插入鍵值對
* 3. 如果有衝突，找到這個衝突節點
* 3.1 如果第一個節點就匹配了，記錄起來否則繼續查找下去
* 3.2 如果當前為紅黑樹結構，調用 putTreeVal 方法插入
* 3.3 如果為鏈表結構，循環遍歷鏈表查找, 找到最後還沒有的話利用尾插法插入節點，找到了的話記錄這個節點，然後退出循環
* 4. 找到了衝突節點的話，判斷 onlyIfAbsent是否為 true, 即代表是否允許修改舊值
* 5. HashMap修改次數modCount 和 容量大小size 自增運算 + 1, 如果 size > threshold, 即達到了 臨界值，進行擴容
*
* @param hash 指定 key 的 hash 值
* @param key 指定 key
* @param value 需要插入的 value 值
* @param e, 表示不允許替換舊值
* @param evict 代表 HashMap 是否處於創建模式
* @return 指定 key 存在的情況下，如果替換了舊值，返回這個值，否則返回 null，當然也有可能 value 值就是 null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果哈希表為空，調用 resize 方法創建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果指定 key 值不衝突，即不存在哈希衝突的情況直接插入鍵值對
// (n - 1) & hash 等價於 hash % n，不過位運算更快
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 = p;
// 如果當前為紅黑樹結構，調用 putTreeVal 方法插入
else if (p instanceof TreeNode)
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);
// 檢查鏈表長度是否達到臨界值，達到的話轉變成紅黑樹結構
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 找到了的話記錄這個節點，然後退出循環
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 記錄值不為空，代表找到了衝突節點
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 判斷 onlyIfAbsent是否為 true, 即代表是否允許修改舊值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 判斷 size 是否達到了臨界值需要進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
擴容操作#
/**
* 對 table 進行初始化或者擴容，擴容的話每次都是容量翻倍，二進制計算後，原來的節點要麼就在原來的位置，要麼就被分配到 “原位置 + 舊容量” 這個位置
* resize 的步驟總結:
* 1. 計算擴容後的容量，臨界值
* 2. 更新HashMap的臨界值
* 3. 根據計算得出的擴容容量，創建新數組，然後將 HashMap 的 table 引用指向新數組
* 4. 將舊數組的元素複製到 table 中
*/
final Node<K,V>[] resize() {
// 新建一個 oldtab 數組保存擴容前的數組 table
Node<K,V>[] oldTab = table;
// 獲取舊數組的長度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 舊數組的臨界值
int oldThr = threshold;
int newCap, newThr = 0;
// 如果舊數組容量大於0
if (oldCap > 0) {
// 如果舊數組容量超過最大值, 將其臨界值設為整型最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果舊數組容量大於默認容量(16)且翻倍後得到的新數組容量小於最大值，將舊數組的臨界值也翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 如果舊容量 <= 0, 而且臨界值 > 0
else if (oldThr > 0) // initial capacity was placed in threshold
// 將新數組容量設為舊數組的臨界值
newCap = oldThr;
// 如果舊容量 <= 0, 而且臨界值 <= 0
else {
// 新容量設為默認值(16)
newCap = DEFAULT_INITIAL_CAPACITY;
// 新臨界值設為默認容量 * 默認負載因子 (16 * 0.75) = 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 在上面的條件判斷中，只有 oldThr > 0 時， newThr == 0
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;
if (oldTab != null) {
// 遍歷舊哈希表的每個節點進行數組拷貝
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 用 e 記錄下舊節點的值
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果舊 bucket 的存儲衝突 hash值的結構為 紅黑樹
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 如果舊 bucket 的存儲衝突 hash值的結構為 鏈表結構
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// java 7 是在 while 循環裡面，單個計算好數組索引位置後，單個的插入數組中，在多線程情況下，會有成環問題
// java 8 是等鏈表整個 while 循環結束後，才給數組賦值，所以多線程情況下，也不會成環
do {
next = e.next;
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;
newTab[j] = loHead;
}
// 節點被分配到 “原位置 + 舊容量” 這個位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
四、Java 中 HashMap 的 key 值要是為類對象則該類需要滿足什麼條件#
一般使用 String、Integer 這樣的包裝類作為 key 鍵，原因是:
- 這種包裝類型為 final 類型，具有不可更改性，因此保證了 hash 值的不可更改性和計算準確性
- 內部重寫了 equals (), hashcode () 方法
因此若 HashMap 中的 key 為類對象的話，需要重寫 hashcode 和 equals () 方法
五、HashMap 是怎麼解決哈希衝突的？#
解決哈希衝突的方法#
開放定址法#
從發生衝突的那個單元起，按照一定的次序，從哈希表中找到一個空閒的單元。然後把發生衝突的元素存入到該單元的一種方法，需要的表長度要大於等於所需要存放的元素
包括以下幾種方法
- 線性探查法
從發生衝突的單元起，依次判斷下一個單元是否為空，當達到最後一個單元時，再從表首依次判斷。直到碰到空閒的單元或者探查完全部單元為止 - 平方探查法
發生衝突時，用發生衝突的單元 d [i], 加上 1²、 2² 等。即 d [i] + 1²，d [i] + 2², d [i] + 3²... 直到找到空閒單元 - 雙散列函數探查法
鏈地址法 (拉鏈法)#
鏈接地址法的思路是將哈希值相同的元素構成一個同義詞的單鏈表，並將單鏈表的頭指針存放在哈希表的第 i 個單元中，查找、插入和刪除主要在同義詞鏈表中進行
再哈希法#
就是同時構造多個不同的哈希函數：
Hi = RHi(key) i= 1,2,3 ... k;
當 H1 = RH1 (key) 發生衝突時，再用 H2 = RH2 (key) 進行計算，直到衝突不再產生，這種方法不易產生聚集，但是增加了計算時間
六、HashMap 在 JDK1.7 和 JDK1.8 中有哪些不同#
-
1.8 加入了 紅黑樹，遍歷查詢時間複雜度由原來鏈表的 O (n) 變為 O (logn)
-
在插入數據的時候，1.7 基於頭插法，這會產生逆序且環形鏈表死循環問題，而 1.8 基於尾插法避免了這個問題，詳見: jdk1.7HashMap 鏈表成環的原因和 jdk1.8 的解決方案
-
擴容後數據存儲位置的計算方式不一樣
- JDK 1.7 使用 hashCode () + 4 次位運算 + 5 次異或運算（9 次擾動）
static final int hash(int h) {
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}```2. JDK 1.8 簡化了擾動函數，只做了 2 次擾動 = 1 次位運算 + 1 次異或運算
Java static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // a. 當key = null時，hash值 = 0，所以HashMap的key 可為null // 注：對比HashTable，HashTable對key直接hashCode（），若key為null時，會拋出異常，所以HashTable的key不可為null // b. 當key ≠ null時，則透過先計算出 key的 hashCode()（記為h），然後 對哈希碼進行 擾動處理： 按位 異或（^） 哈希碼自身右移16位後的二進制 }
七、HashMap 為什麼不直接使用 hashCode () 處理後的哈希值直接作為 table 的下標？#
不直接使用 hashCode (), 而選擇擾動函數處理, 使得根據 key 生成的哈希碼（hash 值）分佈更加均勻、更具備隨機性，避免出現 hash 值衝突
八、HashMap、LinkHashMap 和 TreeMap 的差別#
- 遍歷 HashMap 時，其輸出是無序的
- LinkedHashMap 繼承自 HashMap，具有高效性，同時在 HashMap 的基礎上，又在內部增加了一個鏈表，用以存放元素的順序
- TreeMap 實現了 SortedMap 接口，它可以對元素進行排序
- LinkedHashMap 是基於元素進入集合的順序或者被訪問的先後順序排序，TreeMap 則是基於元素的固有順序 (由 Comparator 或者 Comparable 確定)