摘要：則使用了拉鏈?zhǔn)降纳⒘兴惴ǎ⒃谥幸肓思t黑樹優(yōu)化過長的鏈表。如果大家對紅黑樹感興趣，可以閱讀我的另一篇文章紅黑樹詳細(xì)分析。構(gòu)造方法構(gòu)造方法分析的構(gòu)造方法不多，只有四個。
1.概述
本篇文章我們來聊聊大家日常開發(fā)中常用的一個集合類 - HashMap。HashMap 最早出現(xiàn)在 JDK 1.2中，底層基于散列算法實現(xiàn)。HashMap 允許 null 鍵和 null 值，在計算哈鍵的哈希值時，null 鍵哈希值為 0。HashMap 并不保證鍵值對的順序，這意味著在進(jìn)行某些操作后，鍵值對的順序可能會發(fā)生變化。另外，需要注意的是，HashMap 是非線程安全類，在多線程環(huán)境下可能會存在問題。
在本篇文章中，我將會對 HashMap 中常用方法、重要屬性及相關(guān)方法進(jìn)行分析。需要說明的是，HashMap 源碼中可分析的點很多，本文很難一一覆蓋，請見諒。
2.原理
上一節(jié)說到 HashMap 底層是基于散列算法實現(xiàn)，散列算法分為散列再探測和拉鏈?zhǔn)?。HashMap 則使用了拉鏈?zhǔn)降纳⒘兴惴?，并?JDK 1.8 中引入了紅黑樹優(yōu)化過長的鏈表。數(shù)據(jù)結(jié)構(gòu)示意圖如下：
對于拉鏈?zhǔn)降纳⒘兴惴?，其?shù)據(jù)結(jié)構(gòu)是由數(shù)組和鏈表（或樹形結(jié)構(gòu)）組成。在進(jìn)行增刪查等操作時，首先要定位到元素的所在桶的位置，之后再從鏈表中定位該元素。比如我們要查詢上圖結(jié)構(gòu)中是否包含元素35，步驟如下：
定位元素35所處桶的位置，index = 35 % 16 = 3
在3號桶所指向的鏈表中繼續(xù)查找，發(fā)現(xiàn)35在鏈表中。
上面就是 HashMap 底層數(shù)據(jù)結(jié)構(gòu)的原理，HashMap 基本操作就是對拉鏈?zhǔn)缴⒘兴惴ɑ静僮鞯囊粚影b。不同的地方在于 JDK 1.8 中引入了紅黑樹，底層數(shù)據(jù)結(jié)構(gòu)由數(shù)組+鏈表變?yōu)榱?b>數(shù)組+鏈表+紅黑樹，不過本質(zhì)并未變。好了，原理部分先講到這，接下來說說源碼實現(xiàn)。
3.源碼分析
本篇文章所分析的源碼版本為 JDK 1.8。與 JDK 1.7 相比，JDK 1.8 對 HashMap 進(jìn)行了一些優(yōu)化。比如引入紅黑樹解決過長鏈表效率低的問題。重寫 resize 方法，移除了 alternative hashing 相關(guān)方法，避免重新計算鍵的 hash 等。不過本篇文章并不打算對這些優(yōu)化進(jìn)行分析，本文僅會分析 HashMap 常用的方法及一些重要屬性和相關(guān)方法。如果大家對紅黑樹感興趣，可以閱讀我的另一篇文章 - 紅黑樹詳細(xì)分析。
3.1 構(gòu)造方法
3.1.1 構(gòu)造方法分析
HashMap 的構(gòu)造方法不多，只有四個。HashMap 構(gòu)造方法做的事情比較簡單，一般都是初始化一些重要變量，比如 loadFactor 和 threshold。而底層的數(shù)據(jù)結(jié)構(gòu)則是延遲到插入鍵值對時再進(jìn)行初始化。HashMap 相關(guān)構(gòu)造方法如下：
/** 構(gòu)造方法 1 */
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/** 構(gòu)造方法 2 */
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/** 構(gòu)造方法 3 */
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/** 構(gòu)造方法 4 */
public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
上面4個構(gòu)造方法中，大家平時用的最多的應(yīng)該是第一個了。第一個構(gòu)造方法很簡單，僅將 loadFactor 變量設(shè)為默認(rèn)值。構(gòu)造方法2調(diào)用了構(gòu)造方法3，而構(gòu)造方法3仍然只是設(shè)置了一些變量。構(gòu)造方法4則是將另一個 Map 中的映射拷貝一份到自己的存儲結(jié)構(gòu)中來，這個方法不是很常用。
上面就是對構(gòu)造方法簡單的介紹，構(gòu)造方法本身并沒什么太多東西，所以就不說了。接下來說說構(gòu)造方法所初始化的幾個的變量。
3.1.2 初始容量、負(fù)載因子、閾值
我們在一般情況下，都會使用無參構(gòu)造方法創(chuàng)建 HashMap。但當(dāng)我們對時間和空間復(fù)雜度有要求的時候，使用默認(rèn)值有時可能達(dá)不到我們的要求，這個時候我們就需要手動調(diào)參。在 HashMap 構(gòu)造方法中，可供我們調(diào)整的參數(shù)有兩個，一個是初始容量 initialCapacity，另一個負(fù)載因子 loadFactor。通過這兩個設(shè)定這兩個參數(shù)，可以進(jìn)一步影響閾值大小。但初始閾值 threshold 僅由 initialCapacity 經(jīng)過移位操作計算得出。他們的作用分別如下：
| 名稱 |
用途 |
| initialCapacity |
HashMap 初始容量 |
| loadFactor |
負(fù)載因子 |
| threshold |
當(dāng)前 HashMap 所能容納鍵值對數(shù)量的最大值，超過這個值，則需擴(kuò)容 |
相關(guān)代碼如下：
/** The default initial capacity - MUST be a power of two. */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/** The load factor used when none specified in constructor. */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
final float loadFactor;
/** The next size value at which to resize (capacity * load factor). */
int threshold;
如果大家去看源碼，會發(fā)現(xiàn) HashMap 中沒有定義 initialCapacity 這個變量。這個也并不難理解，從參數(shù)名上可看出，這個變量表示一個初始容量，只是構(gòu)造方法中用一次，沒必要定義一個變量保存。但如果大家仔細(xì)看上面 HashMap 的構(gòu)造方法，會發(fā)現(xiàn)存儲鍵值對的數(shù)據(jù)結(jié)構(gòu)并不是在構(gòu)造方法里初始化的。這就有個疑問了，既然叫初始容量，但最終并沒有用與初始化數(shù)據(jù)結(jié)構(gòu)，那傳這個參數(shù)還有什么用呢？這個問題我先不解釋，給大家留個懸念，后面會說明。
默認(rèn)情況下，HashMap 初始容量是16，負(fù)載因子為 0.75。這里并沒有默認(rèn)閾值，原因是閾值可由容量乘上負(fù)載因子計算而來（注釋中有說明），即threshold = capacity * loadFactor。但當(dāng)你仔細(xì)看構(gòu)造方法3時，會發(fā)現(xiàn)閾值并不是由上面公式計算而來，而是通過一個方法算出來的。這是不是可以說明 threshold 變量的注釋有誤呢？還是僅這里進(jìn)行了特殊處理，其他地方遵循計算公式呢？關(guān)于這個疑問，這里也先不說明，后面在分析擴(kuò)容方法時，再來解釋這個問題。接下來，我們來看看初始化 threshold 的方法長什么樣的的，源碼如下：
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
上面的代碼長的有點不太好看，反正我第一次看的時候不明白它想干啥。不過后來在紙上畫畫，知道了它的用途。總結(jié)起來就一句話：找到大于或等于 cap 的最小2的冪。至于為啥要這樣，后面再解釋。我們先來看看 tableSizeFor 方法的圖解：
上面是 tableSizeFor 方法的計算過程圖，這里cap = 536,870,913 = 229 + 1，多次計算后，算出n + 1 = 1,073,741,824 = 230。通過圖解應(yīng)該可以比較容易理解這個方法的用途，這里就不多說了。
說完了初始閾值的計算過程，再來說說負(fù)載因子（loadFactor）。對于 HashMap 來說，負(fù)載因子是一個很重要的參數(shù)，該參數(shù)反應(yīng)了 HashMap 桶數(shù)組的使用情況（假設(shè)鍵值對節(jié)點均勻分布在桶數(shù)組中）。通過調(diào)節(jié)負(fù)載因子，可使 HashMap 時間和空間復(fù)雜度上有不同的表現(xiàn)。當(dāng)我們調(diào)低負(fù)載因子時，HashMap 所能容納的鍵值對數(shù)量變少。擴(kuò)容時，重新將鍵值對存儲新的桶數(shù)組里，鍵的鍵之間產(chǎn)生的碰撞會下降，鏈表長度變短。此時，HashMap 的增刪改查等操作的效率將會變高，這里是典型的拿空間換時間。相反，如果增加負(fù)載因子（負(fù)載因子可以大于1），HashMap 所能容納的鍵值對數(shù)量變多，空間利用率高，但碰撞率也高。這意味著鏈表長度變長，效率也隨之降低，這種情況是拿時間換空間。至于負(fù)載因子怎么調(diào)節(jié)，這個看使用場景了。一般情況下，我們用默認(rèn)值就可以了。
3.2 查找
HashMap 的查找操作比較簡單，查找步驟與原理篇介紹一致，即先定位鍵值對所在的桶的位置，然后再對鏈表或紅黑樹進(jìn)行查找。通過這兩步即可完成查找，該操作相關(guān)代碼如下：
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
// 1. 定位鍵值對所在桶的位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 2. 如果 first 是 TreeNode 類型，則調(diào)用黑紅樹查找方法
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
// 2. 對鏈表進(jìn)行查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
查找的核心邏輯是封裝在 getNode 方法中的，getNode 方法源碼我已經(jīng)寫了一些注釋，應(yīng)該不難看懂。我們先來看看查找過程的第一步 - 確定桶位置，其實現(xiàn)代碼如下：
// index = (n - 1) & hash
first = tab[(n - 1) & hash]
這里通過(n - 1)& hash即可算出桶的在桶數(shù)組中的位置，可能有的朋友不太明白這里為什么這么做，這里簡單解釋一下。HashMap 中桶數(shù)組的大小 length 總是2的冪，此時，(n - 1) & hash 等價于對 length 取余。但取余的計算效率沒有位運算高，所以(n - 1) & hash也是一個小的優(yōu)化。舉個例子說明一下吧，假設(shè) hash = 185，n = 16。計算過程示意圖如下：
上面的計算并不復(fù)雜，這里就不多說了。
在上面源碼中，除了查找相關(guān)邏輯，還有一個計算 hash 的方法。這個方法源碼如下：
/**
* 計算鍵的 hash 值
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看這個方法的邏輯好像是通過位運算重新計算 hash，那么這里為什么要這樣做呢？為什么不直接用鍵的 hashCode 方法產(chǎn)生的 hash 呢？大家先可以思考一下，我把答案寫在下面。
這樣做有兩個好處，我來簡單解釋一下。我們再看一下上面求余的計算圖，圖中的 hash 是由鍵的 hashCode 產(chǎn)生。計算余數(shù)時，由于 n 比較小，hash 只有低4位參與了計算，高位的計算可以認(rèn)為是無效的。這樣導(dǎo)致了計算結(jié)果只與低位信息有關(guān)，高位數(shù)據(jù)沒發(fā)揮作用。為了處理這個缺陷，我們可以上圖中的 hash 高4位數(shù)據(jù)與低4位數(shù)據(jù)進(jìn)行異或運算，即 hash ^ (hash >>> 4)。通過這種方式，讓高位數(shù)據(jù)與低位數(shù)據(jù)進(jìn)行異或，以此加大低位信息的隨機(jī)性，變相的讓高位數(shù)據(jù)參與到計算中。此時的計算過程如下：
在 Java 中，hashCode 方法產(chǎn)生的 hash 是 int 類型，32 位寬。前16位為高位，后16位為低位，所以要右移16位。
上面所說的是重新計算 hash 的一個好處，除此之外，重新計算 hash 的另一個好處是可以增加 hash 的復(fù)雜度。當(dāng)我們覆寫 hashCode 方法時，可能會寫出分布性不佳的 hashCode 方法，進(jìn)而導(dǎo)致 hash 的沖突率比較高。通過移位和異或運算，可以讓 hash 變得更復(fù)雜，進(jìn)而影響 hash 的分布性。這也就是為什么 HashMap 不直接使用鍵對象原始 hash 的原因了。
3.3 遍歷
和查找查找一樣，遍歷操作也是大家使用頻率比較高的一個操作。對于 遍歷 HashMap，我們一般都會用下面的方式：
for(Object key : map.keySet()) {
// do something
}
或
for(HashMap.Entry entry : map.entrySet()) {
// do something
}
從上面代碼片段中可以看出，大家一般都是對 HashMap 的 key 集合或 Entry 集合進(jìn)行遍歷。上面代碼片段中用 foreach 遍歷 keySet 方法產(chǎn)生的集合，在編譯時會轉(zhuǎn)換成用迭代器遍歷，等價于：
Set keys = map.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
Object key = ite.next();
// do something
}
大家在遍歷 HashMap 的過程中會發(fā)現(xiàn)，多次對 HashMap 進(jìn)行遍歷時，遍歷結(jié)果順序都是一致的。但這個順序和插入的順序一般都是不一致的。產(chǎn)生上述行為的原因是怎樣的呢？大家想一下原因。我先把遍歷相關(guān)的代碼貼出來，如下：
public Set keySet() {
Set ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
/**
* 鍵集合
*/
final class KeySet extends AbstractSet {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
// 省略部分代碼
}
/**
* 鍵迭代器
*/
final class KeyIterator extends HashIterator
implements Iterator {
public final K next() { return nextNode().key; }
}
abstract class HashIterator {
Node next; // next entry to return
Node current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
// 尋找第一個包含鏈表節(jié)點引用的桶
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node nextNode() {
Node[] t;
Node e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
// 尋找下一個包含鏈表節(jié)點引用的桶
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
//省略部分代碼
}
如上面的源碼，遍歷所有的鍵時，首先要獲取鍵集合KeySet對象，然后再通過 KeySet 的迭代器KeyIterator進(jìn)行遍歷。KeyIterator 類繼承自HashIterator類，核心邏輯也封裝在 HashIterator 類中。HashIterator 的邏輯并不復(fù)雜，在初始化時，HashIterator 先從桶數(shù)組中找到包含鏈表節(jié)點引用的桶。然后對這個桶指向的鏈表進(jìn)行遍歷。遍歷完成后，再繼續(xù)尋找下一個包含鏈表節(jié)點引用的桶，找到繼續(xù)遍歷。找不到，則結(jié)束遍歷。舉個例子，假設(shè)我們遍歷下圖的結(jié)構(gòu)：
HashIterator 在初始化時，會先遍歷桶數(shù)組，找到包含鏈表節(jié)點引用的桶，對應(yīng)圖中就是3號桶。隨后由 nextNode 方法遍歷該桶所指向的鏈表。遍歷完3號桶后，nextNode 方法繼續(xù)尋找下一個不為空的桶，對應(yīng)圖中的7號桶。之后流程和上面類似，直至遍歷完最后一個桶。以上就是 HashIterator 的核心邏輯的流程，對應(yīng)下圖：
遍歷上圖的最終結(jié)果是 19 -> 3 -> 35 -> 7 -> 11 -> 43 -> 59，為了驗證正確性，簡單寫點測試代碼跑一下看看。測試代碼如下：
/**
* 應(yīng)在 JDK 1.8 下測試，其他環(huán)境下不保證結(jié)果和上面一致
*/
public class HashMapTest {
@Test
public void testTraversal() {
HashMap map = new HashMap(16);
map.put(7, "");
map.put(11, "");
map.put(43, "");
map.put(59, "");
map.put(19, "");
map.put(3, "");
map.put(35, "");
System.out.println("遍歷結(jié)果：");
for (Integer key : map.keySet()) {
System.out.print(key + " -> ");
}
}
}
遍歷結(jié)果如下：
在本小節(jié)的最后，拋兩個問題給大家。在 JDK 1.8 版本中，為了避免過長的鏈表對 HashMap 性能的影響，特地引入了紅黑樹優(yōu)化性能。但在上面的源碼中并沒有發(fā)現(xiàn)紅黑樹遍歷的相關(guān)邏輯，這是為什么呢？對于被轉(zhuǎn)換成紅黑樹的鏈表該如何遍歷呢？大家可以先想想，然后可以去源碼或本文后續(xù)章節(jié)中找答案。
3.4 插入
3.4.1 插入邏輯分析
通過前兩節(jié)的分析，大家對 HashMap 低層的數(shù)據(jù)結(jié)構(gòu)應(yīng)該了然于心了。即使我不說，大家也應(yīng)該能知道 HashMap 的插入流程是什么樣的了。首先肯定是先定位要插入的鍵值對屬于哪個桶，定位到桶后，再判斷桶是否為空。如果為空，則將鍵值對存入即可。如果不為空，則需將鍵值對接在鏈表最后一個位置，或者更新鍵值對。這就是 HashMap 的插入流程，是不是覺得很簡單。當(dāng)然，大家先別高興。這只是一個簡化版的插入流程，真正的插入流程要復(fù)雜不少。首先 HashMap 是變長集合，所以需要考慮擴(kuò)容的問題。其次，在 JDK 1.8 中，HashMap 引入了紅黑樹優(yōu)化過長鏈表，這里還要考慮多長的鏈表需要進(jìn)行優(yōu)化，優(yōu)化過程又是怎樣的問題。引入這里兩個問題后，大家會發(fā)現(xiàn)原本簡單的操作，現(xiàn)在略顯復(fù)雜了。在本節(jié)中，我將先分析插入操作的源碼，擴(kuò)容、樹化（鏈表轉(zhuǎn)為紅黑樹，下同）以及其他和樹結(jié)構(gòu)相關(guān)的操作，隨后將在獨立的兩小結(jié)中進(jìn)行分析。接下來，先來看一下插入操作的源碼：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// 初始化桶數(shù)組 table，table 被延遲到插入新數(shù)據(jù)時再進(jìn)行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果桶中不包含鍵值對節(jié)點引用，則將新鍵值對節(jié)點的引用存入桶中即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
// 如果鍵的值以及節(jié)點 hash 等于鏈表中的第一個鍵值對節(jié)點時，則將 e 指向該鍵值對
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果桶中的引用類型為 TreeNode，則調(diào)用紅黑樹的插入方法
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
// 對鏈表進(jìn)行遍歷，并統(tǒng)計鏈表長度
for (int binCount = 0; ; ++binCount) {
// 鏈表中不包含要插入的鍵值對節(jié)點時，則將該節(jié)點接在鏈表的最后
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果鏈表長度大于或等于樹化閾值，則進(jìn)行樹化操作
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 條件為 true，表示當(dāng)前鏈表包含要插入的鍵值對，終止遍歷
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 判斷要插入的鍵值對是否存在 HashMap 中
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 表示是否僅在 oldValue 為 null 的情況下更新鍵值對的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 鍵值對數(shù)量超過閾值時，則進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
插入操作的入口方法是 put(K,V)，但核心邏輯在V putVal(int, K, V, boolean, boolean) 方法中。putVal 方法主要做了這么幾件事情：
當(dāng)桶數(shù)組 table 為空時，通過擴(kuò)容的方式初始化 table
查找要插入的鍵值對是否已經(jīng)存在，存在的話根據(jù)條件判斷是否用新值替換舊值
如果不存在，則將鍵值對鏈入鏈表中，并根據(jù)鏈表長度決定是否將鏈表轉(zhuǎn)為紅黑樹
判斷鍵值對數(shù)量是否大于閾值，大于的話則進(jìn)行擴(kuò)容操作
以上就是 HashMap 插入的邏輯，并不是很復(fù)雜，這里就不多說了。接下來來分析一下擴(kuò)容機(jī)制。
3.4.2 擴(kuò)容機(jī)制
在 Java 中，數(shù)組的長度是固定的，這意味著數(shù)組只能存儲固定量的數(shù)據(jù)。但在開發(fā)的過程中，很多時候我們無法知道該建多大的數(shù)組合適。建小了不夠用，建大了用不完，造成浪費。如果我們能實現(xiàn)一種變長的數(shù)組，并按需分配空間就好了。好在，我們不用自己實現(xiàn)變長數(shù)組，Java 集合框架已經(jīng)實現(xiàn)了變長的數(shù)據(jù)結(jié)構(gòu)。比如 ArrayList 和 HashMap。對于這類基于數(shù)組的變長數(shù)據(jù)結(jié)構(gòu)，擴(kuò)容是一個非常重要的操作。下面就來聊聊 HashMap 的擴(kuò)容機(jī)制。
在詳細(xì)分析之前，先來說一下擴(kuò)容相關(guān)的背景知識：
在 HashMap 中，桶數(shù)組的長度均是2的冪，閾值大小為桶數(shù)組長度與負(fù)載因子的乘積。當(dāng) HashMap 中的鍵值對數(shù)量超過閾值時，進(jìn)行擴(kuò)容。
HashMap 的擴(kuò)容機(jī)制與其他變長集合的套路不太一樣，HashMap 按當(dāng)前桶數(shù)組長度的2倍進(jìn)行擴(kuò)容，閾值也變?yōu)樵瓉淼?倍（如果計算過程中，閾值溢出歸零，則按閾值公式重新計算）。擴(kuò)容之后，要重新計算鍵值對的位置，并把它們移動到合適的位置上去。以上就是 HashMap 的擴(kuò)容大致過程，接下來我們來看看具體的實現(xiàn)：
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果 table 不為空，表明已經(jīng)初始化過了
if (oldCap > 0) {
// 當(dāng) table 容量超過容量最大值，則不再擴(kuò)容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 按舊容量和閾值的2倍計算新容量和閾值的大小
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // initial capacity was placed in threshold
/*
* 初始化時，將 threshold 的值賦值給 newCap，
* HashMap 使用 threshold 變量暫時保存 initialCapacity 參數(shù)的值
*/
newCap = oldThr;
else { // zero initial threshold signifies using defaults
/*
* 調(diào)用無參構(gòu)造方法時，桶數(shù)組容量為默認(rèn)容量，
* 閾值為默認(rèn)容量與默認(rèn)負(fù)載因子乘積
*/
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr 為 0 時，按閾值計算公式進(jìn)行計算
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 創(chuàng)建新的桶數(shù)組，桶數(shù)組的初始化也是在這里完成的
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 如果舊的桶數(shù)組不為空，則遍歷桶數(shù)組，并將鍵值對映射到新的桶數(shù)組中
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 重新映射時，需要對紅黑樹進(jìn)行拆分
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
// 遍歷鏈表，并將鏈表節(jié)點按原順序進(jìn)行分組
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 將分組后的鏈表映射到新桶中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
上面的源碼有點長，希望大家耐心看懂它的邏輯。上面的源碼總共做了3件事，分別是：
計算新桶數(shù)組的容量 newCap 和新閾值 newThr
根據(jù)計算出的 newCap 創(chuàng)建新的桶數(shù)組，桶數(shù)組 table 也是在這里進(jìn)行初始化的
將鍵值對節(jié)點重新映射到新的桶數(shù)組里。如果節(jié)點是 TreeNode 類型，則需要拆分紅黑樹。如果是普通節(jié)點，則節(jié)點按原順序進(jìn)行分組。
上面列的三點中，創(chuàng)建新的桶數(shù)組就一行代碼，不用說了。接下來，來說說第一點和第三點，先說說 newCap 和 newThr 計算過程。該計算過程對應(yīng) resize 源碼的第一和第二個條件分支，如下：
// 第一個條件分支
if ( oldCap > 0) {
// 嵌套條件分支
if (oldCap >= MAXIMUM_CAPACITY) {...}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) {...}
}
else if (oldThr > 0) {...}
else {...}
// 第二個條件分支
if (newThr == 0) {...}
通過這兩個條件分支對不同情況進(jìn)行判斷，進(jìn)而算出不同的容量值和閾值。它們所覆蓋的情況如下：
分支一：
| 條件 |
覆蓋情況 |
備注 |
| oldCap > 0 |
桶數(shù)組 table 已經(jīng)被初始化 |
|
| oldThr > 0 |
threshold > 0，且桶數(shù)組未被初始化 |
調(diào)用?HashMap(int) 和 HashMap(int, float) 構(gòu)造方法時會產(chǎn)生這種情況，此種情況下 newCap = oldThr，newThr 在第二個條件分支中算出 |
| oldCap == 0 &&?oldThr == 0 |
桶數(shù)組未被初始化，且?threshold 為 0 |
調(diào)用?HashMap() 構(gòu)造方法會產(chǎn)生這種情況。 |
這里把oldThr > 0情況多帶帶拿出來說一下。在這種情況下，會將 oldThr 賦值給 newCap，等價于newCap = threshold = tableSizeFor(initialCapacity)。我們在初始化時傳入的 initialCapacity 參數(shù)經(jīng)過 threshold 中轉(zhuǎn)最終賦值給了 newCap。這也就解答了前面提的一個疑問：initialCapacity 參數(shù)沒有被保存下來，那么它怎么參與桶數(shù)組的初始化過程的呢？
嵌套分支：
| 條件 |
覆蓋情況 |
備注 |
| oldCap >= 230
|
桶數(shù)組容量大于或等于最大桶容量 230
|
這種情況下不再擴(kuò)容 |
| newCap < 230 && oldCap > 16 |
新桶數(shù)組容量小于最大值，且舊桶數(shù)組容量大于 16 |
該種情況下新閾值 newThr = oldThr << 1，移位可能會導(dǎo)致溢出 |
這里簡單說明一下移位導(dǎo)致的溢出情況，當(dāng) loadFactor小數(shù)位為 0，整數(shù)位可被2整除且大于等于8時，在某次計算中就可能會導(dǎo)致 newThr 溢出歸零。見下圖：
分支二：
| 條件 |
覆蓋情況 |
備注 |
| newThr == 0 |
第一個條件分支未計算 newThr 或嵌套分支在計算過程中導(dǎo)致 newThr 溢出歸零 |
|
說完 newCap 和 newThr 的計算過程，接下來再來分析一下鍵值對節(jié)點重新映射的過程。
在 JDK 1.8 中，重新映射節(jié)點需要考慮節(jié)點類型。對于樹形節(jié)點，需先拆分紅黑樹再映射。對于鏈表類型節(jié)點，則需先對鏈表進(jìn)行分組，然后再映射。需要的注意的是，分組后，組內(nèi)節(jié)點相對位置保持不變。關(guān)于紅黑樹拆分的邏輯將會放在下一小節(jié)說明，先來看看鏈表是怎樣進(jìn)行分組映射的。
我們都知道往底層數(shù)據(jù)結(jié)構(gòu)中插入節(jié)點時，一般都是先通過模運算計算桶位置，接著把節(jié)點放入桶中即可。事實上，我們可以把重新映射看做插入操作。在 JDK 1.7 中，也確實是這樣做的。但在 JDK 1.8 中，則對這個過程進(jìn)行了一定的優(yōu)化，邏輯上要稍微復(fù)雜一些。在詳細(xì)分析前，我們先來回顧一下 hash 求余的過程：
上圖中，桶數(shù)組大小 n = 16，hash1 與 hash2 不相等。但因為只有后4位參與求余，所以結(jié)果相等。當(dāng)桶數(shù)組擴(kuò)容后，n 由16變成了32，對上面的 hash 值重新進(jìn)行映射：
擴(kuò)容后，參與模運算的位數(shù)由4位變?yōu)榱?位。由于兩個 hash 第5位的值是不一樣，所以兩個 hash 算出的結(jié)果也不一樣。上面的計算過程并不難理解，繼續(xù)往下分析。
假設(shè)我們上圖的桶數(shù)組進(jìn)行擴(kuò)容，擴(kuò)容后容量 n = 16，重新映射過程如下:
依次遍歷鏈表，并計算節(jié)點 hash & oldCap 的值。如下圖所示
如果值為0，將 loHead 和 loTail 指向這個節(jié)點。如果后面還有節(jié)點 hash & oldCap 為0的話，則將節(jié)點鏈入 loHead 指向的鏈表中，并將 loTail 指向該節(jié)點。如果值為非0的話，則讓 hiHead 和 hiTail 指向該節(jié)點。完成遍歷后，可能會得到兩條鏈表，此時就完成了鏈表分組：
最后再將這兩條鏈接存放到相應(yīng)的桶中，完成擴(kuò)容。如下圖：
從上圖可以發(fā)現(xiàn)，重新映射后，兩條鏈表中的節(jié)點順序并未發(fā)生變化，還是保持了擴(kuò)容前的順序。以上就是 JDK 1.8 中 HashMap 擴(kuò)容的代碼講解。另外再補充一下，JDK 1.8 版本下 HashMap 擴(kuò)容效率要高于之前版本。如果大家看過 JDK 1.7 的源碼會發(fā)現(xiàn)，JDK 1.7 為了防止因 hash 碰撞引發(fā)的拒絕服務(wù)攻擊，在計算 hash 過程中引入隨機(jī)種子。以增強 hash 的隨機(jī)性，使得鍵值對均勻分布在桶數(shù)組中。在擴(kuò)容過程中，相關(guān)方法會根據(jù)容量判斷是否需要生成新的隨機(jī)種子，并重新計算所有節(jié)點的 hash。而在 JDK 1.8 中，則通過引入紅黑樹替代了該種方式。從而避免了多次計算 hash 的操作，提高了擴(kuò)容效率。
本小節(jié)的內(nèi)容講就先講到這，接下來，來講講鏈表與紅黑樹相互轉(zhuǎn)換的過程。
3.4.3 鏈表樹化、紅黑樹鏈化與拆分
JDK 1.8 對 HashMap 實現(xiàn)進(jìn)行了改進(jìn)。最大的改進(jìn)莫過于在引入了紅黑樹處理頻繁的碰撞，代碼復(fù)雜度也隨之上升。比如，以前只需實現(xiàn)一套針對鏈表操作的方法即可。而引入紅黑樹后，需要另外實現(xiàn)紅黑樹相關(guān)的操作。紅黑樹是一種自平衡的二叉查找樹，本身就比較復(fù)雜。本篇文章中并不打算對紅黑樹展開介紹，本文僅會介紹鏈表樹化需要注意的地方。至于紅黑樹詳細(xì)的介紹，如果大家有興趣，可以參考我的另一篇文章 - 紅黑樹詳細(xì)分析。
在展開說明之前，先把樹化的相關(guān)代碼貼出來，如下：
static final int TREEIFY_THRESHOLD = 8;
/**
* 當(dāng)桶數(shù)組容量小于該值時，優(yōu)先進(jìn)行擴(kuò)容，而不是樹化
*/
static final int MIN_TREEIFY_CAPACITY = 64;
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
}
/**
* 將普通節(jié)點鏈表轉(zhuǎn)換成樹形節(jié)點鏈表
*/
final void treeifyBin(Node[] tab, int hash) {
int n, index; Node e;
// 桶數(shù)組容量小于 MIN_TREEIFY_CAPACITY，優(yōu)先進(jìn)行擴(kuò)容而不是樹化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// hd 為頭節(jié)點（head），tl 為尾節(jié)點（tail）
TreeNode hd = null, tl = null;
do {
// 將普通節(jié)點替換成樹形節(jié)點
TreeNode p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null); // 將普通鏈表轉(zhuǎn)成由樹形節(jié)點鏈表
if ((tab[index] = hd) != null)
// 將樹形鏈表轉(zhuǎn)換成紅黑樹
hd.treeify(tab);
}
}
TreeNode replacementTreeNode(Node p, Node next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
在擴(kuò)容過程中，樹化要滿足兩個條件：
鏈表長度大于等于 TREEIFY_THRESHOLD
桶數(shù)組容量大于等于 MIN_TREEIFY_CAPACITY
第一個條件比較好理解，這里就不說了。這里來說說加入第二個條件的原因，個人覺得原因如下：
當(dāng)桶數(shù)組容量比較小時，鍵值對節(jié)點 hash 的碰撞率可能會比較高，進(jìn)而導(dǎo)致鏈表長度較長。這個時候應(yīng)該優(yōu)先擴(kuò)容，而不是立馬樹化。畢竟高碰撞率是因為桶數(shù)組容量較小引起的，這個是主因。容量小時，優(yōu)先擴(kuò)容可以避免一些列的不必要的樹化過程。同時，桶容量較小時，擴(kuò)容會比較頻繁，擴(kuò)容時需要拆分紅黑樹并重新映射。所以在桶容量比較小的情況下，將長鏈表轉(zhuǎn)成紅黑樹是一件吃力不討好的事。
回到上面的源碼中，我們繼續(xù)看一下 treeifyBin 方法。該方法主要的作用是將普通鏈表轉(zhuǎn)成為由 TreeNode 型節(jié)點組成的鏈表，并在最后調(diào)用 treeify 是將該鏈表轉(zhuǎn)為紅黑樹。TreeNode 繼承自 Node 類，所以 TreeNode 仍然包含 next 引用，原鏈表的節(jié)點順序最終通過 next 引用被保存下來。我們假設(shè)樹化前，鏈表結(jié)構(gòu)如下：
HashMap 在設(shè)計之初，并沒有考慮到以后會引入紅黑樹進(jìn)行優(yōu)化。所以并沒有像 TreeMap 那樣，要求鍵類實現(xiàn) comparable 接口或提供相應(yīng)的比較器。但由于樹化過程需要比較兩個鍵對象的大小，在鍵類沒有實現(xiàn) comparable 接口的情況下，怎么比較鍵與鍵之間的大小了就成了一個棘手的問題。為了解決這個問題，HashMap 是做了三步處理，確保可以比較出兩個鍵的大小，如下：
比較鍵與鍵之間 hash 的大小，如果 hash 相同，繼續(xù)往下比較
檢測鍵類是否實現(xiàn)了 Comparable 接口，如果實現(xiàn)調(diào)用 compareTo 方法進(jìn)行比較
如果仍未比較出大小，就需要進(jìn)行仲裁了，仲裁方法為 tieBreakOrder（大家自己看源碼吧）
tie break 是網(wǎng)球術(shù)語，可以理解為加時賽的意思，起這個名字還是挺有意思的。
通過上面三次比較，最終就可以比較出孰大孰小。比較出大小后就可以構(gòu)造紅黑樹了，最終構(gòu)造出的紅黑樹如下：
橙色的箭頭表示 TreeNode 的 next 引用。由于空間有限，prev 引用未畫出?？梢钥闯?，鏈表轉(zhuǎn)成紅黑樹后，原鏈表的順序仍然會被引用仍被保留了（紅黑樹的根節(jié)點會被移動到鏈表的第一位），我們?nèi)匀豢梢园幢闅v鏈表的方式去遍歷上面的紅黑樹。這樣的結(jié)構(gòu)為后面紅黑樹的切分以及紅黑樹轉(zhuǎn)成鏈表做好了鋪墊，我們繼續(xù)往下分析。
紅黑樹拆分
擴(kuò)容后，普通節(jié)點需要重新映射，紅黑樹節(jié)點也不例外。按照一般的思路，我們可以先把紅黑樹轉(zhuǎn)成鏈表，之后再重新映射鏈表即可。這種處理方式是大家比較容易想到的，但這樣做會損失一定的效率。不同于上面的處理方式，HashMap 實現(xiàn)的思路則是上好佳（上好佳請把廣告費打給我）。如上節(jié)所說，在將普通鏈表轉(zhuǎn)成紅黑樹時，HashMap 通過兩個額外的引用 next 和 prev 保留了原鏈表的節(jié)點順序。這樣再對紅黑樹進(jìn)行重新映射時，完全可以按照映射鏈表的方式進(jìn)行。這樣就避免了將紅黑樹轉(zhuǎn)成鏈表后再進(jìn)行映射，無形中提高了效率。
以上就是紅黑樹拆分的邏輯，下面看一下具體實現(xiàn)吧：
// 紅黑樹轉(zhuǎn)鏈表閾值
static final int UNTREEIFY_THRESHOLD = 6;
final void split(HashMap map, Node[] tab, int index, int bit) {
TreeNode b = this;
// Relink into lo and hi lists, preserving order
TreeNode loHead = null, loTail = null;
TreeNode hiHead = null, hiTail = null;
int lc = 0, hc = 0;
/*
* 紅黑樹節(jié)點仍然保留了 next 引用，故仍可以按鏈表方式遍歷紅黑樹。
* 下面的循環(huán)是對紅黑樹節(jié)點進(jìn)行分組，與上面類似
*/
for (TreeNode e = b, next; e != null; e = next) {
next = (TreeNode)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
// 如果 loHead 不為空，且鏈表長度小于等于 6，則將紅黑樹轉(zhuǎn)成鏈表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
/*
* hiHead == null 時，表明擴(kuò)容后，
* 所有節(jié)點仍在原位置，樹結(jié)構(gòu)不變，無需重新樹化
*/
if (hiHead != null)
loHead.treeify(tab);
}
}
// 與上面類似
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
從源碼上可以看得出，重新映射紅黑樹的邏輯和重新映射鏈表的邏輯基本一致。不同的地方在于，重新映射后，會將紅黑樹拆分成兩條由 TreeNode 組成的鏈表。如果鏈表長度小于 UNTREEIFY_THRESHOLD，則將鏈表轉(zhuǎn)換成普通鏈表。否則根據(jù)條件重新將 TreeNode 鏈表樹化。舉個例子說明一下，假設(shè)擴(kuò)容后，重新映射上圖的紅黑樹，映射結(jié)果如下：
紅黑樹鏈化
前面說過，紅黑樹中仍然保留了原鏈表節(jié)點順序。有了這個前提，再將紅黑樹轉(zhuǎn)成鏈表就簡單多了，僅需將 TreeNode 鏈表轉(zhuǎn)成 Node 類型的鏈表即可。相關(guān)代碼如下：
final Node untreeify(HashMap map) {
Node hd = null, tl = null;
// 遍歷 TreeNode 鏈表，并用 Node 替換
for (Node q = this; q != null; q = q.next) {
// 替換節(jié)點類型
Node p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
Node replacementNode(Node p, Node next) {
return new Node<>(p.hash, p.key, p.value, next);
}
上面的代碼并不復(fù)雜，不難理解，這里就不多說了。到此擴(kuò)容相關(guān)內(nèi)容就說完了，不知道大家理解沒。
3.5 刪除
如果大家堅持看完了前面的內(nèi)容，到本節(jié)就可以輕松一下。當(dāng)然，前提是不去看紅黑樹的刪除操作。不過紅黑樹并非本文講解重點，本節(jié)中也不會介紹紅黑樹相關(guān)內(nèi)容，所以大家不用擔(dān)心。
HashMap 的刪除操作并不復(fù)雜，僅需三個步驟即可完成。第一步是定位桶位置，第二步遍歷鏈表并找到鍵值相等的節(jié)點，第三步刪除節(jié)點。相關(guān)源碼如下：
public V remove(Object key) {
Node e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node[] tab; Node p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
// 1. 定位桶位置
(p = tab[index = (n - 1) & hash]) != null) {
Node node = null, e; K k; V v;
// 如果鍵的值與鏈表第一個節(jié)點相等，則將 node 指向該節(jié)點
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
// 如果是 TreeNode 類型，調(diào)用紅黑樹的查找邏輯定位待刪除節(jié)點
if (p instanceof TreeNode)
node = ((TreeNode)p).getTreeNode(hash, key);
else {
// 2. 遍歷鏈表，找到待刪除節(jié)點
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 3. 刪除節(jié)點，并修復(fù)鏈表或紅黑樹
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
刪除操作本身并不復(fù)雜，有了前面的基礎(chǔ)，理解起來也就不難了，這里就不多說了。
3.6 其他細(xì)節(jié)
前面的內(nèi)容分析了 HashMap 的常用操作及相關(guān)的源碼，本節(jié)內(nèi)容再補充一點其他方面的東西。
被 transient 所修飾 table 變量
如果大家細(xì)心閱讀 HashMap 的源碼，會發(fā)現(xiàn)桶數(shù)組 table 被申明為 transient。transient 表示易變的意思，在 Java 中，被該關(guān)鍵字修飾的變量不會被默認(rèn)的序列化機(jī)制序列化。我們再回到源碼中，考慮一個問題：桶數(shù)組 table 是 HashMap 底層重要的數(shù)據(jù)結(jié)構(gòu)，不序列化的話，別人還怎么還原呢？
這里簡單說明一下吧，HashMap 并沒有使用默認(rèn)的序列化機(jī)制，而是通過實現(xiàn)readObject/writeObject兩個方法自定義了序列化的內(nèi)容。這樣做是有原因的，試問一句，HashMap 中存儲的內(nèi)容是什么？不用說，大家也知道是鍵值對。所以只要我們把鍵值對序列化了，我們就可以根據(jù)鍵值對數(shù)據(jù)重建 HashMap。有的朋友可能會想，序列化 table 不是可以一步到位，后面直接還原不就行了嗎？這樣一想，倒也是合理。但序列化 talbe 存在著兩個問題：
table 多數(shù)情況下是無法被存滿的，序列化未使用的部分，浪費空間
同一個鍵值對在不同 JVM 下，所處的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能會發(fā)生錯誤。
以上兩個問題中，第一個問題比較好理解，第二個問題解釋一下。HashMap 的get/put/remove等方法第一步就是根據(jù) hash 找到鍵所在的桶位置，但如果鍵沒有覆寫 hashCode 方法，計算 hash 時最終調(diào)用 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是 native 型的，不同的 JVM 下，可能會有不同的實現(xiàn)，產(chǎn)生的 hash 可能也是不一樣的。也就是說同一個鍵在不同平臺下可能會產(chǎn)生不同的 hash，此時再對在同一個 table 繼續(xù)操作，就會出現(xiàn)問題。
綜上所述，大家應(yīng)該能明白 HashMap 不序列化 table 的原因了。
3.7 總結(jié)
本章對 HashMap 常見操作相關(guān)代碼進(jìn)行了詳細(xì)分析，并在最后補充了一些其他細(xì)節(jié)。在本章中，插入操作一節(jié)的內(nèi)容說的最多，主要是因為插入操作涉及的點特別多，一環(huán)扣一環(huán)。包含但不限于“table 初始化、擴(kuò)容、樹化”等，總體來說，插入操作分析起來難度還是很大的。好在，最后分析完了。
本章篇幅雖比較大，但仍未把 HashMap 所有的點都分析到。比如，紅黑樹的增刪查等操作。當(dāng)然，我個人看來，以上的分析已經(jīng)夠了。畢竟大家是類庫的使用者而不是設(shè)計者，沒必要去弄懂每個細(xì)節(jié)。所以如果某些細(xì)節(jié)實在看不懂的話就跳過吧，對我們開發(fā)來說，知道 HashMap 大致原理即可。
好了，本章到此結(jié)束。
4.寫在最后
寫到這里終于可以松一口氣了，這篇文章前前后后花了我一周多的時間。在我寫這篇文章之前，對 HashMap 認(rèn)識僅限于原理層面，并未深入了解。一開始，我覺得關(guān)于 HashMap 沒什么好寫的，畢竟大家對 HashMap 多少都有一定的了解。但等我深入閱讀 HashMap 源碼后，發(fā)現(xiàn)之前的認(rèn)知是錯的。不是沒什么可寫的，而是可寫的點太多了，不知道怎么寫了。JDK 1.8 版本的 HashMap 實現(xiàn)上比之前版本要復(fù)雜的多，想弄懂眾多的細(xì)節(jié)難度還是不小的。僅自己弄懂還不夠，還要寫出來，難度就更大了，本篇文章基本上是在邊讀源碼邊寫的狀態(tài)下完成的。由于時間和能力有限，加之文章篇幅比較大，很難保證不出錯分析過程及配圖不出錯。如果有錯誤，希望大家指出來，我會及時修改，這里先謝謝大家。
好了，本文就到這里了，謝謝大家的閱讀！
參考
JDK 源碼中 HashMap 的 hash 方法原理是什么？- 知乎
Java 8系列之重新認(rèn)識HashMap - 美團(tuán)技術(shù)博客
python內(nèi)置的hash函數(shù)對于字符串來說，每次得到的值不一樣？- 知乎
Java中HashMap關(guān)鍵字transient的疑惑 - segmentFault
本文在知識共享許可協(xié)議 4.0 下發(fā)布，轉(zhuǎn)載請注明出處
作者：coolblog
為了獲得更好的分類閱讀體驗，
請移步至本人的個人博客：http://www.coolblog.xyz
本作品采用知識共享署名-非商業(yè)性使用-禁止演繹 4.0 國際許可協(xié)議進(jìn)行許可。
