0、前言
HashMap是Java中最常用的集合之一，相信大家都使用過，可是你對他了解嗎？HashMap存儲的數(shù)據(jù)結(jié)構(gòu)是怎樣的？他是如何進行工作的？HashMap的get和put內(nèi)部的工作原理？如何避免hash沖突以及擴容的機制是怎樣的？網(wǎng)上也有很多文章對HashMap的源碼總結(jié)和分析，我寫這篇文章，主要還是為了記錄自己閱讀后的一點感悟，如不對的地方望大家指正！本文基于JDK1.8。
1、HashMap概述
HashMap是一個散列表，他存儲的內(nèi)容是鍵值對(key-value)映射，每個節(jié)點是一個Node類。HashMap實現(xiàn)了Map接口，因此擁有Map的一系列操作，如：get、put、remove...等方法，而HashMap對此也進行了重寫。HashMap允許null的key和value，但只允許一條記錄的鍵為null，可以允許多條記錄的值為null。HashMap是非線程安全的(后面會闡述為啥)，可以使用Collections.synchronizedMap來包裝HashMap，使其具備線程安全，或者使用ConcurrentHashMap。
2、HashMap的存儲結(jié)構(gòu)
HashMap底層是基于數(shù)組+鏈表+紅黑樹(JDK1.8后增加了紅黑樹部分)來實現(xiàn)的。
圖中的HashTable也就是HashMap數(shù)組。那么HashMap是怎么存儲數(shù)據(jù)的呢？HashMap通過計算key的hash值與(n-1)進行二進制&操作(n為HashMap數(shù)組的長度)即hash&(n-1)，得到HashMap數(shù)組的下標，從而確定存儲位置。當(dāng)存儲的元素過多時，就會存在相同hash值的元素，也就說不同元素key的hash&(n-1)得到相同的存儲位置，這時就出現(xiàn)了hash沖突。學(xué)過數(shù)據(jù)結(jié)構(gòu)的同學(xué)都知道，解決hash沖突的方法有多種，HashMap是通過鏈表的方式來解決沖突的。當(dāng)鏈表的長度大于8時，鏈表就會轉(zhuǎn)成紅黑樹結(jié)構(gòu)(感興趣的朋友可以自行了解)，當(dāng)HashMap實際存儲的元素個數(shù)超過了最大容量threshold時，HashMap就會進行擴容，對已存儲的元素進行再hash重新存儲(后面會詳細闡述擴容及再hash過程)。
正是由于HashMap是采用鏈表來解決沖突的，當(dāng)線程A和線程B同時進行put時，計算出了相同的hash值對應(yīng)的相同數(shù)組位置，兩個線程會同時得到頭結(jié)點，A將數(shù)據(jù)寫入頭結(jié)點后，B也寫入，那B的寫入操作就會覆蓋A的寫入從而導(dǎo)致A寫入的數(shù)據(jù)丟失。當(dāng)A去get(K k)獲取時得到的不是put進去的值。所以HashMap是非線程安全的。
HashMap是非線程安全的 - 在多線程put情況下，有可能在容量超過擴容閾值時進行rehash，因為HashMap為避免尾部遍歷，在鏈表插入時使用的是頭插法，多線程場景下，可能會產(chǎn)生死循環(huán)。
3、HashMap核心方法分析
(1) 解釋幾個關(guān)鍵變量
/**
* HashMap默認容量大小，必須為2的整數(shù)次冪
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* HashMap的最大容量為2的30次冪
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* HashMap的默認加載因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 鏈表轉(zhuǎn)成紅黑樹的閾值。即在當(dāng)鏈表的長度大于等于這個值的時候，將鏈表轉(zhuǎn)成紅黑樹
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 紅黑樹轉(zhuǎn)為鏈表的閾值。即在哈希表擴容時，如果發(fā)現(xiàn)鏈表長度小于6,則會由紅黑樹重新退化為鏈表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* HashMap的最小樹形化容量
* 為了避免進行擴容、樹形化選擇的沖突，這個值不能小于 4 * TREEIFY_THRESHOLD
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* HashMap數(shù)組，初始化分配的時候，數(shù)組的長度總是2的冪
*/
transient Node<K,V>[] table;
/**
* HashMap實際存儲的key-value鍵值對元素個數(shù)
*/
transient int size;
/**
* 用來記錄HashMap內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)，例如put新的key-value，如果某個key對應(yīng)的value被覆蓋不屬于結(jié)構(gòu)變化
*/
transient int modCount;
/**
* HashMap擴容的閾值，表示HashMap所能存儲的最大元素個數(shù)，當(dāng)size >= threshold時，HashMap就會擴容，threshold = HashMap數(shù)組的容量大小 * 加載因子(loadFactor)
*/
int threshold;
/**
* 加載因子，默認值是0.75
*/
final float loadFactor;
Node<K,V>[] table 是存放存放元素的地方，是Node類的數(shù)組，當(dāng)?shù)谝淮蜗騂ashMap put元素時，會初始化默認長度(即 DEFAULT_INITIAL_CAPACITY默認值為16)。Node類包含四個屬性，hash值、key、value、next下一節(jié)點的引用。
size記錄的是HashMap實際存儲的元素個數(shù)，也就是鍵值對的數(shù)量，put新的元素時會加1，remove元素時減1。
modCount記錄的是HashMap內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)，如put新的元素時，modCount數(shù)量會加1，put的時候如果key已經(jīng)存則value會進行覆蓋，不屬于結(jié)構(gòu)變化，modCount的值不改變。同樣的，如果進行remove操作引起結(jié)構(gòu)變化，則modCount數(shù)量也會加1。
threshold HashMap的擴容閾值也可以說是HashMap數(shù)組元素的裝填程度，計算方式為capacity(HashMap數(shù)組的長度) * loadFactor。由于首次向HashMap添加元素時，HashMap數(shù)組的長度初始化為16，故threshold與loadFactor有關(guān)，如果loadFactor設(shè)置越大，threshold就越大填滿的元素越多，擴容時機來的慢，毫無疑問空間利用率也越高，但hash沖突的概率也變高，如前面所說用鏈表來解決沖突，那么鏈表也會變得越長，導(dǎo)致查詢效率會變得更低；同樣的，如果loadFactor設(shè)置越小，threshold就越小填滿的元素越少，擴容時機來的快，空間利用率變低，但存儲的數(shù)據(jù)越稀疏，沖突就會減少，鏈表就不會太長，查詢效率更高。
舉個??理解一下：
假設(shè)HashMap數(shù)組的容量(即長度)為100，加載因子loadFactor為0.8，得到threshold為80，也就是HashMap存儲80個元素后才會進行擴容，在存儲過程中可能有很多key對應(yīng)相同的hash值，那么鏈表長度也就越長。如果加載因子loadFactor設(shè)置為0.1，threshold為10，也就是說HashMap存儲10個元素后就要開始擴容，而在這10個元素中出現(xiàn)hash沖突的概率要比上面的情況小的多，一旦擴容后，會重新計算hash確定存儲位置，這樣保證了鏈表長度不會太長，甚至就一個表頭元素，空間利用率很低，因為很多空間沒利用就擴容了。
那么問題來了，加載因子loadFactor既不能太大也不能太小，太大影響查詢效率，太小浪費存儲空間。加載因子loadFactor到底設(shè)置什么值比較合理呢？其實這是在"減少沖突"和"空間利用率"之間尋找一種平衡，系統(tǒng)默認加載因子為0.75，是JDK權(quán)衡時間和空間效率之后得到的一個相對優(yōu)良的數(shù)值，一般情況下我們無需修改。
(2) 構(gòu)造方法
HashMap有好幾個構(gòu)造方法，下面詳細分析一個比較重要的構(gòu)造方法：
public HashMap(int initialCapacity, float loadFactor) {
// 構(gòu)造時，如果傳遞的initialCapacity小于0，則會拋出參數(shù)不合法異常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 如果大于HashMap最大容量，則直接賦值最大容量值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 如果加載因子小于等于0，或者不是float類型的數(shù)，則會拋出異常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// tableSizeFor方法會計算擴容閾值
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
int n = cap - 1;
// 通過下面二進制的邏輯右移和或操作，最終得到的數(shù)一定是2的k次冪
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;
}
很多朋友可能不理解，tableSizeFor方法里面的二進制操作是怎么實現(xiàn)的？別急，現(xiàn)在我舉個??，看懂這個例子你就明白為啥了。
首先得明白n |= n >>> 1 這個運算是啥意思，表示的是n先邏輯右移一位(對二進制的位運算和移位運算不了解的朋友，建議先復(fù)習(xí)一下，不然會有點吃力)得到的值，再跟n進行|(或)運算，最后將得到的值賦給n。
假設(shè)給定的cap為19(隨機給的一個數(shù))，那么n = cap - 1也就是18的二進制為：
0000 0000 0001 0010
第一步操作：
0000 0000 0001 0010
>>>1 0000 0000 0000 1001 邏輯右移一位
|= 0000 0000 0001 1011 或運算并賦值
第二步操作：
0000 0000 0001 1011
>>>2 0000 0000 0000 0110 邏輯右移兩位
|= 0000 0000 0001 1111 或運算并賦值
第三步操作：
0000 0000 0001 1111
>>>4 0000 0000 0000 0001 邏輯右移四位
|= 0000 0000 0001 1111 或運算并賦值
......
可以看出，后面的右移8位和右移16位得到的值都是0000 0000 0001 1111。最后n+1后，值為32，即2的5次冪，其實得到這樣一個結(jié)論，經(jīng)過tableSizeFor方法得到值一定是2的k次冪。
我們再舉一個二進制大點的??，來驗證下：
0100 0110 0101 0110
第一步操作：
0100 0110 0101 0110
>>>1 0010 0011 0010 1011 邏輯右移一位
|= 0110 0111 0111 1111 或運算并賦值
第二步操作：
0110 0111 0111 1111
>>>2 0001 1001 1101 1111 邏輯右移兩位
|= 0111 1111 1111 1111 或運算并賦值
第三步操作：
0111 1111 1111 1111
>>>4 0000 0111 1111 1111 邏輯右移四位
|= 0111 1111 1111 1111 或運算并賦值
......
結(jié)果一目了然，n+1后最終還是2的k次冪。
(3) put方法
public V put(K key, V value) {
// 內(nèi)部調(diào)用putVal方法，調(diào)用這個方法之前會hash(key)，對key進行hash值的計算，后面會詳細闡述計算過程，暫且跳過
return putVal(hash(key), key, value, false, true); ①
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果HashMap數(shù)組是null，或是空，則進行resize()，也就是先擴容(暫且放下，后面會詳細闡述擴容原理)
if ((tab = table) == null || (n = tab.length) == 0)
// 將擴容后的HashMap數(shù)組長度值賦給n
n = (tab = resize()).length;
// 前面講HashMap存儲結(jié)構(gòu)的時，提到過通過(n - 1) & hash來確定存儲位置；如果HashMap數(shù)組這個位置的元素是null，則會在鏈表的表頭插入新節(jié)點
if ((p = tab[i = (n - 1) & hash]) == null) ②
tab[i] = newNode(hash, key, value, null);
else {
// 表頭元素不為null，則進行遍歷
Node<K,V> e; K k;
// 當(dāng)前節(jié)點的key已存在，則會將value值進行替換
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果表頭節(jié)點是紅黑樹節(jié)點類型，則調(diào)用紅黑樹putTreeVal方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 如果是鏈表，則遍歷鏈表，一個一個往下尋找是否已存在key的節(jié)點
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 找到鏈表結(jié)尾，沒找到，則創(chuàng)建一個新的節(jié)點
p.next = newNode(hash, key, value, null);
// 鏈表中新增一個節(jié)點后，如果鏈表長度大于等于TREEIFY_THRESHOLD時，則鏈表轉(zhuǎn)成紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 找到已存在key的節(jié)點，則退出循環(huán)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果找到了存在key的節(jié)點，則將value進行覆蓋
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// key在鏈表中已存在，返回覆蓋之前的value
return oldValue;
}
}
// HashMap內(nèi)部結(jié)構(gòu)發(fā)生變化
++modCount;
// 如果HashMap存儲的元素個數(shù)大于閾值，則進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
// 插入新的元素節(jié)點成功后，返回null
return null;
}
②處的(n - 1) & hash是用來確定存儲位置，同時也是用于解決hash沖突的，為什么要這么設(shè)計呢？試想一下我們怎樣把一個大于數(shù)組長度的位置，將其放入數(shù)組中？取模，對這個位置取模hash%n，在數(shù)據(jù)結(jié)構(gòu)中處理hash沖突也確實用到的是取模，得到的值肯定小于數(shù)組長度的值。但是取模是除法運算，效率很低，HashMap中通過(n - 1) & hash來代替取模，同樣可以達到均勻散列的效果，而且效率會高很多。當(dāng)HashMap數(shù)組的容量為2的整數(shù)次冪，(n - 1) & hash這是一個非常巧妙的設(shè)計。
例子??走起：
假設(shè)hash = 3，n = 16，則(n - 1) & hash = 3;
假設(shè)hash = 4，n = 16，則(n - 1) & hash = 4;
假設(shè)hash = 15，n = 16，則(n - 1) & hash = 15;
假設(shè)hash = 16，n = 16，則(n - 1) & hash = 0;
假設(shè)hash = 17，n = 16，則(n - 1) & hash = 1;
與取模運算達到同樣的效果，保證計算得到的下標值在HashMap數(shù)組索引范圍內(nèi)。
接下來，我們分析下HashMap數(shù)組容量為什么一定要滿足2的整數(shù)次冪。數(shù)組容量n為2的整數(shù)次冪，那么(n - 1) & hash相當(dāng)于hash%n，既可以保證散列均勻，也提高了效率；同時，n為2的整數(shù)次冪，(n - 1)必然是奇數(shù)，奇數(shù)的二進制最后一位是1，(n - 1) & hash計算出來的結(jié)果最后一位要么是0要么是1，也就是結(jié)果可能是偶數(shù)也有可能是奇數(shù)，這樣保證了散列的均勻性。如果n為奇數(shù)的話，(n - 1)最后一位必然是0，(n - 1) & hash計算出來的結(jié)果為偶數(shù)，也就是說只能得到HashMap數(shù)組偶數(shù)下標的位置，這樣的話HashMap中近一半的空間浪費掉了。
還是例子說明：
假設(shè)HashMap數(shù)組長度分別為16和17，現(xiàn)有兩個元素進行插入，對應(yīng)的hash值分別為5和6，(n-1)&hash的結(jié)果如下：
(n - 1) hash
0000 1111 & 0000 0101 = 0000 0101 (16 - 1)&5
0000 1111 & 0000 0110 = 0000 0110 (16 - 1)&6
--------------------------------------------------------
0001 0000 & 0000 0101 = 0000 0000 (17 - 1)&5
0001 0000 & 0000 0110 = 0000 0000 (17 - 1)&6
從上面例子可以看出當(dāng)HashMap數(shù)組長度為奇數(shù)時，計算出來為數(shù)組的同一位置，產(chǎn)生沖突，存儲的時候形成鏈表，查詢的時候就要遍歷鏈表，降低了查詢效率。而數(shù)組長度為偶數(shù)時，那么(n - 1)的每一位都是1，同hash值&操作時，得到的和原h(huán)ash的低位相同，加之①處hash(K key)方法對key的hashCode的進一步優(yōu)化，加入了高位計算，就使得只有相同的hash值的兩個值才會被放到數(shù)組中的同一個位置上形成鏈表，而且數(shù)據(jù)在數(shù)組上分布均勻，這樣查詢效率也高。
好了，現(xiàn)在我們回過頭來看看①處hash(K key)，是如何計算key的hash值？
// 計算hash
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看上面的方法邏輯是進行位運算重新計算hash值，有朋友不禁要問為什么不直接用key的hashCode作為hash值呢？這樣做有兩個好處：其一，我們知道在②處(n - 1)&hash過程中，hash值只有低位參與了運算，也就是說計算存儲位置跟hash的高位沒有關(guān)系。如果不經(jīng)過上述方法重新計算hash，而僅僅取key的hashCode作為hash值，讓低位參與運算，高位不參與運算的話，非常容易產(chǎn)生沖突，隨機性也會降低。異或操作的目的就是讓高位也參與運算，讓高位數(shù)據(jù)與低位數(shù)據(jù)進行異或，以此加大低位信息的隨機性，提高hash的散列性。還是舉個??看看：
1100 0010 0001 1101 1110 0100 0011 1101
>>>4 0000 1100 0010 0001 0000 1110 0100 0011
^= 1100 1110 0001 1100 1110 1010 0111 1110
可以看出，如果不進行異或操作，重新計算hash，而讓key的hashCode作為hash參與運算的話，兩者存儲位置一致，從而產(chǎn)生沖突。讓高位參與運算后，隨機性就加大了。
在Java中，hashCode方法產(chǎn)生的hash是int類型，32位。前16位為高位，后16位為低位，所以要右移16位。
除此之外，重新計算hash的另一個好處是可以增加hash的復(fù)雜度。當(dāng)我們重寫hashCode方法時，可能會寫出分布性不佳的hashCode方法，進而導(dǎo)致hash的沖突率比較高。通過移位和異或運算，可以讓hash變得更復(fù)雜，進而影響hash的分布性。這也就是為什么HashMap不直接使用key的hashCode作為hash的原因。
(4) get方法
get方法的實現(xiàn)思路：先計算hash值，(n-1)&hash計算出key在HashMap數(shù)組中的下標位置，取出頭結(jié)點，如果頭結(jié)點就是key存儲的元素，則取出并返回；如果不是頭結(jié)點，則判斷是否頭結(jié)點是否是紅黑樹節(jié)點，否則遍歷鏈表，直至找到。若不存key存儲的節(jié)點直接返回null。
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;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
(5) resize擴容方法
HashMap的擴容就是重新計算容量，當(dāng)HashMap數(shù)組無法存儲更多元素時，這是就需要進行擴容。擴容并不是擴大原HashMap數(shù)組的長度，況且java中的數(shù)組也無法自動擴容，而是新建一個容量是原來2倍的數(shù)組，把原數(shù)組中的元素重新計算hash存入新的數(shù)組中。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 獲取原HashMap數(shù)組的容量(長度)
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 如果原HashMap數(shù)組容量已達到最大值，無法再進行擴容，將閾值設(shè)為最大，返回并停止擴容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 否則，新的HashMap數(shù)組容量擴大2倍；如果原HashMap數(shù)組容量大于等于16，新數(shù)組的閾值也擴大2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
// 原HashMap閾值大于0&HashMap數(shù)組長度小于1，則將原HashMap閾值作為新數(shù)組的容量
newCap = oldThr;
else {
// 上述條件不滿足，初始化為默認值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 新HashMap的閾值為0，則對新閾值重新賦值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 創(chuàng)建容量為newCap的新HashMap數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 將新數(shù)組的引用賦值
table = newTab;
if (oldTab != null) {
// 如果是在已存在的HashMap數(shù)組基礎(chǔ)上擴容，則進行元素遷移
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 取出原HashMap數(shù)組中的每個元素,并賦值給臨時變量e
if ((e = oldTab[j]) != null) {
// 將原HashMap數(shù)組元素置為null
oldTab[j] = null;
if (e.next == null)
// 原HashMap數(shù)組該位置的元素只有頭結(jié)點，遷移至新數(shù)組同樣的位置
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 原HashMap數(shù)組該位置的元素不只一個元素，且是紅黑樹節(jié)點，則調(diào)用split方法
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 如果是鏈表，則進行遍歷
do {
next = e.next;
// 將原HashMap數(shù)組中每個鏈表e.hash & oldCap == 0的元素放入低位鏈表
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 將原HashMap數(shù)組中每個鏈表e.hash & oldCap == 1的元素放入高位鏈表
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
// 將低位鏈表元素存入“原處”，這個“原處”是根據(jù)新的hash&(newCap - 1)算出來的
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
// 將高位鏈表元素存入j + oldCap位置
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
直接看上面的代碼不好理解，畫個圖便于理解：
[0] -> (0)
[1] -> ( A
B C
D E F G
H I )
[2] -> (2) -> (6) -> (10) -> (14)
[3] -> (7)
圖中展示了HashMap三種存儲場景，只有一個元素、紅黑樹、鏈表。著重分析一下擴容時，鏈表重新hash存儲的過程，直接上圖
[0] [0]
[1] [1]
[2] -> (2) -> (6) -> (10) -> (14) ----> [2] -> (2) -> (10)
[3] [3]
[4]
[5]
[6] -> (6) -> (14)
[7]
鏈表上的元素是怎樣遷移的呢？主要看（e.hash & oldCap）也就是元素的hash值與原HashMap數(shù)組的容量進行與運算的結(jié)果。如果結(jié)果為0，則存放在原位置；如果不為0，則存放在j + oldCap（原HashMap數(shù)組的長度）的位置。
我們可以這么理解，擴容后其實就是在新HashMap數(shù)組中重新存儲原HashMap數(shù)組中的元素，hash&(2n - 1)來確定新數(shù)組的存儲位置。
擴容前
2 6 10 14
二進制 0000 0010 0000 0110 0000 1010 0000 1110
&(4-1) 0000 0011 0000 0011 0000 0011 0000 0011
= 0000 0010 0000 0010 0000 0010 0000 0010
擴容后
2 6 10 14
二進制 0000 0010 0000 0110 0000 1010 0000 1110
&(8-1) 0000 0111 0000 0111 0000 0111 0000 0111
= 0000 0010 0000 0110 0000 0010 0000 0110
從擴容前后計算存儲位置，我們似乎發(fā)現(xiàn)了什么，擴容前6&(4-1)= 0000 0010，擴容后6&(8-1) = 0000 0110，對比可見擴容后運算的結(jié)果中新增了一位1。同理2和10新增的一位是0，6和14新增的一位是1。因此我們只需要看看新增一位是1還是0，如果是0，存儲到新數(shù)組中索引不變，如果是1，存儲到新數(shù)組中的索引為原索引+oldCap。
(5) Fail-Fast機制
我們知道HashMap不是線程安全的，因此如果在使用迭代器的過程中有其他線程修改了HashMap，那么將拋出ConcurrentModificationException，這就是所謂fail-fast策略。這一策略在源碼中的實現(xiàn)是通過modCount變量來體現(xiàn)的，對HashMap內(nèi)容的修改引起結(jié)構(gòu)變化都將增加這個值，那么在迭代器初始化過程中會將這個值賦給迭代器的expectedModCount。
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
// 迭代器迭代過程中會判斷modCount跟expectedModCount是否相等，如果不相等表明有其他線程對HashMap進行了修改導(dǎo)致結(jié)構(gòu)發(fā)生了變化，拋出異常
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
4、小結(jié)
本文只分析了HashMap的部分核心源碼，闡述了自己的一些感悟和理解，當(dāng)然比如紅黑樹部分沒有展開講解，后續(xù)會放到TreeMap的分析當(dāng)中。最后給大家分享一個鏈接：HashMap添加和刪除動畫演示?？梢院苤庇^的看到HashMap添加和刪除數(shù)據(jù)的過程，幫助我們更好的理解HashMap。如有錯誤，歡迎指正，感激不盡!
