摘要：在二叉查找樹強(qiáng)制一般要求以外，對(duì)于任何有效的紅黑樹增加了如下的額外要求節(jié)點(diǎn)是紅色或黑色。紅黑樹有哪些應(yīng)用場(chǎng)景內(nèi)核和系統(tǒng)調(diào)用實(shí)現(xiàn)中使用的完全公平調(diào)度程序使用紅黑樹。

這篇文章是記錄自己分析 Java 8 的 HashMap 源碼時(shí)遇到的疑問和總結(jié)，在分析的過程中筆者把遇到的問題都記錄下來，然后逐一擊破，如果有錯(cuò)誤的地方，希望讀者可以指正，筆者感激不盡。

什么是 initial capacity);

The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.

initial capacity 指定了 HashMap 內(nèi)部的 hash table 的初始化容量，可以通過構(gòu)造函數(shù)指定，默認(rèn)的初始化容量為 16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

什么是 load factor);

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.  When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

可以看到 load factor 是用于確定 hash table 何時(shí)擴(kuò)容的重要參數(shù)之一。

為什么 initial capacity 太高或 load factor 太低會(huì)影響性能？

Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings).  Thus, its very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor.  The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.  The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.  When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

查看源碼描述

描述主要提到三個(gè)問題：

initial capacity 和 load factor 是重要的性能參數(shù)。

設(shè)置不當(dāng)會(huì)影響迭代性能（如果迭代性能很重要的話）

設(shè)置不當(dāng)會(huì)導(dǎo)致頻繁的 rehash（伴隨 hash table 的 rebuild，并且 hash table 的容量會(huì)成倍增加）

合理的 initial capacity 是多少？

筆者經(jīng)過一番測(cè)試，在 hash 均勻分布的前提下，數(shù)據(jù)量從 100 ~ 千萬級(jí)，initial capacity 設(shè)置從 1 到千萬不等，發(fā)現(xiàn)這個(gè)值的大小對(duì)迭代性能和 rehash 的影響不是很大（到千萬級(jí)別才會(huì)有稍微明顯的效率問題），原因是擴(kuò)容時(shí)，每次都會(huì) double threshold，有效避免了高頻率的擴(kuò)容動(dòng)作；對(duì)迭代性能的影響也非常低（10W數(shù)據(jù)，1億初始容量，毫秒級(jí)別影響）。

合理的 load factor 是多少？

默認(rèn) 0.75 即可，太低可能會(huì)導(dǎo)致頻繁的擴(kuò)容，并且有可能導(dǎo)致 java.lang.OutOfMemoryError: Java heap space

什么時(shí)候會(huì)發(fā)生 resize？

When 
putting data && (hashtable.length == 0 || entries.length >= threshold)

Then 
resize()

什么時(shí)候會(huì)發(fā)生 rehashed？

觸發(fā) resize 的時(shí)候，會(huì)發(fā)生一次擴(kuò)容，并隨 rehash。

為什么需要 rehashed？

擴(kuò)容時(shí)會(huì)重建 hash table，由于新 hash table 的容量 = 舊 hash table 容量左移一位，因此需要 rehash，以確保新的 hash 落在 [0, new_capacity) 區(qū)間內(nèi)。

如何確保 hash 落入 [0, capacity) 區(qū)間？

(capacity - 1) & (hashcode ^ (hashcode >>> 16))

capacity 取值范圍： 2^(N+) - 1，0 < (N+) < 31。

在 hashCode 均勻分布的前提下（Object.hashCode() 默認(rèn)為每個(gè)對(duì)象生成不同的 hash code，具體原理可以看 java doc），hashcode ^ (hashcode >>> 16) 可以降低 hash 沖突的幾率（相對(duì)于 (capacity - 1) & hashcode），原理是混合原始哈希碼的高位和低位，以此來加大低位的隨機(jī)性；(capacity - 1) & new_hash 可以保證計(jì)算出來的 index 落入 [0, capacity)。

為什么擴(kuò)容后是原來的 2 倍，而不是 1.5 倍？3 倍？4 倍？

擴(kuò)容原來的 2 倍可以讓 rehash 的值更加穩(wěn)定，整體的 hash 值均勻分散。

減少不必要的擴(kuò)容空間（影響迭代性能）。

如何模擬 hash 碰撞？

通過覆寫 Object##hashCode()方法即可自定義 hashCode，就可以模擬 hash 碰撞，例如隨機(jī) hashCode 或固定 hashCode。

什么時(shí)候 HashMap 會(huì)采用紅黑樹保存節(jié)點(diǎn)數(shù)據(jù)？

Given
TREEIFY_THRESHOLD = 8

When
hashCount >= TREEIFY_THRESHOLD

Then 
treeifyBin(bin)

