Warning:這是《Java 程式員進階之路》專欄的第 55 篇。那天,小二去蔚來面試,面試官老王一上來就問他:HashMap 的 hash 方法的原理是什麼?當時就把裸面的小二給蚌埠住了。
回來後小二找到了我,于是我就寫下了這篇文章丢給他,并嚴厲地告訴他:再搞不懂就别來找我。聽到這句話,心頭一陣酸,小二繃不住差點要哭 😭。
PS:本文 GitHub 上已同步,有 GitHub 賬号的小夥伴,記得看完後給二哥安排一波 star 呀!沖一波 GitHub 的 trending 榜單,求求各位了。
GitHub 位址:
https://github.com/itwanger/toBeBetterJavaer 來看一下 hash 方法的源碼(JDK 8 中的 HashMap):static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這段代碼究竟是用來幹嘛的呢?
我們都知道,key.hashCode() 是用來擷取鍵位的哈希值的,理論上,哈希值是一個 int 類型,範圍從-2147483648 到 2147483648。前後加起來大概 40 億的映射空間,隻要哈希值映射得比較均勻松散,一般是不會出現哈希碰撞的。
但問題是一個 40 億長度的數組,記憶體是放不下的。HashMap 擴容之前的數組初始大小隻有 16,是以這個哈希值是不能直接拿來用的,用之前要和數組的長度做取模運算,用得到的餘數來通路數組下标才行。
取模運算有兩處。
取模運算(“Modulo Operation”)和取餘運算(“Remainder Operation ”)兩個概念有重疊的部分但又不完全一緻。主要的差別在于對負整數進行除法運算時操作不同。取模主要是用于計算機術語中,取餘則更多是數學概念。
一處是往 HashMap 中 put 的時候(putVal 方法中):
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
}
一處是從 HashMap 中 get 的時候(getNode 方法中):
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {}
}
其中的 (n - 1) & hash 正是取模運算,就是把哈希值和(數組長度-1)做了一個“與”運算。
可能大家在疑惑:取模運算難道不該用 % 嗎?為什麼要用 & 呢?
這是因為 & 運算比 % 更加高效,并且當 b 為 2 的 n 次方時,存在下面這樣一個公式。
a % b = a & (b-1)
用 2 n 2^n 2
n
替換下 b 就是:
a % 2 n 2^n 2
= a & ( 2 n 2^n 2
-1)
我們來驗證一下,假如 a = 14,b = 8,也就是 2 3 2^3 2
3
,n=3。
14%8,14 的二進制為 1110,8 的二進制 1000,8-1 = 7 的二進制為 0111,1110&0111=0110,也就是 0* 2 0 2^0 2
+1* 2 1 2^1 2
1
+1* 2 2 2^2 2
2
+0* 2 3 2^3 2
=0+2+4+0=6,14%8 剛好也等于 6。
這也正好解釋了為什麼 HashMap 的數組長度要取 2 的整次方。
因為(數組長度-1)正好相當于一個“低位掩碼”——這個掩碼的低位最好全是 1,這樣 & 操作才有意義,否則結果就肯定是 0,那麼 & 操作就沒有意義了。
a&b 操作的結果是:a、b 中對應位同時為 1,則對應結果位為 1,否則為 0
2 的整次幂剛好是偶數,偶數-1 是奇數,奇數的二進制最後一位是 1,保證了 hash &(length-1) 的最後一位可能為 0,也可能為 1(這取決于 h 的值),即 & 運算後的結果可能為偶數,也可能為奇數,這樣便可以保證哈希值的均勻性。
& 操作的結果就是将哈希值的高位全部歸零,隻保留低位值,用來做數組下标通路。
假設某哈希值為 10100101 11000100 00100101,用它來做取模運算,我們來看一下結果。HashMap 的初始長度為 16(内部是數組),16-1=15,二進制是 00000000 00000000 00001111(高位用 0 來補齊):
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101
因為 15 的高位全部是 0,是以 & 運算後的高位結果肯定是 0,隻剩下 4 個低位 0101,也就是十進制的 5,也就是将哈希值為 10100101 11000100 00100101 的鍵放在數組的第 5 位。
明白了取模運算後,我們再來看 put 方法的源碼:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
以及 get 方法的源碼:
public V get(Object key) {
HashMap.Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
它們在調用 putVal 和 getNode 之前,都會先調用 hash 方法:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
那為什麼取模運算之前要調用 hash 方法呢?
看下面這個圖。
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5iNhRWY5QjYyITO0cTZzYjYiBTO0gjM2QmYmdjYjFWOk9CX5d2bs92Yl1iclB3bsVmdlR2LcNWaw9CXt92Yu4GZjlGbh5yYjV3Lc9CX6MHc0RHaiojIsJye.png)
某哈希值為 11111111 11111111 11110000 1110 1010,将它右移 16 位(h >>> 16),剛好是 00000000 00000000 11111111 11111111,再進行異或操作(h ^ (h >>> 16)),結果是 11111111 11111111 00001111 00010101
異或(^)運算是基于二進制的位運算,采用符号 XOR 或者^來表示,運算規則是:如果是同值取 0、異值取 1
由于混合了原來哈希值的高位和低位,是以低位的随機性加大了(摻雜了部分高位的特征,高位的資訊也得到了保留)。
結果再與數組長度-1(00000000 00000000 00000000 00001111)做取模運算,得到的下标就是 00000000 00000000 00000000 00000101,也就是 5。
還記得之前我們假設的某哈希值 10100101 11000100 00100101 嗎?在沒有調用 hash 方法之前,與 15 做取模運算後的結果也是 5,我們不妨來看看調用 hash 之後的取模運算結果是多少。
某哈希值 00000000 10100101 11000100 00100101(補齊 32 位),将它右移 16 位(h >>> 16),剛好是 00000000 00000000 00000000 10100101,再進行異或操作(h ^ (h >>> 16)),結果是 00000000 10100101 00111011 10000000
結果再與數組長度-1(00000000 00000000 00000000 00001111)做取模運算,得到的下标就是 00000000 00000000 00000000 00000000,也就是 0。
綜上所述,hash 方法是用來做哈希值優化的,把哈希值右移 16 位,也就正好是自己長度的一半,之後與原哈希值做異或運算,這樣就混合了原哈希值中的高位和低位,增大了随機性。
說白了,hash 方法就是為了增加随機性,讓資料元素更加均衡的分布,減少碰撞。