HashMap 在Java 中的底層實(shí)現(xiàn)是數(shù)組、鍊錶和紅黑樹(shù)的組合結(jié)構(gòu)。 1. 它通過(guò)key 的hash 值計(jì)算索引位置，使用擾動(dòng)處理減少哈希碰撞；2. 當(dāng)發(fā)生哈希衝突時(shí)，採(cǎi)用鍊錶存儲(chǔ)相同索引的元素；3. 鍊錶長(zhǎng)度超過(guò)閾值（默認(rèn)8）時(shí)轉(zhuǎn)換為紅黑樹(shù)以提升性能；4. 元素?cái)?shù)量超過(guò)容量乘以負(fù)載因子（默認(rèn)0.75）時(shí)觸發(fā)擴(kuò)容，將數(shù)組大小翻倍並重新分佈元素；5. 自定義key 時(shí)需重寫equals() 和hashCode() 方法以確保正確存取。

HashMap 在Java 中的底層實(shí)現(xiàn)主要依賴於數(shù)組和鍊錶（或紅黑樹(shù)）結(jié)構(gòu)。當(dāng)你把鍵值對(duì)放入HashMap 時(shí)，它會(huì)根據(jù)key 的hash 值決定該數(shù)據(jù)存儲(chǔ)的位置。如果不同key 計(jì)算出的索引相同，就會(huì)發(fā)生哈希衝突，這時(shí)候HashMap 會(huì)使用鍊錶或紅黑樹(shù)來(lái)處理這些衝突。

Hash 算法與索引計(jì)算

每個(gè)對(duì)像都有自己的hashCode()方法，HashMap 並不會(huì)直接使用這個(gè)值，而是對(duì)其進(jìn)行一次“擾動(dòng)”處理，也就是再哈希（rehash）。這樣做的目的是為了減少哈希碰撞的概率。

 static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

之後，HashMap 會(huì)用這個(gè)hash 值和數(shù)組長(zhǎng)度進(jìn)行按位與操作，得到一個(gè)索引值：

 index = (n - 1) & hash;

這裡n 是數(shù)組的長(zhǎng)度，必須是2 的冪次，這樣能保證分佈更均勻，減少碰撞。

處理哈希衝突：鍊錶與紅黑樹(shù)

當(dāng)多個(gè)不同的key 被映射到同一個(gè)數(shù)組位置時(shí)，它們會(huì)被組織成一個(gè)鍊錶。但鍊錶過(guò)長(zhǎng)會(huì)影響查找效率，因此在鍊錶長(zhǎng)度超過(guò)一定閾值（默認(rèn)是8）後，鍊錶會(huì)被轉(zhuǎn)換為紅黑樹(shù)，以提高查找、插入和刪除的性能。

• 當(dāng)節(jié)點(diǎn)數(shù)小於6 時(shí)，紅黑樹(shù)又會(huì)退化回鍊錶
• 這個(gè)設(shè)計(jì)是為了平衡查找效率和空間開(kāi)銷

所以你可以理解為：HashMap = 數(shù)組鍊錶紅黑樹(shù)

擴(kuò)容機(jī)制：resize()

當(dāng)HashMap 中的元素?cái)?shù)量超過(guò)容量乘以負(fù)載因子（默認(rèn)是0.75）時(shí)，HashMap 會(huì)進(jìn)行擴(kuò)容。擴(kuò)容過(guò)程包括：

• 創(chuàng)建一個(gè)新的數(shù)組，大小是原來(lái)的兩倍
• 把舊數(shù)組中的所有元素重新計(jì)算hash 和index，複製到新數(shù)組中

這個(gè)過(guò)程是比較耗時(shí)的，所以在初始化HashMap 時(shí)，如果能預(yù)估數(shù)據(jù)量，最好指定初始容量，避免頻繁擴(kuò)容。

關(guān)於key 的要求

HashMap 允許key 為null，這種key 會(huì)被放在數(shù)組的第一個(gè)位置。但如果你自定義了key 的類型，比如一個(gè)類，那麼一定要注意重寫equals()和hashCode()方法，否則可能導(dǎo)致無(wú)法正確獲取值或者內(nèi)存洩漏。

例如：

 class Person {
    String name;

    @Override
    public int hashCode() {
        return name.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof Person)) return false;
        return this.name.equals(((Person) obj).name);
    }
}

總結(jié)一下

HashMap 內(nèi)部其實(shí)就是一個(gè)動(dòng)態(tài)數(shù)組，加上鍊表或紅黑樹(shù)的組合結(jié)構(gòu)。它的高效來(lái)自於良好的哈希算法、合理的衝突處理策略以及自動(dòng)擴(kuò)容機(jī)制。理解這些原理有助於寫出更高效的代碼，也能幫助你在面試或調(diào)試中更好地應(yīng)對(duì)相關(guān)問(wèn)題。

基本上就這些。

以上是Hashmap在Java內(nèi)部如何工作？的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！