可以搜索微信公眾號【Jet 與編程】查看更多精彩文章
原文發(fā)布于自己的博客平臺【http://www.jetchen.cn/analysis-hashmap/】
HashMap 這個數(shù)據(jù)結(jié)構(gòu)，不管是日常開發(fā)，還是求職面試诈皿，它始終都是所有 Java 程序員繞不開的宿命，所以還是決定寫篇文章來詳細(xì)剖析下 HashMap 這個數(shù)據(jù)結(jié)構(gòu)，探探期間到底有多少奧秘演熟。
背景
很早的時候就想寫點關(guān)于數(shù)據(jù)結(jié)構(gòu)方面的文章，時隔多年，終于決定正式開始提筆了偏化，那就先從最熱門的 HashMap 開始吧。
HashMap 是 Java 程序中使用率最高的數(shù)據(jù)結(jié)構(gòu)之一镐侯，其主要用于處理鍵值對這種數(shù)據(jù)結(jié)構(gòu)侦讨。而且在 JDK 1.8 中對底層的實現(xiàn)進(jìn)行了優(yōu)化，比如引入了紅黑樹苟翻、優(yōu)化了擴(kuò)容機(jī)制等韵卤。
本文主要是基于 JDK 最常用的 1.8 版本來介紹，詳細(xì)分析了幾個最重要的參數(shù)和方法崇猫，比如索引的計算沈条、數(shù)組的擴(kuò)容、put() 方法等诅炉，末尾也會稍微對比下 1.8 和 1.7 版本之間的差異蜡歹。
簡介
特點
HashMap 繼承自 Map，有如下特點：
- 存儲 key - value 類型結(jié)構(gòu)涕烧，數(shù)據(jù)類型不限制
- 根據(jù) key 的 hashcode 值進(jìn)行存儲數(shù)據(jù)
- 最多只允許一條記錄的鍵(key)為 null（對 value 值不約束）
- 它是無序的（其實一見 hash 我們便知道了）
- 查詢效率很高
- 它是線程不安全的（要線程安全月而，可以使用 Collections 的 synchronizedMap，或者使用更加推薦的 ConcurrentHashMap）
它還有一些常見的兄弟姐妹议纯，比如 LinkedHashMap父款、TreeMap、Hashtable瞻凤，本文就不進(jìn)行對比介紹了憨攒。
基本結(jié)構(gòu)
HashMap 的結(jié)構(gòu)，是數(shù)組+鏈表+紅黑樹的結(jié)構(gòu)阀参，草圖可以見下圖浓恶。
紅黑樹是在 JDK1.8 版本才引入的，目的是加快鏈表的查詢效率
從上圖可看出结笨，HashMap 底層是一個哈希桶數(shù)組，名為 table，數(shù)組內(nèi)存儲的是基于 Node 類型的數(shù)據(jù)炕吸，所以伐憾，這個 Node 甚為關(guān)鍵，下文會詳解赫模。
然后同一個數(shù)組所以的位置可以存儲多個 Node树肃，并以鏈表或紅黑樹的形式來實現(xiàn)，所以很容易猜到瀑罗，既然是鏈表胸嘴，那么每個 Node 必然會記錄下一個 Node。但是如果鏈表很長斩祭，那查詢效率便會降低劣像，所以自 JDK1.8 開始便引入了紅黑樹，即當(dāng)鏈表長度超過 8 的時候摧玫，鏈表便會轉(zhuǎn)為紅黑樹耳奕，另外，當(dāng)鏈表長度小于 6 的時候诬像，會從紅黑樹轉(zhuǎn)為鏈表屋群。
鏈地址法
HashMap 是使用哈希表來存儲數(shù)據(jù)的。哈希表為了解決沖突坏挠，一般有兩種方案：開放地址法 和 鏈地址法芍躏。
開放地址法：哈希完后如果有沖突，則按照某種規(guī)則找到空位插入
HashMap 采用的便是 鏈地址法降狠，即在數(shù)組的每個索引處都是一個鏈表結(jié)構(gòu)对竣，這樣就可以有效解決 hash 沖突。
當(dāng)兩個 key 的 hash 值相同時喊熟，則會將他們至于數(shù)組的同一個位置處柏肪，并以鏈表的形式呈現(xiàn)。
但是如果大部分的數(shù)據(jù)都集中在了數(shù)組中的同一索引處芥牌，而其余索引處的數(shù)據(jù)比較少烦味，即分配不均衡，則說明哈希碰撞較多壁拉。
所以為了提高 HashMap 的存取效率谬俄，我們需要將數(shù)據(jù)盡可能多地分散到數(shù)組中去，即減少哈希碰撞弃理，為了達(dá)到這一目的溃论，最直接的方案便是改善 hash 算法，其次是擴(kuò)大哈希桶數(shù)組的大卸徊（擴(kuò)容）钥勋，在下文會詳細(xì)介紹炬转。
字段和屬性
一些默認(rèn)參數(shù)
// 默認(rèn)的初始容量為 16 （PS：aka 應(yīng)該是 as know as）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量（容量不夠時需要擴(kuò)容）
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認(rèn)的負(fù)載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 鏈表長度為 8 的時候會轉(zhuǎn)為紅黑樹
static final int TREEIFY_THRESHOLD = 8;
// 長度為 6 的時候會從紅黑樹轉(zhuǎn)為鏈表
static final int UNTREEIFY_THRESHOLD = 6;
// 只有桶內(nèi)數(shù)據(jù)量大于 64 的時候才會允許轉(zhuǎn)紅黑樹
static final int MIN_TREEIFY_CAPACITY = 64;
初始容量是 16，可以擴(kuò)容算灸，但是擴(kuò)容之后的容量扼劈，也是 2 的冪次方，比如 32菲驴、64荐吵，why？這里面涉及到很多巧妙的設(shè)計赊瞬，下文介紹 resize() 方法的時候會詳細(xì)介紹先煎。
另外，我們解釋下 MIN_TREEIFY_CAPACITY巧涧，雖然說當(dāng)鏈表長度大于 8 的時候薯蝎，鏈表會轉(zhuǎn)為紅黑樹，但是也是需要滿足桶內(nèi)存儲的數(shù)據(jù)量大于上述這個參數(shù)的值褒侧，否則不僅不會轉(zhuǎn)紅黑樹良风，反而會進(jìn)行擴(kuò)容操作。
比如下面這段代碼是判斷是否要將鏈表轉(zhuǎn)為紅黑樹闷供，乍看烟央，只是將鏈表長度和 UNTREEIFY_THRESHOLD 進(jìn)行對比，其實不然歪脏，點開 treeifyBin(tab, hash) 這個方法疑俭，我們便可以看到，如果此時桶數(shù)組內(nèi)的數(shù)據(jù)量小于 MIN_TREEIFY_CAPACITY婿失，則不會將鏈表轉(zhuǎn)紅黑樹钞艇，而是進(jìn)行擴(kuò)容操作，見下圖：
一些重要的字段
// Map 中存儲的數(shù)據(jù)量豪硅，即 key-value 鍵值對的數(shù)量
transient int size;
// HashMap 內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)哩照，即新增、刪除數(shù)據(jù)的時候都會記錄懒浮，
// 注意：修改某個 key 的值飘弧，并不會改變這個 modCount
transient int modCount;
// 重點，代表最多能容納的數(shù)據(jù)量
// 即最多能容納的 key-value 鍵值對的數(shù)量
int threshold;
// 負(fù)載因子砚著，默認(rèn)為 0.75
// 注意次伶，這個值是可以大于 1 的
final float loadFactor;
其中有兩個參數(shù)需要注意一下，一個是 threshold稽穆，還有一個是 loadFactor冠王。
threshold 代表最多能容納的 Node 數(shù)量，一般 threshold = length * loadFactor舌镶，也就是說要想 HashMap 能夠存儲更多的數(shù)據(jù)（即獲得較大的 threshold）柱彻，有兩種方案豪娜，一種是擴(kuò)容（即增大數(shù)組長度 length），另一種便是增大負(fù)載因子绒疗。
threshold 和數(shù)組長度不是一回事哦
0.75 這個默認(rèn)的負(fù)載因子的值是基于時間和空間考慮而得的一個比較平衡的點侵歇，所以負(fù)載因子我們一般不去調(diào)整，除非有特殊的需求：
- 比如 以空間換時間吓蘑，意思是如果內(nèi)存比較大，并且需要有較高的存取效率坟冲，則可以適當(dāng)降低負(fù)載因子磨镶，這樣做的話，就會減小哈希碰撞的概率健提。
- 再比如 以時間換空間琳猫，意思是如果內(nèi)存比較小，并且接受適當(dāng)減小存取效率私痹，則可以適當(dāng)調(diào)大負(fù)載因子脐嫂，哪怕大于 1，這樣做的話紊遵，就會增大哈希碰撞的概率账千。
關(guān)于 0.75 這個負(fù)載因子的詳細(xì)的解釋，需要建立數(shù)學(xué)模型來分析暗膜，由于鄙人才疏學(xué)淺匀奏，暫不進(jìn)行討論。
Node<K,V>
HashMap 底層是一個 Node[] table学搜，所以 Node 是一個很重要的數(shù)據(jù)結(jié)構(gòu)娃善。
Node 實現(xiàn)了 Entry 接口，所以瑞佩，Node 本質(zhì)上就是一個 Key-Value 數(shù)據(jù)結(jié)構(gòu)聚磺。
static class Node<K,V> implements Map.Entry<K,V> {
// key 的 hash 值
final int hash;
final K key;
V value;
// 記錄下一個 Node
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {...}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {...}
public final V setValue(V newValue) {...}
public final boolean equals(Object o) {...}
}
構(gòu)造函數(shù)
總共有四個構(gòu)造函數(shù)，依次來講解下炬丸。
HashMap()
構(gòu)造一個空的 HashMap瘫寝，初始容量為 16，負(fù)載因子為 0.75
// 構(gòu)造一個空的 HashMap御雕，初始容量為 16矢沿，負(fù)載因子為默認(rèn)值 0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
HashMap(int initialCapacity)
構(gòu)造一個空的 HashMap，并指定初始化容量酸纲，負(fù)載因子為默認(rèn)的 0.75捣鲸。
構(gòu)造函數(shù)內(nèi)部會調(diào)用下文緊接著講到的第三種構(gòu)造函數(shù)。
// 構(gòu)造一個空的 HashMap闽坡，并指定初始化容量栽惶，負(fù)載因子采用默認(rèn)的 0.75
public HashMap(int initialCapacity) {
// 調(diào)用另一個構(gòu)造函數(shù)
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
HashMap(int initialCapacity, float loadFactor)
構(gòu)造一個空的 HashMap愁溜，并指定初始化容量，指定負(fù)載因子外厂。
// 構(gòu)造一個空的 HashMap冕象，并指定初始化容量，指定負(fù)載因子
public HashMap(int initialCapacity, float loadFactor) {
// 初始容量不為負(fù)數(shù)
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
// 初始容量大于最大值時汁蝶，則取最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 負(fù)載因子不能小于 0渐扮，并且必須是數(shù)字，否則拋異常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
// 最大容量 MAXIMUM_CAPACITY 為 1 << 30
}
構(gòu)造函數(shù)中會進(jìn)行一系列的參數(shù)判斷掖棉，并且會進(jìn)行初始化操作墓律。
- 如果初始容量小于 0，或者負(fù)載因子小于 0 或不為數(shù)字時幔亥，會拋出
IllegalArgumentException異常耻讽。 - 如果初始容量大于最大值（2^30），則會使用最大容量帕棉。
- 設(shè)置 threshold针肥，直接調(diào)用
tableSizeFor()方法，該方法會返回一個大于等于指定容量的 2 的冪次方的整數(shù)香伴，例如傳入 6慰枕，則會返回 8。
tableSizeFor()方法的詳細(xì)解釋會放到下文來講解瞒窒。另外捺僻，直接將得到的值賦給
threshold，難道不是應(yīng)該是這樣的操作嗎崇裁？this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;, 其實不然匕坯，我們再看一眼源碼，會發(fā)現(xiàn)初始化的動作放在了 put 操作中拔稳。
HashMap(Map<? extends K, ? extends V> m)
構(gòu)造一個非空的 HashMap葛峻，保證初始化容量能夠完全容下傳進(jìn)來的 Map，另外巴比，負(fù)載因子使用的是默認(rèn)值 0.75术奖。
// 構(gòu)造一個非空的 HashMap，指定了默認(rèn)的負(fù)載因子 0.75
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 將 Map 中的 key-value 賦值到新的 Map 中去
putMapEntries(m, false);
}
putMapEntries() 方法是將傳遞進(jìn)來的 Map 中的數(shù)據(jù)全都存入到當(dāng)前的 HashMap 中去轻绞，方法的詳解見下文采记。
關(guān)鍵方法
tableSizeFor(int cap)
顧名思義，初始化桶數(shù)組的大小政勃。
該方法的作用是返回一個大于等于傳入的參數(shù)的數(shù)值唧龄，并且返回值會滿足以下兩點：
- 返回值是 2 的冪次方
- 返回值是最接近傳入的參數(shù)的值
比如：傳入 5，則返回 8奸远；傳入 8既棺，則返回 8讽挟；
這個方法的設(shè)計是很令人驚嘆的，十分巧妙丸冕，除了敬仰還是敬仰耽梅。
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;
}
2 的冪次方有個特點，就是它的字節(jié)碼除了最高位是 1胖烛，其余全是 0眼姐。
比如 2，字節(jié)碼為：10洪己，最高位為 1妥凳，其余為 0
再比如16，字節(jié)碼為：10000答捕，最高位為 1，其余為 0
所以方法內(nèi)使用了大量的 “或運(yùn)算”和 “右移”操作屑那，目的是保證從最高位起的每個 bit 都是 1拱镐。
- 首行
int n = cap - 1;的作用，是為了防止傳入的參數(shù)本身就是一個 2 的冪次方持际，否則會返回兩倍于參數(shù)的值沃琅； -
n |= n >>> 1;的作用，是保證倒數(shù)第二個高位也是 1蜘欲，下面的代碼類似益眉。 - 最后一行之前，得到的數(shù)類似 0000 1111 這種從第一個高位起全是 1姥份，這樣只要加了 1郭脂，則返回的數(shù)值必然是 2 的冪次方。
詳細(xì)的計算過程詳解見下圖：
putMapEntries(Map<? extends K, ? extends V> m, boolean evict)
該方法是將參數(shù) m 中的所有數(shù)據(jù)存入到當(dāng)前的 HashMap 中去澈歉，比如在上文提到的第四種構(gòu)造函數(shù)便調(diào)用了此方法展鸡。
此方法還是比較簡單的，下文代碼中都注釋埃难，其中涉及到的兩個關(guān)鍵方法 resize() 和 putVal() 方法莹弊，作用分別為擴(kuò)容和賦值，下文再詳細(xì)介紹這兩個方法涡尘。
// 將參數(shù) m 中的所有元素存入到當(dāng)前的 HashMap 中去
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 獲取 m 中的參數(shù)個數(shù)（key-value 的數(shù)量）
int s = m.size();
if (s > 0) {
// 判斷 table 是否被初始化過忍弛，否則初始化一遍。（PS：table 是在 put 操作的時候進(jìn)行初始化的考抄，所以如果當(dāng)前的 HashMap 沒有進(jìn)行過 put 操作细疚，則當(dāng)前的 table 并不會被初始化）
if (table == null) { // pre-size
// 根據(jù)傳進(jìn)來的 map 的元素數(shù)量來計算當(dāng)前 HashMap 需要的容量
float ft = ((float)s / loadFactor) + 1.0F;
// 計算而得的容量是不能大于最大容量的
int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
// 將計算而得的容量賦值給 threshold，前提是大于當(dāng)前容量（即不會減小當(dāng)前的 HashMap 的容量）
if (t > threshold)
// 將容量轉(zhuǎn)換為最近的 2 的 冪次方
threshold = tableSizeFor(t);
}
// table 不為空座泳，即已經(jīng)初始化過了惠昔，
// 如果 m 中的元素數(shù)量超過了當(dāng)前 HashMap 的容量幕与，則要進(jìn)行擴(kuò)容
else if (s > threshold)
resize();
// 遍歷 m 的每個元素，將它的 key-value 插入到當(dāng)前的 HashMap 中去
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
// 插入數(shù)據(jù)（注意镇防，為什么不是 put() 呢啦鸣，因為 put() 其實也是調(diào)用的 putVal() 方法）
putVal(hash(key), key, value, false, evict);
}
}
}
hash(Object key)
HashMap 中的 hash 算法，是將 key 進(jìn)行 hashCode 計算得到 h来氧，然后將 h 的高16位與低16位進(jìn)行異或運(yùn)算诫给。
這樣做是從速度、質(zhì)量等多方面綜合考慮的啦扬，而且將高位和低位進(jìn)行混合運(yùn)算中狂，這樣是可以有效降低沖突概率的。
另外扑毡，高位是可以保證不變的胃榕，變的是低位瞄摊，并且低位中摻雜了高位的信息换帜，最后生成的 hash 值的隨機(jī)性會增大蹲嚣。
下圖舉例介紹異或計算（例如 h 為 467,926,597）：
從上圖中也看出，高位的數(shù)字是不變的。
// (h = key.hashCode()) ^ (h >>> 16);
static final int hash(Object key) {
int h;
// 高 16 位與低 16 位進(jìn)行異或運(yùn)算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
另外换淆，hash() 的作用是根據(jù) key 計算一個 hash 數(shù)值，然后根據(jù)這個 hash 數(shù)值計算得到數(shù)組的索引 i蛋哭，基于這個索引我們才能進(jìn)行相關(guān)的增刪改查操作叛本，所以這個索引甚是關(guān)鍵来候。
計算公式為：i = hash(key) & (n-1)，即下面這個方法转质，但是這個下面這個方法僅限 1.8 以前的版本：
// jdk1.7 的源碼日矫，jdk1.8 沒有這個方法，但是原理一樣
static int indexFor(int h, int length) {
// 取模運(yùn)算
return h & (length-1);
}
這里又是一個很精妙的設(shè)計缔逛，一般情況下，我們要獲取索引 i敦冬，最常用的計算方式是取模運(yùn)算：hash % length，但是此處卻使用的是：hash & （length-1）萌庆，妙哉妙哉。
為什么要這么做呢彭则？因為 '%' 操作相對于位運(yùn)算是比較消耗性能的俯抖，所以采用了奇淫技巧 '&' 運(yùn)算凛捏。但是為什么結(jié)果是和取模運(yùn)算是一致的呢坯癣？其實還是因為table的 length 的問題瓶盛。
我們上文提到過，HashMap 的長度 length 始終是 2 的冪次方示罗，這個是關(guān)鍵惩猫，所以才會有這種結(jié)果，簡單分析見下圖：
使用 & 位運(yùn)算替代常規(guī)的 % 取模運(yùn)算蚜点，性能上提高了很多轧房，這個是 table 如此設(shè)計數(shù)組長度的優(yōu)勢之一，另一個很大的優(yōu)勢是在擴(kuò)容的時候绍绘，下文會分析奶镶。
resize()
resize() 是一個很重要的方法，作用是擴(kuò)容陪拘，從而使得 HashMap 可以存儲更多的數(shù)據(jù)厂镇。
因為當(dāng)我們不斷向 HashMap 中添加數(shù)據(jù)時，它總會超過允許存儲的數(shù)據(jù)量上限左刽，所以必然會經(jīng)歷 擴(kuò)容 這一步操作捺信，但是 HashMap 底層是一個數(shù)組，我們都知道數(shù)組是無法增大容量的欠痴，所以 resize 的過程其實就是新建一個更大容量的數(shù)組來存儲當(dāng)前 HashMap 中的數(shù)據(jù)迄靠。
resize() 方法是很精妙的，我們就一起來看下 JDK1.8 的源碼吧斋否。
final Node<K,V>[] resize() {
// 當(dāng)前 table
Node<K,V>[] oldTab = table;
// 當(dāng)前的 table 的大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 當(dāng)前 table 的 threshold梨水，即允許存儲的數(shù)據(jù)量閥值
int oldThr = threshold;
// 新的 table 的大小和閥值暫時初始化為 0
int newCap, newThr = 0;
// ① 開始計算新的 table 的大小和閥值
// a、當(dāng)前 table 的大小大于 0茵臭，則意味著當(dāng)前的 table 肯定是有數(shù)據(jù)的
if (oldCap > 0) {
// 當(dāng)前 table 的大小已經(jīng)到了上線了疫诽，還咋擴(kuò)容，自個兒繼續(xù)哈希碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 新的 table 的大小直接翻倍，閥值也直接翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// b奇徒、當(dāng)前的 table 中無數(shù)據(jù)雏亚，但是閥值不為零，說明初始化的時候指定過容量或者閥值摩钙，但是沒有被 put 過數(shù)據(jù)罢低，因為在上文中有提到過，此時的閥值就是數(shù)組的大小胖笛，所以直接把當(dāng)前的閥值當(dāng)做新 table 的數(shù)組大小即可
// 回憶一下：threshold = tableSizeFor(t);
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// c网持、這種情況就代表當(dāng)前的 table 是調(diào)用的空參構(gòu)造來初始化的，所有的數(shù)據(jù)都是默認(rèn)值长踊，所以新的 table 也只要使用默認(rèn)值即可
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的閥值是 0功舀，那么就簡單計算一遍就行了
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// ② 初始化新的 table
// 這個 newTab 就是新的 table，數(shù)組大小就是上面這一堆邏輯所計算出來的
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 遍歷當(dāng)前 table身弊，處理每個下標(biāo)處的 bucket辟汰，將其處理到新的 table 中去
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 釋放當(dāng)前 table 數(shù)組的對象引用（for循環(huán)后，當(dāng)前 table 數(shù)組不再引用任何對象）
oldTab[j] = null;
// a阱佛、只有一個 Node帖汞，則直接 rehash 賦值即可
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// b、當(dāng)前的 bucket 是紅黑樹凑术，直接進(jìn)行紅黑樹的 rehash 即可
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// c翩蘸、當(dāng)前的 bucket 是鏈表
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍歷鏈表中的每個 Node，分別判斷是否需要進(jìn)行 rehash 操作
// (e.hash & oldCap) == 0 算法是精髓淮逊，充分運(yùn)用了上文提到的 table 大小為 2 的冪次方這一優(yōu)勢鹿鳖，下文會細(xì)講
do {
next = e.next;
// 根據(jù) e.hash & oldCap 算法來判斷節(jié)點位置是否需要變更
// 索引不變
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原 bucket 位置的尾指針不為空(即還有 node )
if (loTail != null) {
// 鏈表末尾必須置為 null
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
// 鏈表末尾必須置為 null
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
好了，下面我們就介紹下上面的源碼中提到的計算索引的操作壮莹，即判斷 if ((e.hash & oldCap) == 0)。
下圖展示的是擴(kuò)容前和擴(kuò)容后的計算索引的方法姻檀，主要關(guān)注紅色框中的內(nèi)容命满。這種方案是沒問題的，但是之前我們提到绣版，table 的大小為 2 的冪次方胶台，這什么要這么設(shè)計呢，期間的又一個奧秘便體現(xiàn)在此杂抽，請看圖中的備注诈唬。
既然擴(kuò)容后每個 key 的新索引的生成規(guī)則是固定有規(guī)律的，即只有兩種形式缩麸，要么不變 i铸磅，要么增加原先的數(shù)組大小的量（i+n），所以我們其實并不需要真的去計算每個 key 的索引，而只需要判斷索引是否不變即可阅仔。所以此處巧妙地使用了 (e.hash & oldCap) == 0 這個判斷吹散，著實精妙，計算的細(xì)節(jié)過程看下面的圖即可八酒。
put(K key, V value)
此處介紹的是 putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)空民，因為 put() 其實就是直接調(diào)用的 putVal()；
put() 方法是 HashMap 中最常用的方法之一羞迷，我們先大體關(guān)注下 put() 方法的流程界轩，文字就暫不贅述了，看下圖便很清晰了：
下面簡單分析下源碼：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 參數(shù) onlyIfAbsent衔瓮，true：不修改已存在的 value浊猾，false：已存在則進(jìn)行修改
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// ① 如果當(dāng)前 table 為空則進(jìn)行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash 計算得到索引 i，算法在上文有提到报辱，然后查看索引處是否有數(shù)據(jù)
// ② 如果沒有數(shù)據(jù)与殃，則新建一個新的 Node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 索引處有數(shù)據(jù)
else {
Node<K,V> e; K k;
// ③ 索引處的第一個 Node 的 key 和參數(shù) key 是一致的，所以直接修改 value 值即可（修改的動作放在下面）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// ④ 索引處的 bucket 是紅黑樹碍现，按照紅黑樹的邏輯進(jìn)行插入或修改
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// ⑤ 索引處的 bucket 是鏈表
else {
// 遍歷鏈表上面的所有 Node
for (int binCount = 0; ; ++binCount) {
// 索引處的 Node 為尾鏈
if ((e = p.next) == null) {
// 直接新建一個 Node 插在尾鏈處
p.next = newNode(hash, key, value, null);
// 判斷是否需要轉(zhuǎn)換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 鏈表轉(zhuǎn)換為紅黑樹幅疼，此方法在上文中也有介紹
treeifyBin(tab, hash);
break;
}
// 當(dāng)前 Node 的 key 值和參數(shù) key 是一致的，即直接修改 value 值即可（修改的動作放在下面）
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 找到了相同 key 的 Node昼接，所以進(jìn)行修改 vlaue 值即可
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 修改 value 值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 修改操作爽篷，直接 return 結(jié)束掉代碼邏輯
return oldValue;
}
}
// 記錄結(jié)構(gòu)發(fā)生變化的次數(shù)
++modCount;
// ⑥ 判斷是否需要擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
// 新增的 Node，返回 null
return null;
}
get(Object key)
此處介紹的是 getNode(int hash, Object key慢睡，因為 get() 其實就是直接調(diào)用的 getNode()逐工；
get() 方法也是比較簡單的，就是根據(jù) key 獲取 table 的索引漂辐，然后再分情況查找擁有相同 key 的 Node泪喊；
源碼大致如下：
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)前 table 不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判斷索引處的第一個 Node 的 key 值是否和參數(shù) key 相同，相同則返回該 Node
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 索引處的第一個 Node 不是想要的髓涯，則接著查 next
if ((e = first.next) != null) {
// bucket 是紅黑樹結(jié)構(gòu)
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// bucket 是鏈表結(jié)構(gòu)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
JDK1.8 VS JDK1.7
1.7 和 1.8 之間的區(qū)別袒啼，最最主要的是如下三方面，當(dāng)然纬纪，鄙人覺得這三點的變化可以算是比較成功的優(yōu)化蚓再。
- 擴(kuò)容后 Node 索引的計算方式不同。上文提到包各，由于 table 大小的這種神奇的設(shè)計摘仅，所以擴(kuò)容時計算索引的時候，1.8 中只需要簡單使用 & 運(yùn)算來判斷是否為 0 即可问畅，并不需要像 1.7 一樣每次都是用 & 運(yùn)算來計算出索引值娃属。
- 1.8 中引入了紅黑樹結(jié)構(gòu)六荒。上文也提到了，當(dāng)鏈表長度大于 8 的時候會轉(zhuǎn)換為紅黑樹膳犹，但是 1.7 中是數(shù)組+鏈表的組合恬吕。
- 1.8 中采用的是尾插法，而 1.7 中采用的是頭插法须床。比如擴(kuò)容的時候铐料，頭插法會使鏈表上 Node 的順序調(diào)轉(zhuǎn)，而尾插法則不會豺旬，另外钠惩，頭插法也會造成環(huán)形鏈死循環(huán)等問題，本文就不深討了族阅。
其它
HashMap 是線程不安全的篓跛，因為它是允許多線程同時操作同一個數(shù)組的，比如 put()坦刀，比如 resize()愧沟，這些都會造成數(shù)據(jù)異常甚至死循環(huán)。
所以要使用線程安全的 Map 的時候鲤遥，可以使用 HashTable沐寺，但是這個不推薦，或者使用自 JDK1.8 開始引入的 Concurrent 包中的 ConcurrentHashMap盖奈，這個是比較推薦的混坞，具體的介紹就放到下文再說吧。
參考了美團(tuán)的技術(shù)博客：傳送門
