阿里P7崗位面試，面試官問我：為什么HashMap底層樹化標準的元素個數是8

前言

先宣告一下，本文有點標題黨了，像我這樣的菜雞何德何能去面試阿里的P7崗啊，不過，這確實是阿里p7級崗位的面試題，當然，參加面試的人不是我，而是我部門的一個大佬，他把自己的面試經驗分享給了我，也讓我間接體會下阿里級別的面試難度，這樣算起來，我也勉強算是經歷面試過阿里P7的崗位的人吧，頓時感覺信心暴漲，

一般的面試題

對于HashMap，我們再熟悉不過了，日常開發最常用的Java集合類就是它了，而且面試的時候對于HashMap知識點基本是必問的，就拿我之前的面試經歷來看，問的最多的無非是這么幾個：

1、HashMap的底層存盤結構是怎樣的啊？

2、執行緒安全嗎？為什么不安全？

3、1.7和1.8版本的HashMap有什么區別？1.7的有什么隱患，什么原因導致的？

4、hashcode是唯一的嗎？插入元素的時候怎么比較的？

5、跟HashTable，ConcurrentHashMap有什么區別？

對于這些問題，如果你看過一些博客，或者大概的瀏覽過原始碼的話，基本都能答出來，我之前參加過很多面試，也很少在HashMap這塊失過手，

事實證明，我還是年輕了點（怎么說也是90后的），有時候，你答的好不是因為你懂得多，而是人家問的不深，如果你沒有對原始碼做深入的了解和思考的話，別人稍微換個角度考察，你也許就會犯難了，

就好像標題上的題目，為什么HashMap鏈表樹化的標準是8個？說實話，盡管我之前也知道是樹化的閾值是8，但是為什么是這個數目我還真沒仔細的思考過，借著這個機會，我也重新梳理了遍HashMap的原始碼，本文也算是一些新的思考點的總結吧，

HashMap的基本知識點

HashMap可以說是Java專案里最常用的集合類了，作為一種典型的K-V存盤的資料結構，它的底層是由陣列 - 鏈表組成，當添加新元素時，它會根據元素的hash值找到對應的"桶"，也就是HashMap原始碼中Node<K, V> 里的元素，并插入到對應位置的鏈表中，鏈表元素個數過長時會轉化為紅黑樹(JDK1.8后的版本)，

為什么要轉成紅黑樹呢？

我們都知道，鏈表取元素是從頭結點一直遍歷到對應的結點，這個程序的復雜度是O(N) ，而紅黑樹基于二叉樹的結構，查找元素的復雜度為O(logN) ，所以，當元素個數過多時，用紅黑樹存盤可以提高搜索的效率，

既然紅黑樹的效率高，那怎么不一開始就用紅黑樹存盤呢？

這其實是基于空間和時間平衡的考慮，JDK的原始碼里已經對這個問題做了解釋：

* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins.  

看注釋里的前面四行就不難理解，單個 TreeNode 需要占用的空間大約是普通 Node 的兩倍，所以只有當包含足夠多的 Nodes 時才會轉成 TreeNodes，這個足夠多的標準就是由 TREEIFY_THRESHOLD 的值（默認值8）決定的，而當桶中節點數由于移除或者 resize (擴容) 變少后，紅黑樹會轉變為普通的鏈表，這個閾值是 UNTREEIFY_THRESHOLD（默認值6），

