天天看點
傳回

Java1.8 HashMap源碼分析

一、HashMap的特點

    HashMap是基于hash算法+數組+連結清單+紅黑樹實作的，重要性逐漸提高

    1、hash算法就是将任意長度的值通過算法轉換成固定長度的值

    2、數組最大的優點就是随機通路的時間複雜度為O(1)，得到hash算法轉換後的值（下标），那麼就能實作時間複雜度為O(1)的查詢功能。

    3、O(1)的時間複雜度是建立在最理想的hash算法之上的，再好的hash算法也會存在哈希沖突，為了解決hash沖突同時滿足新增、修改、删除、擴容等高性能需求，那麼連結清單就閃亮登場了（至于為什麼不直接使用紅黑樹，可檢視細節中3）

    4、連結清單最大的缺點就是查詢的時間複雜度為O(n)，如果hash算法太差，或者其他原因（例如Hash Collision Dos攻擊）導緻hash沖突嚴重，查詢性能急速下降，在Java1.7版本會導緻CPU飙升，是以Java1.8使用了紅黑樹來解決長連結清單的查詢性能問題，此時時間複雜度從O(n)下降至O(logN)

    總結：從上述可看出，hash算法決定了HashMap的性能高低，是以官方每次對HashMap的優化無非就是一方面提高hash算法的分散性（越分散，碰撞率越低，空間使用率就越高），一方面盡可能地提升hash算法極差時的穩定性（使用了連結清單、紅黑樹和擴容來保證），簡單一句話就是提高HashMap的下限和上限，那麼整體的性能就能提升了。

    提示：HashMap和ArrayList作為容器中兩大殺器，使用率基本是極高極高的，每一點點的性能提升都是值得追求的，那麼下面我們看看HashMap的細節之處，究竟是如何提高HashMap的性能的。

二、HashMap細節

    1、擾動函數hash(key)

        Java1.8對Java1.7做了優化，将多次位運算減到一次位運算 和一次異或運算，也就 是高低位異或，提高分散性，降低hash碰撞率

        可參考知乎：JDK 源碼中 HashMap 的 hash 方法原理是什麼？

    2、treeifyBin方法中如果容量小于64直接擴容

/**
 * 擴容,因為hash沖突嚴重(大于1/3)
 * 1、tab.length為32時，threshold=24(負載因子=0.75)
 * 2、單個bucket的連結清單長度已經達到9了(大于8才轉樹形結構)
 * 碰撞率>=8/24,碰撞率已經很嚴重了,直接擴容
 */
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
   resize();

    3、連結清單長度大于8(包括添加節點)時轉紅黑樹

        受幾個因素影響：

        ①樹節點TreeNode比Node大很多（TreeNode繼承LinkedHashMap.Entry繼承 Node，一個Entry有兩個Entry引用8個位元組，一個TreeNode有4個TreeNode引用16個位元組，1個布爾值1個位元組，而Node為8+4+4+4=20個位元組，兩者比例為45:20）

        ②連結清單查詢的平均時間複雜度為O(n)，而紅黑樹的為O(logN)

        ③對于增删改，紅黑樹需要考慮保持平衡的性能消耗（旋轉）

        ④根據Poisson distribution（泊松分布），達到8的連結清單長度機率幾乎為0

        ⑤如果門檻值太小，退化為連結清單時就會存在頻繁的樹化和退化的情況

    4、擴容後紅黑樹節點小于等于6時退化為連結清單

        确定樹化門檻值為8後，退化的門檻值就相對好确定了：

        ①比樹化門檻值小是為了緩沖上面⑤的情況

    5、擴容函數

        ①最大容量為2^30

