快捷導航

HashMap確定key的存儲位置的源碼分析

更新時間：2023年07月24日 10:42:48 作者：單程車票

HashMap 作為 Java 中最常用的數(shù)據(jù)結(jié)構(gòu)之一，用于存儲和管理鍵值對，HashMap 基于哈希函數(shù)實現(xiàn)，能通過將 key 映射到特定的位置來實現(xiàn)快速存儲、查找和刪除數(shù)據(jù)，接下來將從源碼角度分析以通俗易懂的方式向大家講解一下 HashMap 如何確定 key 的存儲位置的

前言

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

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

源碼分析

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

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

擾動函數(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) 這個式子可能有點不太好理解，我們分開來看：

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

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

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

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

補充 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 中對 hashCode() 方法計算出的哈希值進行了四次擾動，所以在性能上要差一點。在 JDK 1.8 對其優(yōu)化了擾動算法，使得計算的性能開銷降低許多。這里也是 JDK 1.7 和 1.8 在計算 key 的存儲位置上不同的地方了。

取模操作

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

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

可以看到方法中通過 (n - 1) & hash 來確定最終 key 的存儲位置，其實 (n - 1) & hash 這個式子就是取模操作，把通過 hash() 方法計算后得到的 hash 和當前 HashMap 的數(shù)組長度 - 1 進行與運算，相當于 hash % n，從而將其映射到數(shù)組特定的索引中。那么為什么 (n - 1) & hash 等價于 hash % n 呢？

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

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

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

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