HashMap每次擴(kuò)容為什么是2倍
當(dāng)HashMap在初始化沒有指定容量的情況下，首次添加元素時(shí)，數(shù)組的容量為16；當(dāng)超出閾值，數(shù)組容量為擴(kuò)容為之前的2倍。
為什么HashMap每次擴(kuò)容都是之前的2倍？而不是像ArrayList首次為10，后續(xù)為1.5倍呢？2倍不是很浪費(fèi)空間嗎？
HashMap的putVal方法源碼，如下圖所示：
其中 n 為數(shù)組的長度，n - 1 為數(shù)組的最大索引值。(n - 1) & hash 的意思是將每個(gè)元素的key的hash值，與最大索引值-1進(jìn)行相與操作，得出該元素在數(shù)組中的位置。hash是添加的元素進(jìn)過哈希函數(shù)計(jì)算出來的值。
每次擴(kuò)容后的數(shù)組長度如下表：
與運(yùn)算的規(guī)則如下，只要有一個(gè)0，結(jié)果就是0；兩個(gè)同時(shí)為1，結(jié)果才是1。
1 & 0 = 0 0 & 1 = 0 1 & 1 = 1 0 & 0 = 0
假如HashMap的容量不是2的n次冪，設(shè)容量為10，二進(jìn)制為01010，(n-1)的二進(jìn)制是01001，向里面添加同樣的元素9,12,13,15，結(jié)果為：
可以看出，9,13,15得出的結(jié)果都是9，index相同，hash碰撞嚴(yán)重。
當(dāng)HashMap的容量是16時(shí)，它的二進(jìn)制是10000，(n-1)是15,二進(jìn)制表示是01111，和hash值9,12,13,15進(jìn)行與運(yùn)算，計(jì)算結(jié)果如下：
還是9,12,13,15?？梢钥闯?，與運(yùn)算后得出不同的值，使得添加的元素能夠均勻分布在集合中不同的位置上，避免hash碰撞。
綜上所述，HashMap計(jì)算添加元素的位置時(shí)，使用的位運(yùn)算，這是高效的運(yùn)算；
另外，HashMap的初始容量是2的n次冪，擴(kuò)容也是2倍的形式進(jìn)行擴(kuò)容，是因?yàn)槿萘渴?的n次冪，可以使得添加的元素均勻分布在HashMap中的數(shù)組上，減少hash碰撞，避免形成鏈表的結(jié)構(gòu)，使得查詢速度降低！
到此這篇關(guān)于HashMap擴(kuò)容為什么是2倍的文章就介紹到這了,更多相關(guān)HashMap擴(kuò)容2倍內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
基于java查找并打印輸出字符串中字符出現(xiàn)次數(shù)
這篇文章主要介紹了基于java查找并打印輸出字符串中字符出現(xiàn)次數(shù),文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-11-11
輕松理解Java面試和開發(fā)中的IoC（控制反轉(zhuǎn)）
在Java開發(fā)中，IoC意 味著將你設(shè)計(jì)好的類交給系統(tǒng)去控制，而不是在你的類內(nèi)部控制。這稱為控制反轉(zhuǎn)。下文給大家介紹Java面試和開發(fā)中的IoC（控制反轉(zhuǎn)）知識(shí)，需要的朋友參考下吧2017-07-07
java結(jié)束程序進(jìn)程的方法很簡單，只要一句代碼就行，大家參考使用吧2013-12-12
在真實(shí)的應(yīng)用場(chǎng)景中，很多時(shí)候需要使用?Java?讀寫文件。比如說，讀取配置文件信息、讀取用戶輸入等。本篇文章將會(huì)詳細(xì)介紹?Java?文件讀寫的相關(guān)知識(shí)，其中包括：讀取文件、寫入文件、復(fù)制文件和刪除文件等操作,需要的朋友可以參考下2023-05-05
今天小編就為大家分享一篇關(guān)于IntelliJ IDEA查看方法說明文檔的圖解，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2018-10-10
這篇文章主要介紹了Java?輪詢鎖使用時(shí)遇到問題解決方案，當(dāng)我們遇到死鎖之后，除了可以手動(dòng)重啟程序解決之外，還可以考慮使用順序鎖和輪詢鎖，但是過程也會(huì)遇到一些問題，接下來我們一起進(jìn)入下面文章了解解決方案，需要的小伙伴可以參考一下2022-05-05
Java實(shí)現(xiàn)輸出數(shù)字三角形實(shí)例代碼
大家好，本篇文章主要講的是Java實(shí)現(xiàn)輸出三角形實(shí)例代碼，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
SpringBoot整合Redis實(shí)現(xiàn)熱點(diǎn)數(shù)據(jù)緩存的示例代碼
這篇文章主要介紹了SpringBoot中整合Redis實(shí)現(xiàn)熱點(diǎn)數(shù)據(jù)緩存,本文以IDEA?+?SpringBoot作為?Java中整合Redis的使用?的測(cè)試環(huán)境，結(jié)合實(shí)例代碼給大家詳細(xì)講解，需要的朋友可以參考下2023-03-03
本文介紹了springboot開發(fā)后端服務(wù)中,AI組件(Spring AI)的整合與使用,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),感興趣的朋友跟隨小編一起看看吧2024-05-05
spring boot對(duì)緩存支持非常靈活,我們可以使用默認(rèn)的EhCache,也可以整合第三方的框架,只需配置即可,下面這篇文章主要給大家介紹了關(guān)于SpringBoot學(xué)習(xí)之基于注解緩存的相關(guān)資料,需要的朋友可以參考下2022-08-08