HashMap每次擴(kuò)容為什么是2倍
當(dāng)HashMap在初始化沒(méi)有指定容量的情況下，首次添加元素時(shí)，數(shù)組的容量為16；當(dāng)超出閾值，數(shù)組容量為擴(kuò)容為之前的2倍。
為什么HashMap每次擴(kuò)容都是之前的2倍？而不是像ArrayList首次為10，后續(xù)為1.5倍呢？2倍不是很浪費(fèi)空間嗎？
HashMap的putVal方法源碼，如下圖所示：
其中 n 為數(shù)組的長(zhǎng)度，n - 1 為數(shù)組的最大索引值。(n - 1) & hash 的意思是將每個(gè)元素的key的hash值，與最大索引值-1進(jìn)行相與操作，得出該元素在數(shù)組中的位置。hash是添加的元素進(jìn)過(guò)哈希函數(shù)計(jì)算出來(lái)的值。
每次擴(kuò)容后的數(shù)組長(zhǎng)度如下表：
與運(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)文章
SpringBoot中自定義首頁(yè)(默認(rèn)頁(yè))及favicon的方法
這篇文章主要介紹了SpringBoot中如何自定義首頁(yè)(默認(rèn)頁(yè))及favicon,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-08-08
文章介紹了如何使用jjwt插件實(shí)現(xiàn)Token的生成和校驗(yàn),該插件可以直接與SpringBoot集成,Token由三部分組成,分別是header、payload和signature,通過(guò)在請(qǐng)求頭中傳遞Token,后端可以驗(yàn)證其合法性,從而提高安全性2025-01-01
流（Stream）是指一連串的數(shù)據(jù)（字符或字節(jié)），是以先進(jìn)先出的方式發(fā)送信息的通道，數(shù)據(jù)源發(fā)送的數(shù)據(jù)經(jīng)過(guò)這個(gè)通道到達(dá)目的地，按流向區(qū)分為輸入流和輸出流2022-04-04
MyBatis-Generator的配置說(shuō)明和使用
本文主要介紹了MyBatis-Generator的配置說(shuō)明和使用的相關(guān)知識(shí)。具有很好的參考價(jià)值，下面跟著小編一起來(lái)看下吧2017-02-02
Java樂(lè)觀鎖防止數(shù)據(jù)沖突的詳細(xì)過(guò)程
樂(lè)觀鎖是一種并發(fā)控制機(jī)制,用于防止多個(gè)事務(wù)同時(shí)修改同一數(shù)據(jù)導(dǎo)致的數(shù)據(jù)不一致問(wèn)題,它通過(guò)在數(shù)據(jù)記錄中添加一個(gè)版本號(hào)或時(shí)間戳字段,來(lái)判斷數(shù)據(jù)在兩次操作之間是否被其他事務(wù)修改本文介紹了樂(lè)觀鎖防止數(shù)據(jù)沖突的詳細(xì)過(guò)程2025-04-04
這篇文章主要介紹了淺談java8 stream flatMap流的扁平化操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-08-08
這篇文章主要介紹了Druid如何平行替換為Hikari問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-05-05
這篇文章主要介紹了Java中的CompletableFuture詳解,Future接口(FutueTask實(shí)現(xiàn)類)定義了操作異步任務(wù)執(zhí)行一些方法,如獲取異步任務(wù)的執(zhí)行結(jié)果、取消任務(wù)的執(zhí)行、判斷任務(wù)是否被取消、判斷任務(wù)執(zhí)行是否完畢等,需要的朋友可以參考下2023-09-09
Java編程實(shí)現(xiàn)遍歷兩個(gè)MAC地址之間所有MAC的方法
這篇文章主要介紹了Java編程實(shí)現(xiàn)遍歷兩個(gè)MAC地址之間所有MAC的方法,涉及Java針對(duì)MAC的遍歷獲取與字符串轉(zhuǎn)換相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-11-11
這篇文章主要為大家介紹了Java之冒泡排序與選擇排序，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2021-12-12