/**
* The bin count threshold for using a tree rather than list for a
* bin.  Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;

看到這里就不難明白了，紅黑樹雖然查詢效率比鏈表高，但是結點占用的空間大，只有達到一定的數目才有樹化的意義，這是基于時間和空間的平衡考慮，

為什么樹化標準是8個

至于為什么樹化標準的數量是8個，在原始碼中，上面那段筆記后面還有一段較長的注釋，我們可以從那一段注釋中找到答案，原文是這樣：

* usages with well-distributed user hashCodes, tree bins are
* rarely used.  Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 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
* more: less than 1 in ten million

大概意思就是：如果 hashCode的分布離散良好的話，那么紅黑樹是很少會被用到的，因為各個值都均勻分布，很少出現鏈表很長的情況，在理想情況下，鏈表長度符合泊松分布，各個長度的命中概率依次遞減，注釋中給我們展示了1-8長度的具體命中概率，當長度為8的時候，概率概率僅為0.00000006，這么小的概率，HashMap的紅黑樹轉換幾乎不會發生，因為我們日常使用不會存盤那么多的資料，你會存上千萬個資料到HashMap中嗎？

當然，這是理想的演算法，但不妨某些用戶使用HashMap程序導致hashCode分布離散很差的場景，這個時候再轉換為紅黑樹就是一種很好的退讓策略，

至于什么情況下會導致這樣的場景，大家可以自己思考或網上找一下答案，我就不再贅述了，省點力氣，

別，咱好好說話，我接著寫還不行嗎，不容易啊，被你們白嫖就算了，還要被冠上渣男的稱號，我圖啥呢？

首先說明一下，在HashMap中，決定某個物件落在哪一個 “桶“，是由該物件的hashCode決定的，JDK無法阻止用戶實作自己的哈希演算法，如果用戶重寫了hashCode，并且演算法實作比較差的話，就很可能會使HashMap的鏈表變得很長，就比如這樣：

public class HashMapTest {
    public static void main(String[] args) {
        Map<User, Integer> map = new HashMap<>();
        for (int i = 0; i < 1000; i++) {
            map.put(new User("鄙人薛某" + i), i);
        }
    }

    static class User{

        private String name;

        public User(String name) {
            this.name = name;
        }

        @Override
        public int hashCode() {
            return 1;
        }
    }
}

我們設計了一個hashCode永遠為1的類User，這樣一來存盤到HashMap的所有User物件都會存放到同一個“桶”里，這樣一來查詢效率無疑會非常的低下，而這也是HashMap設計鏈表轉紅黑樹的原因，可以有效防止用戶自己實作了不好的哈希演算法時導致鏈表過長的情況，

hash方法

說到哈希演算法，我們再來擴充一個知識點，這也是我覺得HashMap中非常牛逼的設計之一，

在HashMap的原始碼中，存盤物件hashCode的計算是由hash() 方法決定的，hash() 是HashMap 中的核心函式，在存盤資料時，將key傳入中進行運算，得出key的哈希值，通過這個哈希值運算才能獲取key應該放置在 “桶” 的哪個位置，下面是方法的原始碼：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

從代碼中可以看出，傳入key之后，hash() 會獲取key的hashCode進行無符號右移 16 位，然后進行按位異或，并把運算后的值回傳，這個值就是key的哈希值，這樣運算是為了減少碰撞沖突，因為大部分元素的hashCode在低位是相同的，不做處理的話很容易造成沖突，

除了做16位位移的處理，在添加元素的方法中，HashMap還把該hash值與table.length - 1，也就是“桶”陣列的大小做與運算，得到的結果就是對應的“桶”陣列的下標，從而找到該元素所屬的鏈表，原始碼里這樣的：

// n的值是table.length
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

當查找不到對應的索引時，就會新建一個新的結點作為鏈表的頭結點，那么這里為什么要用 i = (n - 1) & hash 作為索引運算呢？

這其實是一種優化手段，由于陣列的大小永遠是一個2次冪，在擴容之后，一個元素的新索引要么是在原位置，要么就是在原位置加上擴容前的容量，這個方法的巧妙之處全在于&運算，之前提到過&運算只會關注n – 1（n =陣列長度）的有效位，當擴容之后，n的有效位相比之前會多增加一位（n會變成之前的二倍，所以確保陣列長度永遠是2次冪很重要），然后只需要判斷hash在新增的有效位的位置是0還是1就可以算出新的索引位置，如果是0，那么索引沒有發生變化，如果是1，索引就為原索引加上擴容前的容量，

用一張效果圖來表示就是：

通過位運算，在每次擴容時都不用重新計算hash，省去了不少時間，而且新增有效位是0還是1是帶有隨機性的，之前兩個碰撞的Entry又有可能在擴容時再次均勻地散布開，達到較好的分布離散效果，不得不感嘆，設計功底真是太牛逼了，幾句看似簡單的代碼里面居然包含了這么多的學問，

為什么退化為鏈表的閾值是6

上面說到，當鏈表長度達到閾值8的時候會轉為紅黑樹，但是紅黑樹退化為鏈表的閾值卻是6，為什么不是小于8就退化呢？比如說7的時候就退化，偏偏要小于或等于6？

主要是一個過渡，避免鏈表和紅黑樹之間頻繁的轉換，如果閾值是7的話，洗掉一個元素紅黑樹就必須退化為鏈表，增加一個元素就必須樹化，來回不斷的轉換結構無疑會降低性能，所以閾值才不設定的那么臨界，

最后

HashMap的知識點還有很多，這里我也強烈大家去多看幾遍原始碼，不光是為了應付面試，也是對自己能如何更好的使用HashMap能有更清晰的認知，畢竟它實在是太常見了，用的不好很容易就產生bug，而且，我覺得JDK的原始碼真的有很多值得我們開發者深入研究的地方，就比如這個HashMap，它的真實代碼量不算多，但非常的高效，最重要的是，它每個版本都在不停的優化，每一行代碼都是精雕細琢，看原始碼的時候我也一直在心里感嘆，我要是也能寫出那么牛逼的代碼，那進阿里什么的還算是事嗎？

我是鄙人薛某，一個不拘于技術的互聯網人，想看更多精彩文章可以關注我的公眾號，里面不僅有技術，還有有趣的吹水文哦~~~

原創不易，看官們的【三連】將是我創作的最大動力，感謝各位的支持！

本文使用 mdnice 排版