當(dāng)出現(xiàn)同一個(gè) hash 達(dá)到 8 次碰撞，就會(huì)從鏈表轉(zhuǎn)換成紅黑樹。

什么是 hash table

hash table 本質(zhì)上是一個(gè)數(shù)組 + 鏈表或紅黑樹的數(shù)據(jù)結(jié)構(gòu)， hash table 通過建立 hash 到數(shù)據(jù)節(jié)點(diǎn)的映射關(guān)系，巧妙的達(dá)成 O(1) 的檢索效率。其中每個(gè)鏈表保存著 hash 沖突(key 不相等，hash 值相等)的數(shù)據(jù)項(xiàng)，默認(rèn)情況下，當(dāng)達(dá)到 8 個(gè)沖突時(shí)，鏈表就會(huì)轉(zhuǎn)換成紅黑樹，轉(zhuǎn)換之后還伴隨著 O(n) -> O(log n) 的效率提升，不過這種情況出現(xiàn)的概率很低（在分散的 hash code 的前提下，相同的 hash 值產(chǎn)生 8 次沖突的概率僅為千萬分之 6），不過可以通過人為模擬重現(xiàn)這種情況。

什么情況下，HashMap 的效率最差？

頻繁的 hash 沖突是導(dǎo)致 HashMap 性能下降的罪魁禍?zhǔn)祝?dāng)同一個(gè) hash 值沖突達(dá)到 8 次及以上時(shí)， 此時(shí) rbtree 可能需要經(jīng)常通過左旋、右旋和著色來保持自身平衡，這個(gè)代價(jià)之大跟同一個(gè) hash 值的沖突次數(shù)成正比，因此需要維護(hù)好重寫的 hashCode 方法，使 hash code 盡可能分散。

為什么采用 RBTree 替代 LinkedList 來保存 hash 沖突的的節(jié)點(diǎn)？

用于提高哈希沖突條件下的性能，同時(shí)去除了以前版本遺留下來的問題，具體可以看這里 openjdk.java.net/jeps/180

什么是紅黑樹？

紅黑樹（英語：Red–black tree）是一種自平衡二叉查找樹，是在計(jì)算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。它在1972年由魯?shù)婪颉へ悹柊l(fā)明，被稱為"對(duì)稱二叉B樹"，它現(xiàn)代的名字源于Leo J. Guibas和Robert Sedgewick于1978年寫的一篇論文。紅黑樹的結(jié)構(gòu)復(fù)雜，但它的操作有著良好的最壞情況運(yùn)行時(shí)間，并且在實(shí)踐中高效：它可以在 O(log n)時(shí)間內(nèi)完成查找，插入和刪除，這里的 n 是樹中元素的數(shù)目。

上面是維基百科中的定義，同時(shí)紅黑樹還有 5 個(gè)性質(zhì)，紅黑樹是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色。在二叉查找樹強(qiáng)制一般要求以外，對(duì)于任何有效的紅黑樹增加了如下的額外要求：

節(jié)點(diǎn)是紅色或黑色。

根是黑色。

所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）。

每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。）

從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

紅黑樹適合哪些應(yīng)用場(chǎng)景？

時(shí)間敏感型程序。

紅黑樹有哪些應(yīng)用場(chǎng)景？

Linux 內(nèi)核和 epoll 系統(tǒng)調(diào)用實(shí)現(xiàn)中使用的完全公平調(diào)度程序使用紅黑樹。

什么是 fail-fast？

HashMap 通過這個(gè)機(jī)制確保迭代時(shí)，如果修改 map 的結(jié)構(gòu)（增，刪），一經(jīng)發(fā)現(xiàn)則立即拋出 ConcurrentModificationException，而不是等到未來的某個(gè)時(shí)刻再通知異常，可以通過這個(gè)機(jī)制來捕獲程序的一些 BUG.

可以通過什么方式使 HashMap 線程安全.

在 HashMap 之上包裝多一層，并且使用 synchronized 同步鎖鎖定 HashMap 實(shí)例的所有公開接口，Collections#synchronizedMap 已經(jīng)提供了這樣一種實(shí)現(xiàn)。

通過閱讀源碼、查閱資料和動(dòng)手驗(yàn)證，才知道 HashMap 的知識(shí)點(diǎn)那么多，不過都啃得差不多之后，就會(huì)覺得知識(shí)點(diǎn)很少（應(yīng)該還有遺漏掉的或者不嚴(yán)謹(jǐn)?shù)那闆r），確實(shí)讓自己學(xué)到了很多之前不知道的知識(shí)點(diǎn)。

在接下來的文章中，筆者會(huì)通過 TDD （測(cè)試驅(qū)動(dòng)開發(fā)）來記錄如何實(shí)現(xiàn)一個(gè)精簡版的 HashMap，避免一看就會(huì)，一做就廢的尷尬局面。