前言

HashMap 通過(guò)哈希函數(shù)確定 key 的存儲(chǔ)位置這一映射過(guò)程，可使得 HashMap 在常數(shù)時(shí)間內(nèi)完成插入、查找和刪除操作，那么大家是否有了解過(guò) HashMap 底層是如何使用哈希函數(shù)實(shí)現(xiàn)映射的呢？是如何高效確認(rèn) key 的存儲(chǔ)位置的呢？

接下來(lái)將從源碼角度分析以通俗易懂的方式向大家講解一下 HashMap 如何確定 key 的存儲(chǔ)位置的。

源碼分析

下面以 JDK 1.8 版本查看 HashMap 中最為常用的方法之一 put(K key, V value) 方法來(lái)看看 key 是如何確定存儲(chǔ)位置的。

可以看到這里 key 會(huì)先通過(guò) hash() 方法進(jìn)行處理，進(jìn)入 hash() 方法一探究竟。

擾動(dòng)函數(shù) #hash()

JDK 1.8 中的 hash() 方法

源碼：

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

第一次看到 (h = key.hashCode()) ^ (h >>> 16) 這個(gè)式子可能有點(diǎn)不太好理解，我們分開來(lái)看：

• 可以看到式子中的 key.hashCode()，說(shuō)明 HashMap 會(huì)將傳入的 key 調(diào)用自身父類 Object 的 hashCode() 來(lái)進(jìn)行哈希計(jì)算。
• 然后將計(jì)算得到的哈希值 h 通過(guò) h ^ (h >>> 16) 把高 16 位異或（^）低 16 位形成新的哈希值（hashCode() 方法返回的是 int 類型，也就是 32 位的數(shù)據(jù)）。

以 (h = "key".hashCode() ^ (h >>> 16)) 為例：

將計(jì)算后的哈希值的高 16 位與低 16 位異或（^）的目的是為了通過(guò)把原本的低 16 位變成高 16 位和低 16 位的混合結(jié)果來(lái)使得低 16 位的隨機(jī)性增大，這樣在數(shù)組長(zhǎng)度較小時(shí)，能起到保證高 16 位也參與到 Hash 計(jì)算中（這個(gè)在后面的取模操作中很好的體現(xiàn)），同時(shí)不會(huì)造成太大的性能開銷。

JDK1.8 中 HashMap 的 hash() 方法也叫做擾動(dòng)函數(shù)，其目的就是為了增加隨機(jī)性，讓數(shù)據(jù)元素更加均衡的散列，減少碰撞。

補(bǔ)充 JDK 1.7 的 hash() 方法

static int hash(int h) {
    int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12); 
    return h ^ (h >>> 7) ^ (h >>> 4);
}

JDK 1.7 中對(duì) hashCode() 方法計(jì)算出的哈希值進(jìn)行了四次擾動(dòng)，所以在性能上要差一點(diǎn)。在 JDK 1.8 對(duì)其優(yōu)化了擾動(dòng)算法，使得計(jì)算的性能開銷降低許多。這里也是 JDK 1.7 和 1.8 在計(jì)算 key 的存儲(chǔ)位置上不同的地方了。

取模操作

在擾動(dòng)函數(shù) hash() 方法中可以看到返回的是一個(gè) int 類型的值，即值的范圍在 [-2147483648, 2147483647] 內(nèi)，也就是說(shuō)通過(guò) hash() 映射到的位置可以在近 40 億的長(zhǎng)度的數(shù)組中。

但是實(shí)際上的內(nèi)存不允許數(shù)組達(dá)到這么大，那么 HashMap 是如何將這個(gè)哈希值映射到數(shù)組中呢，相信讀者們的第一反應(yīng)一定是取模了，那么 HashMap 是怎樣進(jìn)行取模操作的呢，深入 putVal() 方法可以看到：

可以看到方法中通過(guò) (n - 1) & hash 來(lái)確定最終 key 的存儲(chǔ)位置，其實(shí) (n - 1) & hash 這個(gè)式子就是取模操作，把通過(guò) hash() 方法計(jì)算后得到的 hash 和當(dāng)前 HashMap 的數(shù)組長(zhǎng)度 - 1 進(jìn)行與運(yùn)算，相當(dāng)于 hash % n，從而將其映射到數(shù)組特定的索引中。那么為什么 (n - 1) & hash 等價(jià)于 hash % n 呢？

其實(shí)這個(gè)等價(jià)關(guān)系有一個(gè)必要的前提，這個(gè)前提就是 n 總是 2n2^n2n，即數(shù)組的長(zhǎng)度總是 2 的冪次方。當(dāng)數(shù)組長(zhǎng)度為 2 的冪次方時(shí)，可以保證 (n - 1) & hash 等價(jià)于 hash % n。

這是因?yàn)楫?dāng) n 為 2 的冪次方時(shí)，n - 1 可以保證高位為 0，低位全 1 的效果，所以，按位與運(yùn)算的結(jié)果相當(dāng)于保留了 hash 的二進(jìn)制表示的低位部分，而將高位部分全部置為 0，從而確保了 (n - 1) & hash 等價(jià)于 hash % n。

舉個(gè)例子：上圖可以知道 "key" 的哈希值計(jì)算結(jié)果為 0000 0000 0000 0001 1001 1110 0101 1110 即 106078，假設(shè)當(dāng)前數(shù)組長(zhǎng)度為 16 即 0001 0000，那么正常取模為 106078 % 16 = 14。

106078 & (16 - 1) 結(jié)果如圖：

至于為什么要使用位運(yùn)算呢？這是因?yàn)槿∧＿\(yùn)算的性能開銷較大，替換成位運(yùn)算可以得到更高的計(jì)算效率，提高性能。并且數(shù)組長(zhǎng)度為 2 的冪次方可以起到散列均勻分布，減少哈希碰撞的可能性。

總結(jié)

上面就是 HashMap 如何確定 key 的存儲(chǔ)位置的整個(gè)源碼分析過(guò)程了，過(guò)程可以分為三步：

• 將傳入的參數(shù) key 調(diào)用自身的方法 hashCode() 得到哈希值 h。
• 根據(jù)哈希值 h 調(diào)用擾動(dòng)函數(shù) hash() 計(jì)算 h ^ (h >>> 16) 得到擾動(dòng)后的哈希值 hash。
• 根據(jù)哈希值 hash 取模操作 hash & (n - 1) 從而確定 key 的存儲(chǔ)位置。

以上就是本篇文章的全部?jī)?nèi)容了。

到此這篇關(guān)于HashMap確定key的存儲(chǔ)位置的源碼分析的文章就介紹到這了,更多相關(guān)HashMap確定key位置內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論