注：源碼系列文章主要是對某付費(fèi)專欄的總結(jié)記錄。如有侵權(quán)，請聯(lián)系刪除。
整體架構(gòu)
HashMap 底層的數(shù)據(jù)結(jié)構(gòu)主要是：數(shù)組 + 鏈表 + 紅黑樹。其中當(dāng)鏈表的長度大于 8 時，鏈表就會轉(zhuǎn)化成紅黑樹，當(dāng)紅黑樹的大小小于 6 時，紅黑樹會轉(zhuǎn)化成鏈表，整體的數(shù)據(jù)結(jié)構(gòu)如下：
HashMap 數(shù)據(jù)結(jié)構(gòu)圖例
圖中左邊豎著的是 HashMap 的數(shù)組結(jié)構(gòu) table，數(shù)組的元素可能是單個 Node，也可能是個鏈表，也可能是個紅黑樹，比如數(shù)組下標(biāo)索引為 1 的位置就是一個鏈表，下標(biāo)索引為 8 的位置對應(yīng)的就是紅黑樹，具體細(xì)節(jié)下文繼續(xù)。
1.1 類注釋
從 HashMap 的類注釋中，我們可以得到如下信息：
- 允許 null 值（作為鍵或值），不同于 HashTable，是線程不安全的；
-
load factor（影響因子）默認(rèn)值是0.75，是均衡了時間和空間損耗算出來的值，較高的值會減少空間開銷（擴(kuò)容減少，數(shù)組大小增長速度變慢），但增加了查找成本（hash 沖突增加，鏈表長度變長），不擴(kuò)容的條件：數(shù)組容量 > 需要的數(shù)組大小 / load factor； - 如果有很多數(shù)據(jù)需要存儲到 HashMap 中，建議 HashMap 的容量一開始就設(shè)置成足夠的大小，這樣可以防止其過程中不斷的擴(kuò)容，影響性能；
- HashMap 是非線程安全的，我們可以自己在外部加鎖，或者通過
Collections#synchronizedMap來實(shí)現(xiàn)線程安全，Collections#synchronizedMap的實(shí)現(xiàn)是在每個方法上都加上了synchronized鎖； - 在迭代過程中，如果 HashMap 的結(jié)構(gòu)被修改，會快速失敗。
1.2 常見屬性
// 初始容量默認(rèn)值為 16，必須是 2 的冪次方
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量默認(rèn)值，必須是 2 的冪次方并且小于等于 1 << 30
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
// 負(fù)載因子默認(rèn)值
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 桶上的鏈表長度大于等于 8 時，鏈表轉(zhuǎn)化為紅黑樹
/**
* 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;
// 桶上的紅黑樹大小小于等于 6 時，紅黑樹轉(zhuǎn)化為鏈表
/**
* 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;
// 當(dāng)數(shù)組容量大于 64 時，鏈表才會轉(zhuǎn)化為紅黑樹
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
// 存放數(shù)據(jù)的數(shù)組
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
// HashMap 的實(shí)際大小
transient int size;
// 記錄迭代過程中 HashMap 結(jié)構(gòu)是否發(fā)生變化，如果有變化，迭代會 fail-fast
transient int modCount;
// 擴(kuò)容的門檻，有兩種情況：
// 初始化時指定了數(shù)組大小的話，則通過 tableForSize 方法計(jì)算，數(shù)組的大小為 2 的冪次方
// 如果是通過 resize 方法進(jìn)行擴(kuò)容，大小 = 數(shù)組容量 * 0.75
int threshold;
// 負(fù)載因子
// 空參構(gòu)造器時，賦值為默認(rèn)的負(fù)載因子 0.75
final float loadFactor;
// 鏈表的節(jié)點(diǎn)
static class Node<K,V> implements Map.Entry<K,V> {}
// 紅黑樹的節(jié)點(diǎn)
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {}
2 新增
新增源碼流程圖：
HashMap put 流程.png
源碼分析：
// hash: 通過 hash 算法計(jì)算出來的值
// onlyIfAbsent: false 表示即使 key 已經(jīng)存在了，仍然會用新值覆蓋原來的值，默認(rèn)為 false
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab 表示數(shù)組，n 表示數(shù)組的長度，i 表示數(shù)組索引下標(biāo)，p 為 i 下標(biāo)位置的 Node 值
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果數(shù)組為空，使用 resize 方法初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果當(dāng)前索引位置是空的，直接生成新的節(jié)點(diǎn)在當(dāng)前索引位置上
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 如果當(dāng)前索引位置有值的處理方法，即我們常說的如何解決 hash 沖突
else {
// e: 當(dāng)前節(jié)點(diǎn)的臨時變量
Node<K,V> e; K k;
// 如果新增的 key 的 hash 和值都相等，則直接把當(dāng)前下標(biāo)位置的 Node 賦值給臨時變量
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果是紅黑樹，則使用紅黑樹的方式新增
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 如果是鏈表
else {
// 自旋
for (int binCount = 0; ; ++binCount) {
// e = p.next 表示鏈表從頭開始遍歷
// 如果 p.next == null 表明 p 是鏈表的尾節(jié)點(diǎn)
if ((e = p.next) == null) {
// 如果 p 是鏈表的尾節(jié)點(diǎn)，則直接將新節(jié)點(diǎn)放到鏈表的尾部
p.next = newNode(hash, key, value, null);
// 當(dāng)鏈表的長度大于等于 8 時，鏈表轉(zhuǎn)化為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 鏈表遍歷過程中，發(fā)現(xiàn)有元素和新增的元素相等，結(jié)束循環(huán)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 說明新節(jié)點(diǎn)的新增位置已經(jīng)找到了
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 當(dāng) onlyIfAbsent 為 false 時，才會覆蓋值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 返回舊的值
return oldValue;
}
}
// 記錄 HashMap 的數(shù)據(jù)結(jié)構(gòu)發(fā)生了變化
++modCount;
// 如果 HashMap 的實(shí)際大小大于擴(kuò)容的門檻，則開始擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
新增的流程上面已經(jīng)表示很清楚了，接下來看看鏈表和紅黑樹的新增。
2.1 鏈表的新增
鏈表的新增比較簡單，就是把當(dāng)前節(jié)點(diǎn)追加到鏈表的尾部，和 LinkedList 的追加實(shí)現(xiàn)一樣。
當(dāng)鏈表長度大于等于 8 時，此時鏈表就會轉(zhuǎn)化為紅黑樹，轉(zhuǎn)化的方法是 treeifyBin，此方法有一個判斷，當(dāng)鏈表長度大于等于 8，并且整個數(shù)組大小大于 64 時，才會轉(zhuǎn)換為紅黑樹，當(dāng)數(shù)組大小小于 64 時，只會觸發(fā)擴(kuò)容，不會轉(zhuǎn)化為紅黑樹。
可能面試的時候，有人問你為什么是 8，這個答案在源碼注釋中有說，翻譯大概如下：
鏈表查詢的時間復(fù)雜度是 O(n)，紅黑樹的查詢復(fù)雜度是 O(log(n))。在鏈表數(shù)據(jù)不多的時候，使用鏈表進(jìn)行遍歷也比較快，只有當(dāng)鏈表數(shù)據(jù)比較多的時候，才會轉(zhuǎn)化為紅黑樹，但紅黑樹需要占用的空間是鏈表的兩倍，拷貝到轉(zhuǎn)化時間和空閑損耗，所以我們需要定義出轉(zhuǎn)化的邊界值。
在考慮設(shè)計(jì) 8 這個值時，參考了<a >泊松分布概率函數(shù)</a>，由泊松分布中得出結(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)化為紅黑樹的情況，畢竟概率只有千萬分之一。
2.2 紅黑樹的新增
略。
3 查找
HashMap 的查找分為以下三步：
- 根據(jù) hash 算法定位數(shù)組的索引位置，equals 判斷當(dāng)前索引處節(jié)點(diǎn)是否是我們需要尋找的 key，是的話直接返回，不是的話繼續(xù)往下；
- 判斷當(dāng)前節(jié)點(diǎn)有無 next 節(jié)點(diǎn)，有的話判斷是鏈表類型，還是紅黑樹類型；
- 分別走鏈表和紅黑樹不同類型的查找方法。
源碼如下：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 只有當(dāng)數(shù)組不為空，并且數(shù)組長度大于0，并且根據(jù)當(dāng)前查找key的hash得到的節(jié)點(diǎn)不為null才進(jìn)入查找
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 如果當(dāng)前節(jié)點(diǎn)的就是我們要查找的節(jié)點(diǎn)則直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn) next 不為空則繼續(xù)
if ((e = first.next) != null) {
// 判斷當(dāng)前節(jié)點(diǎn)是紅黑樹則走紅黑樹查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 判斷當(dāng)前節(jié)點(diǎn)是鏈表
// 采用自旋方式從鏈表中查找 key，e 初始化鏈表的頭節(jié)點(diǎn) first 的下一個節(jié)點(diǎn) next
do {
// 如果當(dāng)前節(jié)點(diǎn) hash 等于 key 的 hash，并且 equals 相等，則當(dāng)前節(jié)點(diǎn)就是我們要找的節(jié)點(diǎn)
// 當(dāng) hash 沖突時，同一個 hash 值上是一個鏈表的時候，我們通過 equals 方法來比較 key 是否相等的
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
// 否則，把當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)拿出來繼續(xù)尋找
} while ((e = e.next) != null);
}
}
return null;
}
紅黑樹的查找：略。
總結(jié)
HashMap 的內(nèi)容雖然比較多，但大多數(shù) API 都只是針對數(shù)組 + 鏈表 + 紅黑樹這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行封裝而已。
------------------------------------- END -------------------------------------
