一文搞定 HashMap工作原理
點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號(hào)”
優(yōu)質(zhì)文章，第一時(shí)間送達(dá)
1 HashMap在JAVA中的怎么工作的？
基于Hash的原理
2 什么是哈希？
最簡單形式的 hash，是一種在對任何變量/對象的屬性應(yīng)用任何公式/算法后， 為其分配唯一代碼的方法。
一個(gè)真正的hash方法必須遵循下面的原則
哈希函數(shù)每次在相同或相等的對象上應(yīng)用哈希函數(shù)時(shí), 應(yīng)每次返回相同的哈希碼。換句話說, 兩個(gè)相等的對象必須一致地生成相同的哈希碼。
Java 中所有的對象都有 Hash 方法
Java中的所有對象都繼承 Object 類中定義的 hashCode() 函數(shù)的默認(rèn)實(shí)現(xiàn)。此函數(shù)通常通過將對象的內(nèi)部地址轉(zhuǎn)換為整數(shù)來生成哈希碼，從而為所有不同的對象生成不同的哈希碼。
3 HashMap 中的 Node 類
Map的定義是：將鍵映射到值的對象。
因此，HashMap 中必須有一些機(jī)制來存儲(chǔ)這個(gè)鍵值對。答案是肯定的。HHashMap 有一個(gè)內(nèi)部類 Node，如下所示：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;// 記錄hash值， 以便重hash時(shí)不需要再重新計(jì)算
final K key;
V value;
Node<K,V> next;
...// 其余的代碼
}
當(dāng)然，Node 類具有存儲(chǔ)為屬性的鍵和值的映射。key 已被標(biāo)記為 final，另外還有兩個(gè)字段：next 和 hash。
在下面中， 我們將會(huì)理解這些屬性的必須性。
4 鍵值對在 HashMap 中是如何存儲(chǔ)的
鍵值對在 HashMap 中是以 Node 內(nèi)部類的數(shù)組存放的， 如下所示：
transient Node<K,V>[] table;
哈希碼計(jì)算出來之后， 會(huì)轉(zhuǎn)換成該數(shù)組的下標(biāo)， 在該下標(biāo)中存儲(chǔ)對應(yīng)哈希碼的鍵值對， 在此先不詳細(xì)講解hash碰撞的情況。
該數(shù)組的長度始終是 2 的次冪， 通過以下的函數(shù)實(shí)現(xiàn)該過程
static final int tableSizeFor(int cap) {
int n = cap - 1;// 如果不做該操作， 則如傳入的 cap 是 2 的整數(shù)冪， 則返回值是預(yù)想的 2 倍
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
其原理是將傳入?yún)?shù) (cap) 的低二進(jìn)制全部變?yōu)?1， 最后加 1 即可獲得對應(yīng)的大于 cap 的 2 的次冪作為數(shù)組長度。
為什么要使用 2 的次冪作為數(shù)組的容量呢？
在此有涉及到 HashMap 的 hash 函數(shù)及數(shù)組下標(biāo)的計(jì)算， 鍵(key)所計(jì)算出來的哈希碼有可能是大于數(shù)組的容量的， 那怎么辦？可以通過簡單的求余運(yùn)算來獲得， 但此方法效率太低。HashMap 中通過以下的方法保證 hash 的值計(jì)算后都小于數(shù)組的容量。
(n - 1) & hash
這也正好解釋了為什么需要 2 的次冪作為數(shù)組的容量。由于 n 是 2 的次冪， 因此， n - 1 類似于一個(gè)低位掩碼。通過與操作， 高位的hash值全部歸零，保證低位才有效， 從而保證獲得的值都小于 n。同時(shí)， 在下一次 resize() 操作時(shí)， 重新計(jì)算每個(gè) Node 的數(shù)組下標(biāo)將會(huì)因此變得很簡單， 具體的后文講解。以默認(rèn)的初始值 16 為例
01010011 00100101 01010100 00100101
& 00000000 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000000 00000101 //高位全部歸零，只保留末四位
// 保證了計(jì)算出的值小于數(shù)組的長度 n
但是， 使用了該功能之后， 由于只取了低位， 因此 hash 碰撞會(huì)也會(huì)相應(yīng)的變得很嚴(yán)重。這時(shí)候就需要使用 「擾動(dòng)函數(shù)」
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
該函數(shù)通過將哈希碼的高 16 位的右移后與原哈希碼進(jìn)行異或而得到， 以以上的例子為例
此方法保證了高16位不變， 低16位根據(jù)異或后的結(jié)果改變。計(jì)算后的數(shù)組下標(biāo)將會(huì)從原先的 5 變?yōu)?0。
使用了 「擾動(dòng)函數(shù)」 之后， hash 碰撞的概率將會(huì)下降。有人專門做過類似的測試， 雖然使用該 「擾動(dòng)函數(shù)」 并沒有獲得最大概率的避免 hash 碰撞， 但考慮其計(jì)算性能和碰撞的概率， JDK 中使用了該方法， 且只 hash 一次。
5 哈希碰撞及其處理
在理想的情況下， 哈希函數(shù)將每一個(gè) key 都映射到一個(gè)唯一的 bucket， 然而， 這是不可能的。哪怕是設(shè)計(jì)在良好的哈希函數(shù)， 也會(huì)產(chǎn)生哈希沖突。
前人研究了很多哈希沖突的解決方法， 在維基百科中， 總結(jié)出了四大類
在 Java 的 HashMap 中， 采用了第一種 Separate chaining 方法(大多數(shù)翻譯為拉鏈法)+鏈表和紅黑樹來解決沖突。
在 HashMap 中， 哈希碰撞之后會(huì)通過 Node 類內(nèi)部的成員變量 Node<K,V> next; 來形成一個(gè)鏈表(節(jié)點(diǎn)小于8)或紅黑樹（節(jié)點(diǎn)大于8， 在小于6時(shí)會(huì)從新轉(zhuǎn)換為鏈表）， 從而達(dá)到解決沖突的目的。
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
6 HashMap 的初始化
public HashMap();
public HashMap(int initialCapacity);
public HashMap(Map<? extends K, ? extends V> m);
public HashMap(int initialCapacity, float loadFactor);
HashMap 中有四個(gè)構(gòu)造函數(shù)， 大多是初始化容量和負(fù)載因子的操作。以 public HashMap(int initialCapacity, float loadFactor) 為例
public HashMap(int initialCapacity, float loadFactor) {
// 初始化的容量不能小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 初始化容量不大于最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 負(fù)載因子不能小于 0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
通過該函數(shù)進(jìn)行了容量和負(fù)載因子的初始化，如果是調(diào)用的其他的構(gòu)造函數(shù)， 則相應(yīng)的負(fù)載因子和容量會(huì)使用默認(rèn)值（默認(rèn)負(fù)載因子=0.75， 默認(rèn)容量=16）。在此時(shí)， 還沒有進(jìn)行存儲(chǔ)容器 table 的初始化， 該初始化要延遲到第一次使用時(shí)進(jìn)行。
7 HashMap 中哈希表的初始化或動(dòng)態(tài)擴(kuò)容
所謂的哈希表， 指的就是下面這個(gè)類型為內(nèi)部類Node的 table 變量。
transient Node<K,V>[] table;
作為數(shù)組， 其在初始化時(shí)就需要指定長度。在實(shí)際使用過程中， 我們存儲(chǔ)的數(shù)量可能會(huì)大于該長度，因此 HashMap 中定義了一個(gè)閾值參數(shù)(threshold)， 在存儲(chǔ)的容量達(dá)到指定的閾值時(shí)， 需要進(jìn)行擴(kuò)容。
我個(gè)人認(rèn)為初始化也是動(dòng)態(tài)擴(kuò)容的一種， 只不過其擴(kuò)容是容量從 0 擴(kuò)展到構(gòu)造函數(shù)中的數(shù)值（默認(rèn)16）。而且不需要進(jìn)行元素的重hash.
7.1 擴(kuò)容發(fā)生的條件
初始化的話只要數(shù)值為空或者數(shù)組長度為 0 就會(huì)進(jìn)行。而擴(kuò)容是在元素的數(shù)量大于閾值（threshold）時(shí)就會(huì)觸發(fā)。
threshold = loadFactor * capacity
比如 HashMap 中默認(rèn)的 loadFactor=0.75, capacity=16, 則
threshold = loadFactor * capacity = 0.75 * 16 = 12
那么在元素?cái)?shù)量大于 12 時(shí)， 就會(huì)進(jìn)行擴(kuò)容。擴(kuò)容后的 capacity 和 threshold 也會(huì)隨之而改變。
負(fù)載因子影響觸發(fā)的閾值， 因此， 它的值較小的時(shí)候， HashMap 中的 hash 碰撞就很少， 此時(shí)存取的性能都很高， 對應(yīng)的缺點(diǎn)是需要較多的內(nèi)存；而它的值較大時(shí)， HashMap 中的 hash 碰撞就很多， 此時(shí)存取的性能相對較低， 對應(yīng)優(yōu)點(diǎn)是需要較少的內(nèi)存；不建議更改該默認(rèn)值， 如果要更改， 建議進(jìn)行相應(yīng)的測試之后確定。
7.2 再談容量為2的整數(shù)次冪和數(shù)組索引計(jì)算
前面說過了數(shù)組的容量為 2 的整次冪， 同時(shí)， 數(shù)組的下標(biāo)通過下面的代碼進(jìn)行計(jì)算
index = (table.length - 1) & hash
該方法除了可以很快的計(jì)算出數(shù)組的索引之外， 在擴(kuò)容之后， 進(jìn)行重 hash 時(shí)也會(huì)很巧妙的就可以算出新的 hash 值。由于數(shù)組擴(kuò)容之后， 容量是現(xiàn)在的 2 倍， 擴(kuò)容之后 n-1 的有效位會(huì)比原來多一位， 而多的這一位與原容量二進(jìn)制在同一個(gè)位置。示例
這樣就可以很快的計(jì)算出新的索引啦
7.3 步驟
先判斷是初始化還是擴(kuò)容， 兩者在計(jì)算 newCap和newThr 時(shí)會(huì)不一樣
計(jì)算擴(kuò)容后的容量，臨界值。
將hashMap的臨界值修改為擴(kuò)容后的臨界值
根據(jù)擴(kuò)容后的容量新建數(shù)組，然后將hashMap的table的引用指向新數(shù)組。
將舊數(shù)組的元素復(fù)制到table中。在該過程中， 涉及到幾種情況， 需要分開進(jìn)行處理（只存有一個(gè)元素， 一般鏈表， 紅黑樹）
具體的看代碼吧
final Node<K, V>[] resize() {
//新建oldTab數(shù)組保存擴(kuò)容前的數(shù)組table
Node<K, V>[] oldTab = table;
//獲取原來數(shù)組的長度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//原來數(shù)組擴(kuò)容的臨界值
int oldThr = threshold;
int newCap, newThr = 0;
//如果擴(kuò)容前的容量 > 0
if (oldCap > 0) {
//如果原來的數(shù)組長度大于最大值(2^30)
if (oldCap >= MAXIMUM_CAPACITY) {
//擴(kuò)容臨界值提高到正無窮
threshold = Integer.MAX_VALUE;
//無法進(jìn)行擴(kuò)容，返回原來的數(shù)組
return oldTab;
//如果現(xiàn)在容量的兩倍小于MAXIMUM_CAPACITY且現(xiàn)在的容量大于DEFAULT_INITIAL_CAPACITY
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//臨界值變?yōu)樵瓉淼?倍
newThr = oldThr << 1;
} else if (oldThr > 0) //如果舊容量 <= 0，而且舊臨界值 > 0
//數(shù)組的新容量設(shè)置為老數(shù)組擴(kuò)容的臨界值
newCap = oldThr;
else { //如果舊容量 <= 0，且舊臨界值 <= 0，新容量擴(kuò)充為默認(rèn)初始化容量，新臨界值為DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY
newCap = DEFAULT_INITIAL_CAPACITY;//新數(shù)組初始容量設(shè)置為默認(rèn)值
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//計(jì)算默認(rèn)容量下的閾值
}
// 計(jì)算新的resize上限
if (newThr == 0) {//在當(dāng)上面的條件判斷中，只有是初始化時(shí)(oldCap=0, oldThr > 0)時(shí)，newThr == 0
//ft為臨時(shí)臨界值，下面會(huì)確定這個(gè)臨界值是否合法，如果合法，那就是真正的臨界值
float ft = (float) newCap * loadFactor;
//當(dāng)新容量< MAXIMUM_CAPACITY且ft < (float)MAXIMUM_CAPACITY，新的臨界值為ft，否則為Integer.MAX_VALUE
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
//將擴(kuò)容后hashMap的臨界值設(shè)置為newThr
threshold = newThr;
//創(chuàng)建新的table，初始化容量為newCap
@SuppressWarnings({"rawtypes", "unchecked"})
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
//修改hashMap的table為新建的newTab
table = newTab;
//如果舊table不為空，將舊table中的元素復(fù)制到新的table中
if (oldTab != null) {
//遍歷舊哈希表的每個(gè)桶，將舊哈希表中的桶復(fù)制到新的哈希表中
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
//如果舊桶不為null，使用e記錄舊桶
if ((e = oldTab[j]) != null) {
//將舊桶置為null
oldTab[j] = null;
//如果舊桶中只有一個(gè)node
if (e.next == null)
//將e也就是oldTab[j]放入newTab中e.hash & (newCap - 1)的位置
newTab[e.hash & (newCap - 1)] = e;
//如果舊桶中的結(jié)構(gòu)為紅黑樹
else if (e instanceof TreeNode)
//將樹中的node分離
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else { //如果舊桶中的結(jié)構(gòu)為鏈表,鏈表重排，jdk1.8做的一系列優(yōu)化
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
//遍歷整個(gè)鏈表中的節(jié)點(diǎn)
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {// 原索引+oldCap
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
7.4 注意事項(xiàng)
雖然 HashMap 設(shè)計(jì)的非常優(yōu)秀， 但是應(yīng)該盡可能少的避免 resize(), 該過程會(huì)很耗費(fèi)時(shí)間。
同時(shí)， 由于 hashmap 不能自動(dòng)的縮小容量。因此， 如果你的 hashmap 容量很大， 但執(zhí)行了很多 remove 操作時(shí)， 容量并不會(huì)減少。如果你覺得需要減少容量， 請重新創(chuàng)建一個(gè) hashmap。
8 HashMap.put() 函數(shù)內(nèi)部是如何工作的？
在使用多次 HashMap 之后， 大體也能說出其添加元素的原理：計(jì)算每一個(gè)key的哈希值， 通過一定的計(jì)算之后算出其在哈希表中的位置，將鍵值對放入該位置，如果有哈希碰撞則進(jìn)行哈希碰撞處理。
而其工作時(shí)的原理如下（圖是我很早之前保存的， 忘了出處了）
源碼如下：
/* @param hash 指定參數(shù)key的哈希值
* @param key 指定參數(shù)key
* @param value 指定參數(shù)value
* @param onlyIfAbsent 如果為true，即使指定參數(shù)key在map中已經(jīng)存在，也不會(huì)替換value
* @param evict 如果為false，數(shù)組table在創(chuàng)建模式中
* @return 如果value被替換，則返回舊的value，否則返回null。當(dāng)然，可能key對應(yīng)的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;
//如果哈希表為空，調(diào)用resize()創(chuàng)建一個(gè)哈希表，并用變量n記錄哈希表長度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
* 如果指定參數(shù)hash在表中沒有對應(yīng)的桶，即為沒有碰撞
* Hash函數(shù)，(n - 1) & hash 計(jì)算key將被放置的槽位
* (n - 1) & hash 本質(zhì)上是hash % n，位運(yùn)算更快
*/
if ((p = tab[i = (n - 1) & hash]) == null)
//直接將鍵值對插入到map中即可
tab[i] = newNode(hash, key, value, null);
else {// 桶中已經(jīng)存在元素
Node<K, V> e;
K k;
// 比較桶中第一個(gè)元素(數(shù)組中的結(jié)點(diǎn))的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 將第一個(gè)元素賦值給e，用e來記錄
e = p;
// 當(dāng)前桶中無該鍵值對，且桶是紅黑樹結(jié)構(gòu)，按照紅黑樹結(jié)構(gòu)插入
else if (p instanceof TreeNode)
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
// 當(dāng)前桶中無該鍵值對，且桶是鏈表結(jié)構(gòu)，按照鏈表結(jié)構(gòu)插入到尾部
else {
for (int binCount = 0; ; ++binCount) {
// 遍歷到鏈表尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 檢查鏈表長度是否達(dá)到閾值，達(dá)到將該槽位節(jié)點(diǎn)組織形式轉(zhuǎn)為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 鏈表節(jié)點(diǎn)的<key, value>與put操作<key, value>相同時(shí)，不做重復(fù)操作，跳出循環(huán)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 找到或新建一個(gè)key和hashCode與插入元素相等的鍵值對，進(jìn)行put操作
if (e != null) { // existing mapping for key
// 記錄e的value
V oldValue = e.value;
/**
* onlyIfAbsent為false或舊值為null時(shí)，允許替換舊值
* 否則無需替換
*/
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 訪問后回調(diào)
afterNodeAccess(e);
// 返回舊值
return oldValue;
}
}
// 更新結(jié)構(gòu)化修改信息
++modCount;
// 鍵值對數(shù)目超過閾值時(shí)，進(jìn)行rehash
if (++size > threshold)
resize();
// 插入后回調(diào)
afterNodeInsertion(evict);
return null;
}
在此過程中， 會(huì)涉及到哈希碰撞的解決。
9 HashMap.get() 方法內(nèi)部是如何工作的？
/**
* 返回指定的key映射的value，如果value為null，則返回null
* get可以分為三個(gè)步驟：
* 1.通過hash(Object key)方法計(jì)算key的哈希值hash。
* 2.通過getNode( int hash, Object key)方法獲取node。
* 3.如果node為null，返回null，否則返回node.value。
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K, V> e;
//根據(jù)key及其hash值查詢node節(jié)點(diǎn)，如果存在，則返回該節(jié)點(diǎn)的value值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
其最終是調(diào)用了 getNode 函數(shù)。其邏輯如下
源碼如下：
/**
* @param hash 指定參數(shù)key的哈希值
* @param key 指定參數(shù)key
* @return 返回node，如果沒有則返回null
*/
final Node<K, V> getNode(int hash, Object key) {
Node<K, V>[] tab;
Node<K, V> first, e;
int n;
K k;
//如果哈希表不為空，而且key對應(yīng)的桶上不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果桶中的第一個(gè)節(jié)點(diǎn)就和指定參數(shù)hash和key匹配上了
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
//返回桶中的第一個(gè)節(jié)點(diǎn)
return first;
//如果桶中的第一個(gè)節(jié)點(diǎn)沒有匹配上，而且有后續(xù)節(jié)點(diǎn)
if ((e = first.next) != null) {
//如果當(dāng)前的桶采用紅黑樹，則調(diào)用紅黑樹的get方法去獲取節(jié)點(diǎn)
if (first instanceof TreeNode)
return ((TreeNode<K, V>) first).getTreeNode(hash, key);
//如果當(dāng)前的桶不采用紅黑樹，即桶中節(jié)點(diǎn)結(jié)構(gòu)為鏈?zhǔn)浇Y(jié)構(gòu)
do {
//遍歷鏈表，直到key匹配
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//如果哈希表為空，或者沒有找到節(jié)點(diǎn)，返回null
return null;
}
作者 | 阿進(jìn)的寫字臺(tái)
來源 | https://www.cnblogs.com/homejim/p/10029796.html
