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