欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java面試題之HashMap 的 hash 方法原理是什么

 更新時間:2021年11月05日 09:11:49   作者:沉默王二  
那天,小二去蔚來面試,面試官老王一上來就問他: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 就是:

image.png

我們來驗證一下,假如 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)文章

  • JavaWeb開發(fā)中alias攔截器的使用方法

    JavaWeb開發(fā)中alias攔截器的使用方法

    本文給大家介紹在JavaWeb開發(fā)中alias攔截器的使用方法相關(guān)知識,本文介紹的非常詳細,具有參考借鑒價值,感興趣的朋友一起看下吧
    2016-08-08
  • Java并發(fā) synchronized鎖住的內(nèi)容解析

    Java并發(fā) synchronized鎖住的內(nèi)容解析

    這篇文章主要介紹了Java并發(fā) synchronized鎖住的內(nèi)容解析,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2019-09-09
  • Java實現(xiàn)在正則表達式中控制大小寫的方法

    Java實現(xiàn)在正則表達式中控制大小寫的方法

    這篇文章主要介紹了Java實現(xiàn)在正則表達式中控制大小寫的方法,結(jié)合實例形式分析了java正則表達式中傳遞控制參數(shù)的功能與相關(guān)操作技巧,需要的朋友可以參考下
    2017-04-04
  • Springboot整合SpringSecurity實現(xiàn)登錄認證和鑒權(quán)全過程

    Springboot整合SpringSecurity實現(xiàn)登錄認證和鑒權(quán)全過程

    這篇文章主要介紹了Springboot整合SpringSecurity實現(xiàn)登錄認證和鑒權(quán)全過程,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2023-12-12
  • 探索Java I/O 模型的演進

    探索Java I/O 模型的演進

    什么是同步?什么是異步?阻塞和非阻塞又有什么區(qū)別?本文先從 Unix 的 I/O 模型講起,介紹了5種常見的 I/O 模型。而后再引出 Java 的 I/O 模型的演進過程,并用實例說明如何選擇合適的 Java I/O 模型來提高系統(tǒng)的并發(fā)量和可用性。,需要的朋友可以參考下
    2019-06-06
  • java通過URLClassLoader類加載器加載外部jar代碼示例

    java通過URLClassLoader類加載器加載外部jar代碼示例

    ClassLoader翻譯過來就是類加載器,普通的java開發(fā)者其實用到的不多,但對于某些框架開發(fā)者來說卻非常常見,下面這篇文章主要給大家介紹了關(guān)于java通過URLClassLoader類加載器加載外部jar的相關(guān)資料,需要的朋友可以參考下
    2024-01-01
  • SpringBoot中AOP的動態(tài)匹配和靜態(tài)匹配詳解

    SpringBoot中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值

    這篇文章主要介紹了詳解Java8的forEach(...)如何提供index值,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-03-03
  • Java Socket一對多通信實現(xiàn)之并發(fā)處理方式

    Java Socket一對多通信實現(xiàn)之并發(fā)處理方式

    這篇文章主要介紹了Java Socket一對多通信實現(xiàn)之并發(fā)處理方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2023-08-08
  • Java并發(fā)編程:CountDownLatch與CyclicBarrier和Semaphore的實例詳解

    Java并發(fā)編程:CountDownLatch與CyclicBarrier和Semaphore的實例詳解

    這篇文章主要介紹了Java并發(fā)編程:CountDownLatch與CyclicBarrier和Semaphore的實例詳解的相關(guān)資料,需要的朋友可以參考下
    2017-09-09

最新評論