Java面試題之HashMap 的 hash 方法原理是什么
Warning:這是《Java 程序員進階之路》專欄的第 55 篇。
回來后小二找到了我,于是我就寫下了這篇文章丟給他,并嚴厲地告訴他:再搞不懂就別來找我。聽到這句話,心頭一陣酸,小二繃不住差點要哭 😭。
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 億的映射空間,只要哈希值映射得比較均勻松散,一般是不會出現(xiàn)哈希碰撞的。
但問題是一個 40 億長度的數(shù)組,內(nèi)存是放不下的。HashMap 擴容之前的數(shù)組初始大小只有 16,所以這個哈希值是不能直接拿來用的,用之前要和數(shù)組的長度做取模運算,用得到的余數(shù)來訪問數(shù)組下標才行。
取模運算有兩處。
取模運算(“Modulo Operation”)和取余運算(“Remainder Operation ”)兩個概念有重疊的部分但又不完全一致。主要的區(qū)別在于對負整數(shù)進行除法運算時操作不同。取模主要是用于計算機術(shù)語中,取余則更多是數(shù)學(xué)概念。
一處是往 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
正是取模運算,就是把哈希值和(數(shù)組長度-1)做了一個“與”運算。
可能大家在疑惑:取模運算難道不該用 %
嗎?為什么要用 &
呢?
這是因為 &
運算比 %
更加高效,并且當 b 為 2 的 n 次方時,存在下面這樣一個公式。
a % b = a & (b-1)
用 2 n 2^n 2n 替換下 b 就是:
我們來驗證一下,假如 a = 14,b = 8,也就是 2 3 2^3 23,n=3。
14%8,14 的二進制為 1110,8 的二進制 1000,8-1 = 7 的二進制為 0111,1110&0111=0110,也就是 0*
2 0 2^0 20+1*
2 1 2^1 21+1*
2 2 2^2 22+0*
2 3 2^3 23=0+2+4+0=6,14%8 剛好也等于 6。
這也正好解釋了為什么 HashMap 的數(shù)組長度要取 2 的整次方。
因為(數(shù)組長度-1)正好相當于一個“低位掩碼”——這個掩碼的低位最好全是 1,這樣 & 操作才有意義,否則結(jié)果就肯定是 0,那么 & 操作就沒有意義了。
a&b 操作的結(jié)果是:a、b 中對應(yīng)位同時為 1,則對應(yīng)結(jié)果位為 1,否則為 0
2 的整次冪剛好是偶數(shù),偶數(shù)-1 是奇數(shù),奇數(shù)的二進制最后一位是 1,保證了 hash &(length-1) 的最后一位可能為 0,也可能為 1(這取決于 h 的值),即 & 運算后的結(jié)果可能為偶數(shù),也可能為奇數(shù),這樣便可以保證哈希值的均勻性。
& 操作的結(jié)果就是將哈希值的高位全部歸零,只保留低位值,用來做數(shù)組下標訪問。
假設(shè)某哈希值為 10100101 11000100 00100101
,用它來做取模運算,我們來看一下結(jié)果。HashMap 的初始長度為 16(內(nèi)部是數(shù)組),16-1=15,二進制是 00000000 00000000 00001111
(高位用 0 來補齊):
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101
因為 15 的高位全部是 0,所以 & 運算后的高位結(jié)果肯定是 0,只剩下 4 個低位 0101
,也就是十進制的 5,也就是將哈希值為 10100101 11000100 00100101
的鍵放在數(shù)組的第 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; }
它們在調(diào)用 putVal 和 getNode 之前,都會先調(diào)用 hash 方法:
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
那為什么取模運算之前要調(diào)用 hash 方法呢?
看下面這個圖。
某哈希值為 11111111 11111111 11110000 1110 1010
,將它右移 16 位(h >>> 16),剛好是 00000000 00000000 11111111 11111111
,再進行異或操作(h ^ (h >>> 16)),結(jié)果是 11111111 11111111 00001111 00010101
異或(^
)運算是基于二進制的位運算,采用符號 XOR 或者^
來表示,運算規(guī)則是:如果是同值取 0、異值取 1
由于混合了原來哈希值的高位和低位,所以低位的隨機性加大了(摻雜了部分高位的特征,高位的信息也得到了保留)。
結(jié)果再與數(shù)組長度-1(00000000 00000000 00000000 00001111
)做取模運算,得到的下標就是 00000000 00000000 00000000 00000101
,也就是 5。
還記得之前我們假設(shè)的某哈希值 10100101 11000100 00100101
嗎?在沒有調(diào)用 hash 方法之前,與 15 做取模運算后的結(jié)果也是 5,我們不妨來看看調(diào)用 hash 之后的取模運算結(jié)果是多少。
某哈希值 00000000 10100101 11000100 00100101
(補齊 32 位),將它右移 16 位(h >>> 16),剛好是 00000000 00000000 00000000 10100101
,再進行異或操作(h ^ (h >>> 16)),結(jié)果是 00000000 10100101 00111011 10000000
結(jié)果再與數(shù)組長度-1(00000000 00000000 00000000 00001111
)做取模運算,得到的下標就是 00000000 00000000 00000000 00000000
,也就是 0。
綜上所述,hash 方法是用來做哈希值優(yōu)化的,把哈希值右移 16 位,也就正好是自己長度的一半,之后與原哈希值做異或運算,這樣就混合了原哈希值中的高位和低位,增大了隨機性。
說白了,hash 方法就是為了增加隨機性,讓數(shù)據(jù)元素更加均衡的分布,減少碰撞。
到此這篇關(guān)于Java面試題之HashMap 的 hash 方法原理是什么的文章就介紹到這了,更多相關(guān)Java HashMap內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java并發(fā) synchronized鎖住的內(nèi)容解析
這篇文章主要介紹了Java并發(fā) synchronized鎖住的內(nèi)容解析,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-09-09Springboot整合SpringSecurity實現(xiàn)登錄認證和鑒權(quán)全過程
這篇文章主要介紹了Springboot整合SpringSecurity實現(xiàn)登錄認證和鑒權(quán)全過程,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-12-12java通過URLClassLoader類加載器加載外部jar代碼示例
ClassLoader翻譯過來就是類加載器,普通的java開發(fā)者其實用到的不多,但對于某些框架開發(fā)者來說卻非常常見,下面這篇文章主要給大家介紹了關(guān)于java通過URLClassLoader類加載器加載外部jar的相關(guān)資料,需要的朋友可以參考下2024-01-01SpringBoot中AOP的動態(tài)匹配和靜態(tài)匹配詳解
這篇文章主要介紹了SpringBoot中AOP的動態(tài)匹配和靜態(tài)匹配詳解,在創(chuàng)建代理的時候?qū)δ繕祟惖拿總€連接點使用靜態(tài)切點檢查,如果僅通過靜態(tài)切點檢查就可以知道連接點是不匹配的,則在運行時就不再進行動態(tài)檢查了,需要的朋友可以參考下2023-09-09詳解Java8的forEach(...)如何提供index值
這篇文章主要介紹了詳解Java8的forEach(...)如何提供index值,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03Java Socket一對多通信實現(xiàn)之并發(fā)處理方式
這篇文章主要介紹了Java Socket一對多通信實現(xiàn)之并發(fā)處理方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08Java并發(fā)編程:CountDownLatch與CyclicBarrier和Semaphore的實例詳解
這篇文章主要介紹了Java并發(fā)編程:CountDownLatch與CyclicBarrier和Semaphore的實例詳解的相關(guān)資料,需要的朋友可以參考下2017-09-09