小米,滴滴,快手……都在問!HashMap的容量為什麼是2的n次方

2021-01-08 素秋雲

回答這個問題,我們首先需要知道HashMap是如何存取元素的,為了存取高效,需要把數據分布均勻,這我們就需要分析HashMap的源碼,從底層上理解Java作者的意圖。

HashMap如何存放元素

HashMap存放元素時通過put()方法來實現的,我們知道定位元素的存放位置,是通過key的hash值,做一定的運算來確定的,而HashMap中的hash()方法,就是來獲取hash值的源碼如下。

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

這裡計算的hash值,並不是直接使用key.hashCode()來獲取的值h(後面統一稱為h),而是用h與h無符號右移的值做異或運算。

h >>> 16 這裡先解釋下這句話什麼意思,>>>其實是無符號右移,什麼意思呢,我們看下圖就明白了。

將h轉換成二進位數,然後無符號右移16位,空缺的用0補齊,看圖中字體顏色我們就能清楚地明白這是怎麼操作的。

h^ (h >>> 16)的作用

想要知道寫HashMap源碼大佬的想法,我們還需要來看看HashMap中put()方法的源碼。

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; 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); ......省略 }

我們從源碼中可以看出來,計算下標的時候,是通過(n - 1) & hash來計算的,n = tab.length是HashMap的容量,用HashMap容量減1與hash值做&運算,得出下標值。

HashMap默認初始容量位16,16-1=15,15的二進位為00000000 00000000 00001111,與hash值做&運算時,結果是只取了最低的後四位,hash值的高位全部歸0,只保留了低位值。有的同學,可能不太清楚什麼意思,我們舉個例子,畫個圖就清楚了。

假如有個key的hash值,轉化為二進位是,01001001 00110010 00011001,獲取元素下標時,用HashMap容量減1的二進位與hash值的二進位做&運算,如下圖所示。

我們可以看到hash值二進位的高位都補0了,其實上面的計算可以簡化為 1111 & 1001,結果為1001,轉換成十進位就是9,即下標為9。

當HashMap容量為16=2的4次方時,則是後4位參與&運算當HashMap容量為32=2的5次方時,則是後5位參與&運算當HashMap容量為2時,則是後n位參與&運算,獲取元素下標。 因為在大多數情況下,HashMap的容量是小於2的16次方,運算得到的下標都是與hashcode的二進位的後16位做&運算的到的值。

要想得到的hash值更加的散列,我們需要把高位和低位都參與運算,這樣的算出的hash值,更有特徵。如果直接返回hash值,獲取元素下標值,參與取模運行的低位,重複性偏高,將高16位和低16位做&運算,這樣算出來的hash值,更加分散,hash碰撞的概率就越小,所以就有了h^(h>>>16)。

HashMap容量為2的作用

我們知道HashMap底層由數組+(鍊表或紅黑樹)來實現,元素都被存放在一個個Entry數組中,存放元素的時候,會根據HashMap中hash()方法計算key的hash值,再根據計算出的hash值,確定元素存到數組的哪個位置,即下標值,一般HashMap的容量不會太大,而hash值並不能直接作為下標值,所以一般根據HashMap的容量減1來取模計算下標值(PS:上面已經介紹了具體做法)。

當容量為2時,取模的是時候,h&(n-1)與h%n計算的結果相等,而&運算的效率遠遠比用%效率更高,因為&是直接對內存中的二進位碼進行操作,不需要轉換為十進位,所以更快。計算下標值的公式為h&(n-1),當容量為奇數時,n-1則為偶數,轉換成二進位,最後一位一定是0,在做&運算計算下標值時,最後一位也一定是0,則奇數位的下標值,則無法取到,如3(0011), 5(0101),7(0111)等,所以容量為偶數時,才能取到奇數下標值。

總結

HashMap的容量為2主要目的還是為了讓元素均勻分布,減少hash碰撞。從HashMap中的hash()方法就知道,讓高位和低位都參與運算,讓hash值更有特徵性,在通過計算的hash值,與容量減一做&運算得到下標值,綜合分析,當容量為2時,元素存放更均勻,效率也更快。

