HashMap是Java中廣泛使用的數(shù)據(jù)結(jié)構(gòu)之一，它提供了高效的鍵值對(duì)存儲(chǔ)和檢索功能。本文將深入探討HashMap的底層原理，包括它的數(shù)據(jù)結(jié)構(gòu)、哈希算法、碰撞解決方法以及工作原理。
數(shù)據(jù)結(jié)構(gòu)
HashMap的底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表（或紅黑樹）。數(shù)組用于存儲(chǔ)元素的桶（bucket），每個(gè)桶是一個(gè)鏈表或紅黑樹的頭節(jié)點(diǎn)。當(dāng)出現(xiàn)大量元素存儲(chǔ)在同一個(gè)桶內(nèi)時(shí)，鏈表將轉(zhuǎn)換為紅黑樹，以提高檢索效率。
哈希算法
HashMap使用哈希算法將鍵映射到數(shù)組索引位置。哈希算法的關(guān)鍵是?hashCode()?方法。當(dāng)調(diào)用?hashCode()?方法時(shí)，HashMap會(huì)根據(jù)鍵的特性生成一個(gè)哈希碼。哈希碼是一個(gè)整數(shù)，它代表了鍵在數(shù)組中的位置。
碰撞解決方法
在哈希算法中，不同的鍵可能會(huì)生成相同的哈希碼，這就是所謂的碰撞（collision）。HashMap使用鏈表和紅黑樹來解決碰撞問題。
當(dāng)元素被插入到HashMap中時(shí)，首先根據(jù)鍵的哈希碼計(jì)算出數(shù)組索引。如果該索引位置為空，則直接將元素插入其中。如果該索引位置已經(jīng)存在元素，則遍歷鏈表或紅黑樹，判斷鍵是否已經(jīng)存在。如果鍵已存在，則更新對(duì)應(yīng)的值；如果鍵不存在，則將新元素添加到鏈表或紅黑樹的末尾或合適位置。
當(dāng)鏈表的長度超過8個(gè)節(jié)點(diǎn)，并且數(shù)組的長度大于64時(shí)，鏈表將被轉(zhuǎn)換為紅黑樹。這是為了提高在大量元素存儲(chǔ)在同一個(gè)桶內(nèi)時(shí)的查找效率。
源碼
// 遍歷鏈表
for (int binCount = 0; ; ++binCount) {
// 遍歷到鏈表最后一個(gè)節(jié)點(diǎn)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果鏈表元素個(gè)數(shù)大于等于TREEIFY_THRESHOLD（8）
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 紅黑樹轉(zhuǎn)換（并不會(huì)直接轉(zhuǎn)換成紅黑樹）
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
工作原理
當(dāng)使用HashMap進(jìn)行插入、獲取或刪除操作時(shí)，它會(huì)執(zhí)行以下步驟：
- 根據(jù)鍵的?
hashCode()?方法計(jì)算哈希碼。 - 根據(jù)哈希碼找到數(shù)組索引位置。
- 如果該索引位置為空，直接插入元素。
- 如果該索引位置不為空，檢查鍵是否已存在，如果存在則更新值，否則將元素插入鏈表或紅黑樹。
- 如果鏈表長度過長，并且數(shù)組長度足夠大，將鏈表轉(zhuǎn)換為紅黑樹。
- 根據(jù)需要調(diào)整數(shù)組的大?。〝U(kuò)容或收縮）以保持較低的負(fù)載因子。
總結(jié)
HashMap是一種高效的鍵值對(duì)存儲(chǔ)和檢索數(shù)據(jù)結(jié)構(gòu)。它的底層原理基于數(shù)組、鏈表和紅黑樹，使用哈希算法將鍵映射到數(shù)組索引位置。碰撞問題通過鏈表和紅黑樹的使用得以解決。了解HashMap的底層原理對(duì)于理解其運(yùn)作方式、優(yōu)化性能以及避免潛在的問題非常重要。通過合理選擇哈希函數(shù)和調(diào)整負(fù)載因子，我們可以確保HashMap在各種場景下都能夠提供高效的數(shù)據(jù)存儲(chǔ)和檢索能力。
