小米,滴滴,快手……都在問!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時,元素存放更均勻,效率也更快。

相關焦點

  • 數值的整數次方(劍指 Offer 題解Java版)
    數值的整數次方題目連結題目描述解題思路實現代碼16. 數值的整數次方題目連結NowCoder題目描述給定一個 double 類型的浮點數 base 和 int 類型的整數 exponent,求 base 的 exponent 次方。解題思路下面的討論中 x 代表 base,n 代表 exponent。
  • 美版快手「Zynn」在美上線,抖音的海外對手來了;SpaceX發射成功...
    5月29日,雷軍在騰訊新聞話題訪談欄目「Q問」上表示,如果與董明珠的「賭約」能讓中國製造更強大,他願意接受。雷軍表示,小米和格力的「賭局」的本質是國產品牌在市場上你追我趕、相互促進。從去年兩家公司的年報來看,小米整體營收已經超過格力。他還預測,衛星網際網路大規模商用還需要5-10年,中國衛星網際網路將可以很快追上美國。(騰訊)6.雷軍:小米高管80%以上都是內部提拔,不會參與商業航天業務小米創始人雷軍 表示,全球疫情對小米業務有一定影響,但是影響是階段性的、可控的。
  • 快手將於2月5日在港上市;唯品會被立案調查;小米加盟商自曝已虧...
    文 | 靜靜更多創業內容請訪問www.iheima.com今日頭條1.快手將於2月5日在港上市,擬籌資50億美元據報導,短視頻初創公司快手已於1月14日下午通過港交所聆訊,計劃2月第一周上市。知情人士稱,快手此次計劃募資約50億美元。
  • BN早報:傳滴滴0元收購小藍,人人因區塊鏈被約談,投行稱小米2000億...
    隨後,周鴻禕在王思聰微信朋友圈回應稱,「你們都撒幣,我大撒幣,比你們厲害。」滴滴APP將上線共享單車入口,打開後是一個地圖頁面,地圖上有黃色的ofo和藍色的小藍單車,未來還將加入滴滴自有單車品牌。,也就是說滴滴只負責接管債務,不會支付任何現金等。」
  • 抖音是下山虎,快手是草原狼
    很多人對此不解,為什麼那個產品能做大做強,而這個產品就會成為歷史塵埃。 今天3W隆重推出「競品研究社」欄目,直面對比同賽道產品,分析它們優點與缺陷,揭露它們能在短兵相接的商戰中脫穎而出的秘密... 用快手 CEO 宿華的話說,我們更在乎生活分享。快手的用戶更像是社會的鏡子和投影,都是用普通人自己的視角去觀察到的世界。 數據顯示,截至 2018 年 12 月,快手擁有超過 1.6 億日活用戶,3 億月活用戶,每日上傳短視頻超過 1500 萬條,庫存短視頻數量超過 80 億條。 2、平臺數據 安卓手機下載量對比
  • 小吉科技在小米智能家庭發布新品:屬於年輕人的洗衣機
    8月16日,小吉科技旗下產品——一臺可「進化」的智能迷你滾筒洗衣機(minij 6C)上線小米智能家庭眾籌,上線3.5小時便突破200萬。據了解,這是小吉科技推出的第二款迷你洗衣機,同時也是首個登陸小米眾籌的的非小米生態鏈企業的家電品牌。
  • 小米發布MIX3,雷軍懟華為:貴不一定最好;微信開放快手、微視分享...
    小米發布MIX3,雷軍懟華為:貴不一定最好;微信開放快手、微視分享通道,抖音繼續被禁;ofo有意退出日本市場......雷軍說:「為什麼小廠與大廠差距越來越大,因為AI和相機的投入越來越大,每個項目的投入都是幾百人甚至上千人。」他將MIX3的手持超級夜景與華為P20 Pro的超級夜景做對比,並再次開懟:「友商的手機賊貴,但貴的不一定是最好的。」(新浪科技)國內新聞2.
  • 2的3次方和冷熱陰陽論,揭示先天八卦的數理
    但都離不開一個數字和一個理字,二者是不可分割的。本文認為數理更多反映的是數字所表達的道理,是以數論道。玄莊策馬早年學習易經和洛書,並沒有領悟其中的數理。數理上是2的3次方,體現出一生二,二生三,三生萬物。下圖是傳承的經典演示。
  • 快手視頻問姻緣
    快手視頻問姻緣2020年04月18日20時21分農曆:二零二零年 三月 二六日 戌時幹支:庚子 庚辰
  • 為什麼滴滴、順豐、釘釘、閒魚並不是一個好名字?
    、閒魚、釘釘和順豐,我是說——所有帶諧音或者多音的名字都不是好名字。2我們來看兩個改名的案例——滴滴打車開始的時候並不叫滴滴,而是叫嘀嘀,2014年5月,滴滴才正式從嘀嘀更名為「滴滴」。那麼,它為什麼要更名呢?
  • 零基礎學周易(十六)先天八卦數為什麼乾1兌2離3…
    所有學過《周易》的學者都應該知道,先天八卦中乾卦(☰)的先天數為1、兌(duì)卦(☱)的先天數為2、離卦(☲)的先天數為3、震卦(☳)的先天數為4、巽(xùn)卦(☴)的先天數為5、坎(kǎn)卦(☵)的先天數為6、艮(gèn)卦(☶)的先天數為7、坤卦(☷)的先天數為8。但是很少人知道這是為什麼?
  • 深度資訊 | 2018年巨虧109億元,7歲滴滴的虧損窟窿是被什麼捅大的?
    文 | 36氪每日商業精選2018年巨虧109億元,7歲滴滴的虧損窟窿是被什麼捅大的?36氪得到的一份滴滴出行內部流傳出來的財務數據顯示,2018全年滴滴虧損109億元,同比(2017年為25億元)虧損擴大4倍多,僅下半年的虧損額就達68.6億元,整年光是司機補貼就投入了113億元。對於虧損,滴滴從來坦誠。
  • 花生票號談新經濟:螞蟻金服、小米、滴滴等公司的供應鏈金融ABS...
    據報導,3月19日,滴滴新型供應鏈金融ABS取得上海證券交易所無異議函,獲批儲架發行額度為100億元,首期擬發行規模3億元。而在3月2日,小米公司供應鏈金融ABS100億元儲架發行獲批,3月16日,德邦螞蟻供應鏈金融應收帳款ABS20億元發行獲批。  近兩年,供應鏈金融相關類別ABS大有提速趨勢。目前市場上按照發行主體來看,供應鏈金融ABS可劃分為網際網路公司和傳統行業。
  • 丁磊將在快手直播帶貨;董明珠:不認識李佳琦
    白皮書顯示,中國新冠肺炎累計治癒率94.3%,新冠確診患者人均醫療費2.3萬,全部由國家承擔。外交部表示,已宣布向77個有關發展中國家暫停債務償還。IOC委員:東京奧運會要麼在2021年舉行,要麼取消由於新冠病毒疫情,東京奧運會推遲到2021年7月23日至8月8日舉行。
  • 小米筆記本體驗 關注性能/續航/散熱的請點這裡
    當然筆記本畢竟是筆記本,真拼輕薄的話,和2in產品完全不在一個級別。  題外話,這裡給蘋果喊個冤,樹大招風啊,天天被人秒殺,比不過蘋果都不好意思出門了。不過令人深思的是為啥一款天天被秒殺的產品,銷量那麼高呢?大家自己琢磨.....
  • 小米官宣,11月5日發布,可以戴在手上的小型手機?
    因為小米在小米9Pro後,終於又要迎來又一款新手機了,而且還是有著一億像素的五攝手機。但對筆者來說,最期待的並不是這款手機,而是小米的手錶。目前市場上也有許多的智能手錶在銷售,但大部分的功能和智能手環相差並不大,就和為手環換了一個大一點的屏幕一樣,那麼小米手錶的實力怎麼樣呢,讓我們一起來看看小米官博的爆料,來認識一下它!
  • 三星UFS2.0大容量來襲,2017年旗艦機或向256GB邁進
    2014年蘋果引領高端智能型手機向128GB發展,2015年搭載128GB容量的旗艦機紛紛湧進,2016年小米5也搭載了
  • 小米落後了?為什麼大家都用UFS3.0就小米不用,其實沒有那麼簡單
    不知道大家有沒有發現,最近「UFS3.0」這個專業性詞語開始頻繁的出現在大家的嚴重,很多新推出的手機都把UFS3.0作為一個賣點,並且大肆宣傳。UFS3.0也成了高端旗艦手機的標配,華為,OPPO,vivo,一加等廠商推出的旗艦機型都配有UFS3.0這一技術。
  • 【PW早報】周杰倫7月26日晚將在快手開啟直播首秀
    蘋果歷年都是在9月份發布手機,通常是在發布手機不久便向市場開始銷售。據報導稱,2020年的iPhone 12雖然仍保持在9月份發布,但起售時間推遲到了10月底。據報導,iPhone LTE‌ 12‌將在10月份公布,而5G型號將會在11月公布。