相關焦點

  • Java初學者進階系列:HashMap的容量與性能
    HashMap的容量與性能HashMap的性能受到兩個參數的影響:初始化容量和負載因子,下面來詳細講述這幾個關鍵問題。初始化容量和負載因子的默認值是Java官方經過實踐和優化得到的數據,可以適應大多數的場景。
  • 3,4,5的大表哥歐拉猜想:n個整數的n次方之和是另一個整數的n次方...
    費馬說在整數n>2時,A,B,C 沒有正整數解,他進一步推廣,並猜想了許多的相關等式都不成立,特別是那句著名的梗:我有一個絕妙的證明但太長了寫不下,深深的印在我們的腦海裡。畢達哥拉斯定理早已被大眾熟知當你知道了勾股定理,就會很自然地去問類似的等式是否成立,比如說這個第一個式子有無窮多組正整數解,最後一個也有一組漂亮的解,下圖所示,是不是很漂亮數學巨匠歐拉,認為還能繼續推廣,歐拉已經知道有些數的立方,能寫成3個立方數的和,比如漂亮的3,4,5,6,它們是勾股數
  • 歐拉猜想:n個整數的n次方之和等於另一個整數的n次方
    費馬大定理的具體的描述是:整數n >2時,關於x, y, z的方程 x^n + y^n = z^n 沒有正整數解。>如果n=4的情況下,費馬大定理是成立,那麼也就證明了n=8.n=12,n=16.......的情況下也是成立的。
  • 469,位運算求最小的2的n次方
    給一個函數f(x),返回一個不小於x的最小的2的n次方。描述的比較繞口,舉個例子。f(7)=8f(9)=16f(30)=32f(64)=64注意:x是正整數0<x<Integer.MAX_VALUE我們看到返回的結果都是2的n次方,並且是不小於x的最小的2的n次方。
  • 搞定HashMap面試,深入講解HashMap的工作原理
    為什麼HashMap深受面試官青睞,我想有這3個原因:常用、基礎線程不安全,容易出問題大廠都在問,自己不問顯得面試官沒水平Hash虐我千百遍,我視它為初戀,真的是又愛又恨。愛的是每次面試都有它,可以提前做準備,恨的是準備也白準備,依然被滅。這次要做回真正的男人,和它做一個了斷。互虐一次,一勞永逸。
  • √2的√2次方是無理數嗎?
    這個定理告訴我們,假設 α 和 β 都是代數數,如果 α 不等於 0 和 1 ,並且 β 不是有理數,那麼 α 的 β 次方一定是超越數。根據這一定理我們可以立即看出,根號 2 的根號 2 次方真的是一個無理數,實際情況應該是上述推理中的後者。     那麼,是否存在一個無理數 a ,使得 a 的 a 次方是有理數呢?
  • C/C++語言中將一個正整數圓整為2的n次方的方法
    問題提出在數位訊號處理領域,常遇到需要將一個正整數向上圓整為2的n次方的數據的情況,如對採集到的時域信號做頻譜分析時,常要求數據點數必須滿足為2的n次方,滿足此種情況才可用傅立葉變換的基2快速算法,以達到較好的運算速度。
  • x的n次方-1的因式分解及應用
    下面公式為初等數學中常用的2個在初高中大部分老師對於第二個公式都是直接讓記住,但如果不經常使用,勉強記住不僅容易記錯而且很容易忘記,還是理解了再記憶更加容易。今天小編介紹的是x的n次方-1的通用分解因式和他的證明,以及公式在等比數列前n項和and某個高等數學等價無窮小的證明中的使用。先上公式那麼這個公式有什麼用呢?1,求等比數列的前N項和雖然在初等數學教科書中用了倍差法推出了前n項和公式,但是我們也可以用上面的公式求。
  • LeetCode-50.求X的N次方(Pow(x, n))
    = 1/4 = 0.25說明:-100.0 < x < 100.0n 是 32 位有符號整數,其數值範圍是 [−2^31, 2^31 − 1] 。 def helper(self, x: float, n: int) -> float: if n == 0: return 1.0 half = self.helper(x, n // 2) if n & 1 == 1: return half * half * x
  • 2的0次方為什麼等於1?
    、10、1又分別可以使用10^3(10的3次方)、10^2、10^1、10^0來表示,所以十進位計數法的數位都是10^n的形式,n從右往左分別為0、1、2、3、4.....,10稱作十進位計數法的基數或底,n稱作指數。
  • 為什麼在計量型特徵值的控制圖中,通常建議子組容量n等於5?
    問:為什麼在計量型特徵值的控制圖中,通常建議子組容量n等於5?答:經過精心策劃的取樣方案是成功運用控制圖控制過程的關健因素。子組樣本容量n等於5是多方面綜合考慮的結果,它也不是強制的,建議大家考慮子組容量時,能結合控制圖的功效曲線來看。
  • 英讀廊——為什麼1T的固態硬碟顯示只有931G容量?
    【譯】為什麼1TB的SSD只能提供931GB的空間?【解析】1TB在這裡是指硬碟的容量,其中,B代表bytes,即「字節」,一個字節表示計算機領域中的8個2進位位,T則表示trillion,即萬億,1TB即1萬億個字節。
  • 怎麼求一個數的n次方?
    怎麼求一個數的n次方?有興趣的朋友可以了解一下!一、前言excel是我們工作中經常使用的一款表格製作工具,它不僅僅只是用來製作表格,而在表格數據的處理方面也顯得非常突出。excel為我們提供了很多函數,對於一些常用簡單的函數我們應該要了解,這能大大提高我們的工作效率。
  • 一文讀懂Java之HashMap索引位置計算
    1.2 index的計算原則Entry[]數組的長度在初始化的時候會被指定,假定這個值為length。那index的值就從 0 ~ length-1。所以index需要儘可能的平衡,也就是分布均勻,不能某些位置上存儲特別多的數據,某些位置上又特別少。
  • 根號十的負二次方等於多少 √10的負2次方
    根號十的負二次方等於十分之一。根號10等於10的2分之1次方,10的2分之1次方的負2次方等於10的負1次方,等於10分之1。若aⁿ=b,那麼a是b開n次方的n次方根或a是b的1/n次方。開n次方手寫體和印刷體用表示,被開方的數或代數式寫在符號左方√ ̄的右邊和符號上方一橫部分的下方共同包圍的區域中,而且不能出界。
  • 看完這篇 HashMap,和面試官扯皮就沒問題了
    初始容量不同:HashTable 的初始長度是11,之後每次擴充容量變為之前的 2n+1(n為上一次的長度)而 HashMap 的初始長度為16,之後每次擴充變為原來的兩倍。創建時,如果給定了容量初始值,那麼HashTable 會直接使用你給定的大小,而 HashMap 會將其擴充為2的冪次方大小。
  • 【數學】0的0次方到底等於幾?
    有一次,Vita哥哥問了我一個非常刁鑽的問題:0的0次方等於幾?
  • 準大學生疑問:為什麼所有人都不推薦我買小米手機?
    前幾天一個粉絲滴滴我,和我聊了一下,自己剛高考結束,想買一手手機,看中了小米的小米 10 Pro,自己目前在打暑假工,旁邊就有一家手機店,想著線下賣手機會送很多禮品,於是去店子買手機,但是店員都是推薦不要買小米,小米不行並且推薦給我vivo X50 Pro+。
  • 數學 | 2的-2次方等於幾?不如讓娃自己琢磨一下
    負數次方其實並不是一個獨立的概念,只不過是把指數擴展到了負數而已,就好像我們可以把加減乘除運算擴展到負數一樣,它一定是能夠從已知的一些規律推導出來的。這個推理的核心都在畫紅圈的地方,我來替他整理一下。到這裡,他把n用我問題中的數2代入,於是有:
  • 短途旅行一個就夠,小米20000mAh大容量移動電源2C發布
    2017年9月14日,小米生態鏈推出小米移動電源2C 20000mAh ,採用高品質鋰聚合物電芯,大容量,支持QC3.0,雙USB輸出,微電流充電,雙向快充等實用功能,可以對各種設備進行迅速且安全的充電,中短期旅行只要帶這樣一款移動電源就夠用。