分類
發燒車訊

java中hashmap容量的初始化

HashMap使用HashMap(int initialCapacity)對集合進行初始化。

在默認的情況下,HashMap的容量是16。但是如果用戶通過構造函數指定了一個数字作為容量,那麼Hash會選擇大於該数字的第一個2的冪作為容量。比如如果指定了3,則容量是4;如果指定了7,則容量是8;如果指定了9,則容量是16。

為什麼要設置HashMap的初始化容量

在《阿里巴巴Java開發手冊》中,有一條開發建議是建議我們設置HashMap的初始化容量。

下面我們通過具體的代碼來了解下為什麼會這麼建議。

我們先來寫一段代碼在JDK1.7的環境下運行,來分別測試下,在不指定初始化容量和指定初始化容量的情況下性能情況的不同。

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("未初始化容量,耗時: " + (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,耗時: " + (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,耗時: " + (s6 - s5)); // 7978
}

從以上的代碼不難理解,我們創建了3個HashMap,分別使用默認的容量(16)、使用元素個數的一半(5千萬)作為初始容量和使用元素個數(一億)作為初始容量進行初始化,然後分別向其中put一億個KV。

從上面的打印結果中可以得到一個初步的結論:在已知HashMap中將要存放的KV個數的時候,設置一個合理的初始化容量可以有效地提高性能。下面我們來簡單分析一下原因。

我們知道,HashMap是有擴容機制的。所謂的擴容機制,指的是當達到擴容條件的時候,HashMap就會自動進行擴容。而HashMap的擴容條件就是當HashMap中的元素個數(Size)超過臨界值(Threshold)的情況下就會自動擴容。

threshold = loadFactor * capacity

在元素個數超過臨界值的情況下,隨着元素的不斷增加,HashMap就會發生擴容,而HashMap中的擴容機制決定了每次擴容都需要重建hash表,這一操作需要消耗大量資源,是非常影響性能的。因此,如果我們沒有設置初始的容量大小,HashMap就可能會不斷髮生擴容,也就使得程序的性能降低了。

另外,在上面的代碼中我們會發現,同樣是設置了初始化容量,設置的數值不同也會影響性能,那麼當我們已知HashMap中即將存放的KV個數的時候,容量的設置就成了一個問題。

HashMap中容量的初始化

開頭提到,在默認的情況下,當我們設置HashMap的初始化容量時,實際上HashMap會採用第一個大於該數值的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

當初始化的容量設置成1的時候,通過反射取出來的capacity卻是2。在JDK1.8中,如果我們傳入的初始化容量為1,實際上設置的結果也是1。上面的代碼打印的結果為2的原因,是代碼中給map塞入值的操作導致了擴容,容量從1擴容到了2。事實上,在JDK1.7和JDK1.8中,HashMap初始化容量(capacity)的時機不同。在JDK1.8中,調用HashMap的構造函數定義HashMap的時候,就會進行容量的設定。而在JDK1.7中,要等到第一次put操作時才進行這一操作。

因此,當我們通過HashMap(int initialCapacity)設置初始容量的時候,HashMap並不一定會直接採用我們傳入的數值,而是經過計算,得到一個新值,目的是提高hash的效率。比如1->1、3->4、7->8和9->16。

HashMap中初始容量的合理值

通過上面的分析我們可以知道,當我們使用HashMap(int initialCapacity)來初始化容量的時候,JDK會默認幫我們計算一個相對合理的值當做初始容量。那麼,是不是我們只需要把已知的HashMap中即將存放的元素個數直接傳給initialCapacity就可以了呢?

initialCapacity = (需要存儲的元素個數 / 負載因子) + 1

這裏的負載因子就是loaderFactor,默認值為0.75。

initialCapacity = expectedSize / 0.75F + 1.0F

上面這個公式是《阿里巴巴Java開發手冊》中的一個建議,在Guava中也是提供了相同的算法,更甚之,這個算法實際上是JDK8中putAll()方法的實現。這是公式的得出是因為,當HashMap內部維護的哈希表的容量達到75%時(默認情況下),就會觸發rehash(重建hash表)操作。而rehash的過程是比較耗費時間的。所以初始化容量要設置成expectedSize/0.75 + 1的話,可以有效地減少衝突,也可以減小誤差。

總結

當我們想要在代碼中創建一個HashMap的時候,如果我們已知這個Map中即將存放的元素個數,給HashMap設置初始容量可以在一定程度上提升效率。

但是,JDK並不會直接拿用戶傳進來的数字當做默認容量,而是會進行一番運算,最終得到一個2的冪。而為了最大程度地避免擴容帶來的性能消耗,通常是建議可以把默認容量的数字設置成expectedSize / 0.75F + 1.0F。

在日常開發中,可以使用Guava提供的一個方法來創建一個HashMap,計算的過程Guava會幫我們完成。

Map<String, String> map = Maps.newHashMapWithExpectedSize(10);

最後要說的一點是,這種算法實際上是一種使用內存換取性能的做法,在真正的應用場景中要考慮到內存的影響。

 

“當你認真喜歡一個人的時候,你的全世界都是她。”

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站,提高曝光率!!

網頁設計一頭霧水??該從何著手呢? 找到專業技術的網頁設計公司,幫您輕鬆架站!

※想知道最厲害的台北網頁設計公司推薦台中網頁設計公司推薦專業設計師”嚨底家”!!