java中hashmap容量的初始化實(shí)現(xiàn)
HashMap使用HashMap(int initialCapacity)對(duì)集合進(jìn)行初始化。
在默認(rèn)的情況下,HashMap的容量是16。但是如果用戶通過構(gòu)造函數(shù)指定了一個(gè)數(shù)字作為容量,那么Hash會(huì)選擇大于該數(shù)字的第一個(gè)2的冪作為容量。比如如果指定了3,則容量是4;如果指定了7,則容量是8;如果指定了9,則容量是16。
為什么要設(shè)置HashMap的初始化容量
在《阿里巴巴Java開發(fā)手冊(cè)》中,有一條開發(fā)建議是建議我們?cè)O(shè)置HashMap的初始化容量。
下面我們通過具體的代碼來了解下為什么會(huì)這么建議。
我們先來寫一段代碼在JDK1.7的環(huán)境下運(yùn)行,來分別測(cè)試下,在不指定初始化容量和指定初始化容量的情況下性能情況的不同。
public static void main(String[] args) { int aHundredMillion = 10000000; // 未初始化容量 Map<Integer, Integer> map = new HashMap<>(); long s1 = System.currentTimeMillis(); for (int i = 0; i < aHundredMillion; i++) { map.put(i, i); } long s2 = System.currentTimeMillis(); System.out.println("未初始化容量,耗時(shí): " + (s2 - s1)); // 14322 // 初始化容量為50000000 Map<Integer, Integer> map1 = new HashMap<>(aHundredMillion / 2); long s3 = System.currentTimeMillis(); for (int i = 0; i < aHundredMillion; i++) { map1.put(i, i); } long s4 = System.currentTimeMillis(); System.out.println("初始化容量5000000,耗時(shí): " + (s4 - s3)); // 11819 // 初始化容量為100000000 Map<Integer, Integer> map2 = new HashMap<>(aHundredMillion); long s5 = System.currentTimeMillis(); for (int i = 0; i < aHundredMillion; i++) { map2.put(i, i); } long s6 = System.currentTimeMillis(); System.out.println("初始化容量為10000000,耗時(shí): " + (s6 - s5)); // 7978 }
從以上的代碼不難理解,我們創(chuàng)建了3個(gè)HashMap,分別使用默認(rèn)的容量(16)、使用元素個(gè)數(shù)的一半(5千萬)作為初始容量和使用元素個(gè)數(shù)(一億)作為初始容量進(jìn)行初始化,然后分別向其中put一億個(gè)KV。
從上面的打印結(jié)果中可以得到一個(gè)初步的結(jié)論:在已知HashMap中將要存放的KV個(gè)數(shù)的時(shí)候,設(shè)置一個(gè)合理的初始化容量可以有效地提高性能。下面我們來簡單分析一下原因。
我們知道,HashMap是有擴(kuò)容機(jī)制的。所謂的擴(kuò)容機(jī)制,指的是當(dāng)達(dá)到擴(kuò)容條件的時(shí)候,HashMap就會(huì)自動(dòng)進(jìn)行擴(kuò)容。而HashMap的擴(kuò)容條件就是當(dāng)HashMap中的元素個(gè)數(shù)(Size)超過臨界值(Threshold)的情況下就會(huì)自動(dòng)擴(kuò)容。
threshold = loadFactor * capacity
在元素個(gè)數(shù)超過臨界值的情況下,隨著元素的不斷增加,HashMap就會(huì)發(fā)生擴(kuò)容,而HashMap中的擴(kuò)容機(jī)制決定了每次擴(kuò)容都需要重建hash表,這一操作需要消耗大量資源,是非常影響性能的。因此,如果我們沒有設(shè)置初始的容量大小,HashMap就可能會(huì)不斷發(fā)生擴(kuò)容,也就使得程序的性能降低了。
另外,在上面的代碼中我們會(huì)發(fā)現(xiàn),同樣是設(shè)置了初始化容量,設(shè)置的數(shù)值不同也會(huì)影響性能,那么當(dāng)我們已知HashMap中即將存放的KV個(gè)數(shù)的時(shí)候,容量的設(shè)置就成了一個(gè)問題。
HashMap中容量的初始化
開頭提到,在默認(rèn)的情況下,當(dāng)我們?cè)O(shè)置HashMap的初始化容量時(shí),實(shí)際上HashMap會(huì)采用第一個(gè)大于該數(shù)值的2的冪作為初始化容量。
Map<String, String> map = new HashMap<>(1); map.put("huangq", "yanggb"); Class<?> mapType = map.getClass(); Method capacity = mapType.getDeclaredMethod("capacity"); capacity.setAccessible(true); System.out.println("capacity : " + capacity.invoke(map)); // 2
當(dāng)初始化的容量設(shè)置成1的時(shí)候,通過反射取出來的capacity卻是2。在JDK1.8中,如果我們傳入的初始化容量為1,實(shí)際上設(shè)置的結(jié)果也是1。上面的代碼打印的結(jié)果為2的原因,是代碼中給map塞入值的操作導(dǎo)致了擴(kuò)容,容量從1擴(kuò)容到了2。事實(shí)上,在JDK1.7和JDK1.8中,HashMap初始化容量(capacity)的時(shí)機(jī)不同。在JDK1.8中,調(diào)用HashMap的構(gòu)造函數(shù)定義HashMap的時(shí)候,就會(huì)進(jìn)行容量的設(shè)定。而在JDK1.7中,要等到第一次put操作時(shí)才進(jìn)行這一操作。
因此,當(dāng)我們通過HashMap(int initialCapacity)設(shè)置初始容量的時(shí)候,HashMap并不一定會(huì)直接采用我們傳入的數(shù)值,而是經(jīng)過計(jì)算,得到一個(gè)新值,目的是提高h(yuǎn)ash的效率。比如1->1、3->4、7->8和9->16。
HashMap中初始容量的合理值
通過上面的分析我們可以知道,當(dāng)我們使用HashMap(int initialCapacity)來初始化容量的時(shí)候,JDK會(huì)默認(rèn)幫我們計(jì)算一個(gè)相對(duì)合理的值當(dāng)做初始容量。那么,是不是我們只需要把已知的HashMap中即將存放的元素個(gè)數(shù)直接傳給initialCapacity就可以了呢?
initialCapacity = (需要存儲(chǔ)的元素個(gè)數(shù) / 負(fù)載因子) + 1
這里的負(fù)載因子就是loaderFactor,默認(rèn)值為0.75。
initialCapacity = expectedSize / 0.75F + 1.0F
上面這個(gè)公式是《阿里巴巴Java開發(fā)手冊(cè)》中的一個(gè)建議,在Guava中也是提供了相同的算法,更甚之,這個(gè)算法實(shí)際上是JDK8中putAll()方法的實(shí)現(xiàn)。這是公式的得出是因?yàn)椋?dāng)HashMap內(nèi)部維護(hù)的哈希表的容量達(dá)到75%時(shí)(默認(rèn)情況下),就會(huì)觸發(fā)rehash(重建hash表)操作。而rehash的過程是比較耗費(fèi)時(shí)間的。所以初始化容量要設(shè)置成expectedSize/0.75 + 1的話,可以有效地減少?zèng)_突,也可以減小誤差。
總結(jié)
當(dāng)我們想要在代碼中創(chuàng)建一個(gè)HashMap的時(shí)候,如果我們已知這個(gè)Map中即將存放的元素個(gè)數(shù),給HashMap設(shè)置初始容量可以在一定程度上提升效率。
但是,JDK并不會(huì)直接拿用戶傳進(jìn)來的數(shù)字當(dāng)做默認(rèn)容量,而是會(huì)進(jìn)行一番運(yùn)算,最終得到一個(gè)2的冪。而為了最大程度地避免擴(kuò)容帶來的性能消耗,通常是建議可以把默認(rèn)容量的數(shù)字設(shè)置成expectedSize / 0.75F + 1.0F。
在日常開發(fā)中,可以使用Guava提供的一個(gè)方法來創(chuàng)建一個(gè)HashMap,計(jì)算的過程Guava會(huì)幫我們完成。
Map<String, String> map = Maps.newHashMapWithExpectedSize(10);
最后要說的一點(diǎn)是,這種算法實(shí)際上是一種使用內(nèi)存換取性能的做法,在真正的應(yīng)用場(chǎng)景中要考慮到內(nèi)存的影響。
以上就是本文的全部內(nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
java 實(shí)現(xiàn)雙向鏈表實(shí)例詳解
這篇文章主要介紹了java 實(shí)現(xiàn)雙向鏈表實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-03-03使用SpringBoot-JPA進(jìn)行自定義保存及批量保存功能
這篇文章主要介紹了使用SpringBoot-JPA進(jìn)行自定義的保存及批量保存功能,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-06-06java實(shí)現(xiàn)微信點(diǎn)餐申請(qǐng)微信退款
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)微信點(diǎn)餐申請(qǐng)微信退款,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-09-09SpringBoot使用Validator進(jìn)行參數(shù)校驗(yàn)實(shí)戰(zhàn)教程(自定義校驗(yàn),分組校驗(yàn))
這篇文章主要介紹了SpringBoot使用Validator進(jìn)行參數(shù)校驗(yàn)(自定義校驗(yàn),分組校驗(yàn))的實(shí)戰(zhàn)教程,本文通過示例代碼給大家介紹的非常詳細(xì),需要的朋友參考下吧2023-07-07Java實(shí)現(xiàn)的爬蟲抓取圖片并保存操作示例
這篇文章主要介紹了Java實(shí)現(xiàn)的爬蟲抓取圖片并保存操作,涉及Java針對(duì)頁面URL訪問、獲取、字符串匹配、文件下載等相關(guān)操作技巧,需要的朋友可以參考下2018-08-08RabbitMQ中的channel信道、exchange交換機(jī)和queue隊(duì)列詳解
這篇文章主要介紹了RabbitMQ中的channel信道、exchange交換機(jī)和queue隊(duì)列詳解,connection是指物理的連接,一個(gè)client與一個(gè)server之間有一個(gè)連接,一個(gè)連接上可以建立多個(gè)channel,可以理解為邏輯上的連接,需要的朋友可以參考下2023-08-08