HashMap解密：揭秘高效存儲(chǔ)與快速檢索的魔法

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)鏈表的長(zhǎng)度超過8個(gè)節(jié)點(diǎn)，并且數(shù)組的長(zhǎng)度大于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í)行以下步驟：

1. 根據(jù)鍵的?hashCode()?方法計(jì)算哈希碼。
2. 根據(jù)哈希碼找到數(shù)組索引位置。
3. 如果該索引位置為空，直接插入元素。
4. 如果該索引位置不為空，檢查鍵是否已存在，如果存在則更新值，否則將元素插入鏈表或紅黑樹。
5. 如果鏈表長(zhǎng)度過長(zhǎng)，并且數(shù)組長(zhǎng)度足夠大，將鏈表轉(zhuǎn)換為紅黑樹。
6. 根據(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在各種場(chǎng)景下都能夠提供高效的數(shù)據(jù)存儲(chǔ)和檢索能力。