HashMap 是日常開闢中，用的最多的集 合類之一，也是口試中常常被問到的 Java 類之一。同時，HashMap 在實現方式上面又有十分代表的范例。不顧是從哪一方面來看，吸取 HashMap 都可以說是有利無害的。
解析 HashMap 的源碼的詞章在上面已經數不勝數了，本文另辟蹊徑來解析 HashMap 的設計思想。
**底層數據組織**
說到 HashMap 的數據庫，我們需求從兩個 JDK 版原來解析：JDK7 和 JDK8。
JDK7 版本的 HashMap 的數據組織為：數組 + 鏈表。而 JDK8 版本的 HashMap 的數據組織為： 數組 + 鏈表 + 紅黑樹。可以看到 7 和 8 中 HashMap 的底層數據組織最重要的區別即是 Java8 多了紅黑樹。
**何必是數組加鏈表？**
上文中說到了 不顧是 7 或者8 ，底層數據組織都是 數組 + 鏈表，但這又是為什麼呢？
數組是一個鏈式數據組織。put的時候，通過哈希函數將數據進行 哈希運算 之后，就得到數組的下標，這樣子就可以將數據保留在對應的槽中，這個槽在 HashMap 中被稱為 En try。在 get 時候，通過雷同的哈希函數，將 key 進行哈希運算，可以得到對應的下標，就可以快速找到該 key 對應的 value。這時候， get 的時間復雜度還是 O(1)。
但，哈希運算就避免不了有哈希沖突，也就說，差異的值通過哈希運算之后可能得到同一個值。在散列表的關連概念中，我們說了幾種解決哈希沖突的計劃，在 HashMap中，則是采用了鏈表法。
也即是說，發作了沖突之后，我們在En try中形成一個單鏈表。不過這里有存在了一玩運彩 評價個疑問，假如鏈表過長，檢索起來的效率同樣也會很低。于是，在 Java8 中，通過鏈表轉紅黑樹來解決這個疑問。
**何必要加上紅黑樹**
為什麼要鏈表轉紅黑樹，我們需求從數據組織來分析。
假如從一個無序單鏈表中檢索數據，我們只能重新到尾一個一個檢索，一旦數據量很大的場合下，檢索的效率就很低。這時，我們想到了紅黑樹，從目前的場合來看，紅黑樹能很好地解決這個疑問。
我們先來看看紅黑樹的定義：
紅黑樹是每個節點都帶有色彩屬性 的二叉查找樹，色彩為紅色或白色。在二叉查找樹強制通常要求以外，對于任何有效的紅黑樹我們提升了如下的額外要求：
– 節點是紅色或白色。根是白色。
– 所有葉子都是白色（葉子是NIL節點）。
– 每個紅色節點必要有兩個白色 的子節點。（從每個葉子到根的所有路徑上不可有兩個持續的紅色節點。）
– 從任一節點到其每個葉子的所有簡樸路徑都涵蓋雷同數量的白色節點。
紅黑樹
要是紅黑樹，首要得是二叉查找樹：
二叉查找樹（英語：Binary Search Tree），也稱為二叉搜索樹、有序二叉樹（ordered binary tree）或排列二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：
– 若任意節點的左子樹不空，則左子樹上所有節點的值均小于它的根節點的值；
– 若任意節點的右子樹不空，則右子樹上所有節點的值均大于或等于它的根節點的值；
– 任意節點的左、右子樹也差別為二叉查找樹；
簡樸做一個結算，紅黑樹的左節點要比父節點小，右節點要比父節點大。假如要檢索一個數字，可以將時間復雜度從 O(n) 減低到 O(logn)。
**當然了，增添了紅黑樹的數據組織之后，代碼實現要比 只用數組 + 鏈表要復雜了好幾倍。看代碼的時候簡直是不可再苦惱了。**
**什麼時候轉成紅黑樹，有什麼轉成鏈表**
在源碼中有這麼一個字段，static final int TREEIFY_THRESHOLD = 8;，見字知義，這個字段的意思鏈表轉紅黑樹的閾值，也即是 8。同樣的，還有這麼一個字段，static final int UN TREEIFY_THRESHOLD = 6;，它意思是紅黑樹轉鏈表的閾值。
為什麼是 8 呢？在源碼的注釋中也有辯白，英文翻譯過來即是下面的意思。
鏈表查詢的時間復雜度是 O (n)，紅黑樹的查詢復雜度是 O (log n)。在鏈表數據不多的時候，採用鏈表進行遍歷也對照快，只有當鏈表數據對照多的時候，才會幻化成紅黑樹，但紅黑樹需求的占用空間是鏈表的 2 倍，斟酌到幻化時間和空間損耗，所以我們需求定義出幻化的界限值。
在斟酌設計 8 這個值的時候，我們參考了泊松分布概率函數，由泊松分布中得出結論，鏈表各個長度的擲中概率為：
“`
* 0 0.60653066
* 1 0.30326533
* 2 0.07581633
* 3 0.01263606
* 4 0.00157952
* 5 0.00015795
* 6 0.00001316
* 7 0.000004
* 8 0.00000006
“`
意思是，當鏈表的長度是 8 的時候，顯露的概率是 0.00000006，不到萬萬分之一，所以說正常場合下，鏈表的長度不能能達到 8 ，而一旦達到 8 時，肯定是 hash 算法出了美國運彩疑問，所以在這種運彩 帳戶場合下，為了讓 HashMap 仍然有較高的查詢功能，所以讓鏈表幻化成紅黑樹，我們正常寫代碼，採用 HashMap 時，幾乎不會碰到鏈表幻化成紅黑樹的場合，終究概念只有萬萬分之一。
為什麼兩個閾值不一樣的，大家想想，假如一樣的，在鏈表白到8 的時候，會轉成紅黑樹，但紅黑樹轉鏈表的閾值也是8，這時候就會顯露輪迴轉換。
**鏈表轉紅黑樹還有一個前提，即是當數組容量大于 64 時，鏈表才會幻化成紅黑樹**
**擴容的前提**
在說擴容之前，先來說說 HashMap 在 7 和 8 中初始化時的差異體現。
在 Java 7 中，HashMap 初始化的時候，會有個默認容量 （16）。但在 Java8 中，HashMap 初始化的時候，默認容量為0，只有在第一次 put 的時候，才會擴容到 16。（實在 ArrayList 在 Java8 也是這麼體現的）。
在 HashMap 源碼中，有一個字段定義 static final float DEFAULT_LOAD_FACTOR = 0.75f;。運彩 股票這個字段的意思是，當HashMap 的長度 = HashMap 當前容量 * 0.75的時候，就會發作擴容。
關于為什麼負載因子是 0.75，我們可以在源碼注釋找到一定的答案。
load factor
大要意思即是說負載因子是0.75的時候，空間應用率對照高，並且避免了相當多的Hash沖突，使得底層的鏈表或者是紅黑樹的高度對照低，增加了空間效率。
HashMap的擴容是變成原本容量的 2 倍。
**Hash函數**
我們先來看看 Java 8 的 hash 函數。
“`
static final int hash(Object key) {
int h;
return (key == null) ? 0 (h = key.hashCode()) ^ (h >>> 16);
}
“`
這里的大約意思即是，先算計出 key 的 hashCode h。然后算計算計 h ^ (h >>> 16)。無符號右移16位。這麼做的優點是使多數配景下，算出來的 hash 值對照散開。
通常來說，hash 值算出來之后，要算計當前 key 在數組中的索引下標位置時，可以采用取模的方式，即是索引下標位置 = hash 值 數組大小，這樣做的優點，即是可以擔保算計出來的索引下標值可以均勻的分布在數組的各個索引位置上，但取模操縱對于處置器的算計是對照慢的，數學上有個公式，當 b 是 2 的冪次方時，a b = a 假如數組大小大于 64 時，鏈表就會幻化運彩 因雨延賽成紅黑樹。
這里不光僅判斷鏈表個數大于等于 8，還判斷了數組大小，數組容量小于 64 沒有當即幻化的來由，測度重要是由於紅黑樹占用的空間比鏈表大許多，幻化也對照耗時，所以數組容量小的場合下沖突嚴重，我們可以先嘗試擴容，看看可否通過擴容來解決沖突的疑問。
> 云棲號在線上課每日都有產物專業專家分享！
> 課程地址：syqh.aliyun.live
> 當即參加社群，與專家面臨面，及時了解課程最新動態！
> 云棲號在線上課 社群sc.tb.cnF3.Z8gvnK
原文發行時間：2024-07-08
本文作者：飛行的竹蜻蜓
本文來自：，了解關連信息可以注目掘金