if (oldCap >= MAXIMUM_CAPACITY) {
    /**
     * threshold變成MAX_VALUE(2^31-1),随它們碰撞,但是oldCap不改變。
     * 為什麼不擴容了呢？--> 為什麼capacity擴容都是擴大一倍并且是2的幂次方呢？
     * 這裡涉及到擴容中的邏輯e.hash & (oldCap - 1) 跟空間使用率
     * 假如當容量擴容到最大值MAX_VALUE(2^31-1)時,轉換成二進制
     *            hash
     *      &
     *            0111 1111 1111 1111 1111 1111 1111 1110
     * ---------------------------------------------------
     *            xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxx0
     * 從上面可看出無論hash最低位是0或者1,結果的最低位都為0,也就是下标隻有2^30個位置被使用,有
     * 2^30-1個下标沒有被使用
     * 是以當容量為MAX_VALUE(2^31-1)時會造成一半的空間浪費,效率等同于未擴容前的
     * MAXIMUM_CAPACITY(2^30)
     * 總結：如果capacity擴容後的容量不是2的幂次方，空間使用率最高不超過50%
     */
    threshold = Integer.MAX_VALUE;
    return oldTab;
}

        ②容量大于等于16的擴容不重新計算threshold

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
    /**
     * 為什麼需要判斷oldCap >= DEFAULT_INITIAL_CAPACITY呢？
     * (這問題類似于數組下标為什麼從0開始？cpu計算數組位址公式baseAddress+n*typeSize和
     * baseAddress+(n-1)*typeSize為了省去cpu計算n-1的指令)
     * 當容量capacity較小時 threshold=capacity * loadFactor 造成的誤差比較大,
     * 例如初始化容量為capacity=2 * loadFactor=0.75 threshold=1,如果每次擴容threshold都翻倍,
     * 第二次：threshold=2
     * 第三次：threshold=4
     * ....
     * 那麼誤差就越來越大了，是以為了降低誤差，容量較小時還是需要重新計算threshold
     * 為什麼隻小于16呢？
     * 個人猜測是在每次擴容都計算newThr和用位運算翻倍之間做權衡
     * 因為loadFactor預設值為0.75,當capacity>=4的時候，當capacity*loadFactor是沒有小數的，
     * 是以threshold是沒有誤差的，是以如果需要設定loadFactor，
     * 最好是使得capacity（1,2,4,8）*loadFactor=整數
     * 如果 loadFactor=0.6 初始化容量capacity=8  則threshold=4
     * 下次擴容：threshold=8 capacity=16 由于capacity>=16的時候不會再次計算threshold
     * 是以，這個時候loadFactor相當于從0.6降低到了0.5
     */
    newThr = oldThr << 1; // double threshold

        ③擴容後位置，1.8根據hash值對應的最高位決定

if (e.next == null)
    /**
     * e.hash & (newCap - 1) 重點，要考！
     * newCap - 1 ：最高位1到最低位全是1，因為容量是2的幂次方
     * newCap = oldCap*2
     * 節點在oldTab中的下标為：e.hash & (oldCap - 1)
     * 節點在newCap中的下标為：e.hash & (oldCap*2 - 1)
     * 那麼(oldCap - 1) 與(oldCap*2 - 1) 的差别就是在最高位的差别，後者比前者多一位最高位1
     * 例如32 -1 與64-1 換成二進制就明顯了
     * 那麼最終的下标就在于e.hash 對應 (oldCap*2 - 1)或者(newCap - 1) 最高位的bit是0或1了
     * 轉化為：e.hash & oldCap
     * 0下标不變，1下标=原下标+oldCap
     * 這麼做有什麼好處？
     * 1、1.7版本rehash性能低，比位運算差多了
     * 2、把原來碰撞的節點又散列了一次（非常重要，減低沖突是hash算法的畢生使命）
     */
    newTab[e.hash & (newCap - 1)] = e;

          ④疑問，put方法，第一個if和else為什麼不合并？

           個人覺得這解析還是比較牽強，如果有其他思路請給我留言，謝謝！

/**
 * 為什麼不跟下面的else合并？先判斷第一個連結清單元素，下面else再循環周遊連結清單？
 * Poisson distribution（泊松分布）http://en.wikipedia.org/wiki/Poisson_distribution
 * 也可參考ConcurrentHashMap中的Overview，下面就是桶中元素個數的機率：
 *  0:    0.60653066
 *  1:    0.30326533
 *  2:    0.07581633
 *  3:    0.01263606
 *  4:    0.00157952
 *  5:    0.00015795
 *  6:    0.00001316
 *  7:    0.00000094
 *  8:    0.00000006
 * 進入此分支代碼時，說明p要麼是連結清單，要麼是樹形結構，按照上面的機率來說，桶中隻有一個元素的機率為0.3/(1-0.61)=77.69%
 * 根據此結論，多幾行代碼或許能提升一點性能，還是可以接受的
 */
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;
else if (p instanceof TreeNode)
    // 樹結構
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
    // 周遊節點
    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);
            // binCount從0開始，是以-1，大于8個才轉樹結構(上面的if也需要算)
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }
}

           總結：雖然平時開發不用太刻意去追求一點點性能（建議不要犧牲可讀性去追求一點點性能），但是這些思路還是很值得學習的

java基礎 hashmap 集合 容器
上一篇: HashMap簡略源碼解析
下一篇: HashMap源碼分析（2）HashMap源碼分析（2）

繼續閱讀