HashMap 是日常開發(fā)中，用的最多的集 合類之一，也是面試中經(jīng)常被問到的 Java 類之一。同時，HashMap 在實(shí)現(xiàn)方式上面又有十分典型的范例。不管是從哪一方面來看，學(xué)習(xí) HashMap 都可以說是有利無害的。 分析 HashMap 的源碼的文章在網(wǎng)上面已經(jīng)數(shù)不勝數(shù)了，本文另辟蹊徑來分析 HashMap 的設(shè)計思想。 **底層數(shù)據(jù)結(jié)構(gòu)** 說到 HashMap 的數(shù)據(jù)庫，我們需要從兩個 JDK 版本來分析：JDK7 和 JDK8。 JDK7 版本的 HashMap 的數(shù)據(jù)結(jié)構(gòu)為：數(shù)組 + 鏈表。而 JDK8 版本的 HashMap 的數(shù)據(jù)結(jié)構(gòu)為： 數(shù)組 + 鏈表 + 紅黑樹?？梢钥吹?7 和 8 中 HashMap 的底層數(shù)據(jù)結(jié)構(gòu)最主要的區(qū)別就是 Java8 多了紅黑樹。 **為何是數(shù)組加鏈表？** 上文中說到了 不管是 7 或者8 ，底層數(shù)據(jù)結(jié)構(gòu)都是 數(shù)組 + 鏈表，但這又是為什么呢？ 數(shù)組是一個鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)。put的時候，通過哈希函數(shù)將數(shù)據(jù)進(jìn)行 哈希運(yùn)算 之后，就得到數(shù)組的下標(biāo)，這樣子就可以將數(shù)據(jù)保存在對應(yīng)的槽中，這個槽在 HashMap 中被稱為 En try。在 get 時候，通過相同的哈希函數(shù)，將 key 進(jìn)行哈希運(yùn)算，可以得到對應(yīng)的下標(biāo)，就可以快速找到該 key 對應(yīng)的 value。這時候， get 的時間復(fù)雜度還是 O(1)。 但，哈希運(yùn)算就避免不了有哈希沖突，也就說，不同的值通過哈希運(yùn)算之后可能得到同一個值。在散列表的相關(guān)概念中，我們說了幾種解決哈希沖突的方案，在 HashMap中，則是采用了鏈表法。 也就是說，發(fā)生了沖突之后，我們在En try中形成一個單鏈表。但是這里有存在了一個問題，如果鏈表過長，檢索起來的效率同樣也會很低。于是，在 Java8 中，通過鏈表轉(zhuǎn)紅黑樹來解決這個問題。 **為何要加上紅黑樹** 為什么要鏈表轉(zhuǎn)紅黑樹，我們需要從數(shù)據(jù)結(jié)構(gòu)來解析。 如果從一個無序單鏈表中檢索數(shù)據(jù)，我們只能從頭到尾一個一個檢索，一旦數(shù)據(jù)量很大的情況下，檢索的效率就很低。這時，我們想到了紅黑樹，從目前的情況來看，紅黑樹能很好地解決這個問題。 我們先來看看紅黑樹的定義： 紅黑樹是每個節(jié)點(diǎn)都帶有顏色屬性 的二叉查找樹，顏色為紅色或黑色。在二叉查找樹強(qiáng)制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求： - 節(jié)點(diǎn)是紅色或黑色。根是黑色。 - 所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）。 - 每個紅色節(jié)點(diǎn)必須有兩個黑色 的子節(jié)點(diǎn)。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點(diǎn)。） - 從任一節(jié)點(diǎn)到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。 紅黑樹 要是紅黑樹，首先得是二叉查找樹： 二叉查找樹（英語：Binary Search Tree），也稱為二叉搜索樹、有序二叉樹（ordered binary tree）或排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質(zhì)的二叉樹： - 若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值； - 若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于或等于它的根節(jié)點(diǎn)的值； - 任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹； 簡單做一個總結(jié)，紅黑樹的左節(jié)點(diǎn)要比父節(jié)點(diǎn)小，右節(jié)點(diǎn)要比父節(jié)點(diǎn)大。如果要檢索一個數(shù)字，可以將時間復(fù)雜度從 O(n) 降低到 O(logn)。 **當(dāng)然了，添加了紅黑樹的數(shù)據(jù)結(jié)構(gòu)之后，代碼實(shí)現(xiàn)要比 只用數(shù)組 + 鏈表要復(fù)雜了好幾倍。看代碼的時候簡直是不能再痛苦了。** **什么時候轉(zhuǎn)成紅黑樹，有什么轉(zhuǎn)成鏈表** 在源碼中有這么一個字段，static final int TREEIFY_THRESHOLD = 8;，見字知義，這個字段的意思鏈表轉(zhuǎn)紅黑樹的閾值，也就是 8。同樣的，還有這么一個字段，static final int UN TREEIFY_THRESHOLD = 6;，它意思是紅黑樹轉(zhuǎn)鏈表的閾值。 為什么是 8 呢？在源碼的注釋中也有解釋，英文翻譯過來就是下面的意思。 鏈表查詢的時間復(fù)雜度是 O (n)，紅黑樹的查詢復(fù)雜度是 O (log n)。在鏈表數(shù)據(jù)不多的時候，使用鏈表進(jìn)行遍歷也比較快，只有當(dāng)鏈表數(shù)據(jù)比較多的時候，才會轉(zhuǎn)化成紅黑樹，但紅黑樹需要的占用空間是鏈表的 2 倍，考慮到轉(zhuǎn)化時間和空間損耗，所以我們需要定義出轉(zhuǎn)化的邊界值。 在考慮設(shè)計 8 這個值的時候，我們參考了泊松分布概率函數(shù)，由泊松分布中得出結(jié)論，鏈表各個長度的命中概率為： ``` * 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 ``` 意思是，當(dāng)鏈表的長度是 8 的時候，出現(xiàn)的概率是 0.00000006，不到千萬分之一，所以說正常情況下，鏈表的長度不可能到達(dá) 8 ，而一旦到達(dá) 8 時，肯定是 hash 算法出了問題，所以在這種情況下，為了讓 HashMap 仍然有較高的查詢性能，所以讓鏈表轉(zhuǎn)化成紅黑樹，我們正常寫代碼，使用 HashMap 時，幾乎不會碰到鏈表轉(zhuǎn)化成紅黑樹的情況，畢竟概念只有千萬分之一。 為什么兩個閾值不一樣的，大家想想，如果一樣的，在鏈表達(dá)到8 的時候，會轉(zhuǎn)成紅黑樹，但紅黑樹轉(zhuǎn)鏈表的閾值也是8，這時候就會出現(xiàn)循環(huán)轉(zhuǎn)換。 **鏈表轉(zhuǎn)紅黑樹還有一個條件，就是當(dāng)數(shù)組容量大于 64 時，鏈表才會轉(zhuǎn)化成紅黑樹** **擴(kuò)容的條件** 在說擴(kuò)容之前，先來說說 HashMap 在 7 和 8 中初始化時的不同表現(xiàn)。 在 Java 7 中，HashMap 初始化的時候，會有個默認(rèn)容量 （16）。但在 Java8 中，HashMap 初始化的時候，默認(rèn)容量為0，只有在第一次 put 的時候，才會擴(kuò)容到 16。（其實(shí) ArrayList 在 Java8 也是這么表現(xiàn)的）。 在 HashMap 源碼中，有一個字段定義 static final float DEFAULT_LOAD_FACTOR = 0.75f;。這個字段的意思是，當(dāng)HashMap 的長度 = HashMap 當(dāng)前容量 * 0.75的時候，就會發(fā)生擴(kuò)容。 關(guān)于為什么負(fù)載因子是 0.75，我們可以在源碼注釋找到一定的答案。 load factor 大致意思就是說負(fù)載因子是0.75的時候，空間利用率比較高，而且避免了相當(dāng)多的Hash沖突，使得底層的鏈表或者是紅黑樹的高度比較低，提升了空間效率。 HashMap的擴(kuò)容是變成原先容量的 2 倍。 **Hash函數(shù)** 我們先來看看 Java 8 的 hash 函數(shù)。 ``` static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` 這里的大概意思就是，先計算出 key 的 hashCode h。然后計算計算 h ^ (h >>> 16)。無符號右移16位。這么做的好處是使大多數(shù)場景下，算出來的 hash 值比較分散。 一般來說，hash 值算出來之后，要計算當(dāng)前 key 在數(shù)組中的索引下標(biāo)位置時，可以采用取模的方式，就是索引下標(biāo)位置 = hash 值 % 數(shù)組大小，這樣做的好處，就是可以保證計算出來的索引下標(biāo)值可以均勻的分布在數(shù)組的各個索引位置上，但取模操作對于處理器的計算是比較慢的，數(shù)學(xué)上有個公式，當(dāng) b 是 2 的冪次方時，a % b = a &（b-1），所以此處索引位置的計算公式我們可以更換為： (n-1) & hash。 此問題可以延伸出三個小問題： **1：為什么不用 key % 數(shù)組大小，而是需要用 key 的 hash 值 % 數(shù)組大小。** 答：如果 key 是數(shù)字，直接用 key % 數(shù)組大小是完全沒有問題的，但我們的 key 還有可能是字符串，是復(fù)雜對象，這時候用 字符串或復(fù)雜對象 % 數(shù)組大小是不行的，所以需要先計算出 key 的 hash 值。 **2：計算 hash 值時，為什么需要右移 16 位？** 答：hash 算法是 h ^ (h >>> 16)，為了使計算出的 hash 值更分散，所以選擇先將 h 無符號右移 16 位，然后再于 h 異或時，就能達(dá)到 h 的高 16 位和低 16 位都能參與計算，減少了碰撞的可能性。 **3：為什么把取模操作換成了 & 操作？** 答：key.hashCode() 算出來的 hash 值還不是數(shù)組的索引下標(biāo)，為了隨機(jī)的計算出索引的下表位置，我們還會用 hash 值和數(shù)組大小進(jìn)行取模，這樣子計算出來的索引下標(biāo)比較均勻分布。 取模操作處理器計算比較慢，處理器對 & 操作就比較擅長，換成了 & 操作，是有數(shù)學(xué)上證明的支撐，為了提高了處理器處理的速度。 **hash 沖突時怎么辦？** hash 沖突指的是 key 值的 hashcode 計算相同，但 key 值不同的情況。 - 如果桶中元素原本只有一個或已經(jīng)是鏈表了，新增元素直接追加到鏈表尾部； - 如果桶中元素已經(jīng)是鏈表，并且鏈表個數(shù)大于等于 8 時，此時有兩種情況： 如果此時數(shù)組大小小于 64，數(shù)組再次擴(kuò)容，鏈表不會轉(zhuǎn)化成紅黑樹;如果數(shù)組大小大于 64 時，鏈表就會轉(zhuǎn)化成紅黑樹。 這里不僅僅判斷鏈表個數(shù)大于等于 8，還判斷了數(shù)組大小，數(shù)組容量小于 64 沒有立即轉(zhuǎn)化的原因，猜測主要是因?yàn)榧t黑樹占用的空間比鏈表大很多，轉(zhuǎn)化也比較耗時，所以數(shù)組容量小的情況下沖突嚴(yán)重，我們可以先嘗試擴(kuò)容，看看能否通過擴(kuò)容來解決沖突的問題。 > 【云棲號在線課堂】每天都有產(chǎn)品技術(shù)專家分享！ > 課程地址：https://yqh.aliyun.com/live > 立即加入社群，與專家面對面，及時了解課程最新動態(tài)！ > 【云棲號在線課堂 社群】https://c.tb.cn/F3.Z8gvnK 原文發(fā)布時間：2020-07-08 本文作者：飛翔的竹蜻蜓 本文來自：“”，了解相關(guān)信息可以關(guān)注“掘金”