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

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

什么是 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ù)指定，默認的初始化容量為 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ù)之一。

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

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, it"s 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.

查看源碼描述

描述主要提到三個問題：

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

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

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

合理的 initial capacity 是多少？

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

合理的 load factor 是多少？

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

什么時候會發(fā)生 resize？

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

Then 
resize()

什么時候會發(fā)生 rehashed？

觸發(fā) resize 的時候，會發(fā)生一次擴容，并隨 rehash。

為什么需要 rehashed？

擴容時會重建 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() 默認為每個對象生成不同的 hash code，具體原理可以看 java doc），hashcode ^ (hashcode >>> 16) 可以降低 hash 沖突的幾率（相對于 (capacity - 1) & hashcode），原理是混合原始哈希碼的高位和低位，以此來加大低位的隨機性；(capacity - 1) & new_hash 可以保證計算出來的 index 落入 [0, capacity)。

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

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

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

如何模擬 hash 碰撞？

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

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

Given
TREEIFY_THRESHOLD = 8

When
hashCount >= TREEIFY_THRESHOLD

Then 
treeifyBin(bin)

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

什么是 hash table

hash table 本質(zhì)上是一個數(shù)組 + 鏈表或紅黑樹的數(shù)據(jù)結(jié)構(gòu)， hash table 通過建立 hash 到數(shù)據(jù)節(jié)點的映射關(guān)系，巧妙的達成 O(1) 的檢索效率。其中每個鏈表保存著 hash 沖突(key 不相等，hash 值相等)的數(shù)據(jù)項，默認情況下，當達到 8 個沖突時，鏈表就會轉(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 性能下降的罪魁禍首，當同一個 hash 值沖突達到 8 次及以上時， 此時 rbtree 可能需要經(jīng)常通過左旋、右旋和著色來保持自身平衡，這個代價之大跟同一個 hash 值的沖突次數(shù)成正比，因此需要維護好重寫的 hashCode 方法，使 hash code 盡可能分散。

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

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

什么是紅黑樹？

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

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

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

根是黑色。

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

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

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

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

時間敏感型程序。

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

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

什么是 fail-fast？

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

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

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

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

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