?在java語言中，HashMap是一個(gè)非常重要的數(shù)據(jù)結(jié)構(gòu)，它被廣泛用于存儲(chǔ)具有key-value映射關(guān)系的數(shù)據(jù)要门，HashMap提供了高效的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)key-value的映射钦铁；從HashMap的設(shè)計(jì)與實(shí)現(xiàn)中，我們可以學(xué)到很多巧妙的計(jì)算機(jī)思維殉疼，對(duì)我們?nèi)粘９ぷ髦羞M(jìn)行編碼及方案設(shè)計(jì)存在很高的參考價(jià)值梯浪，學(xué)習(xí)和掌握HashMap就成了非常有必要的一件事情了。
學(xué)習(xí)HashMap株依，有這么幾個(gè)關(guān)鍵問題需要搞明白：
HashMap的數(shù)據(jù)結(jié)構(gòu)是什么樣的驱证，不同jdk版本架構(gòu)是如何的；
HashMap關(guān)鍵屬性恋腕，屬性的含義及如何設(shè)置等問題抹锄；
HashMap的key-value插入流程是怎樣的；
HashMap的數(shù)據(jù)查詢流程是怎樣的；
HashMap的擴(kuò)容機(jī)制是怎么工作的伙单；
HashMap的數(shù)據(jù)更新流程是什么樣的（比如：刪除）获高；
HashMap的并發(fā)問題產(chǎn)生原因及正確的并發(fā)用法（比如并發(fā)環(huán)境下如何產(chǎn)生cpu 100%）；
搞明白這幾個(gè)關(guān)鍵問題吻育，HashMap就算是掌握得差不多了念秧，下面，從源碼級(jí)來分析一下這些關(guān)鍵問題的答案是什么布疼。
一摊趾、 HashMap的數(shù)據(jù)結(jié)構(gòu)
HashMap的數(shù)據(jù)結(jié)構(gòu)由數(shù)組+鏈表組成，從java 8開始游两，會(huì)新增紅黑樹這種數(shù)據(jù)結(jié)構(gòu)砾层，也就是在java8中，鏈表超過一定長(zhǎng)度后就會(huì)變?yōu)榧t黑樹贱案。
在下文的分析中肛炮，如果不是特別說明，都是指的是java 8中的HashMap宝踪。
二 侨糟、HashMap關(guān)鍵屬性
有幾個(gè)關(guān)鍵的屬性需要我們知道：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
默認(rèn)的table的大小，table的大小只能是2的冪次方瘩燥，這和HashMap的哈希槽尋址算法存在著很大的關(guān)系秕重，當(dāng)然，HashMap執(zhí)行resize的時(shí)候也會(huì)得益于這個(gè)table數(shù)組的冪次方大小的特性颤芬，這些問題稍后再分析悲幅；
/**
* 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;
table的最大長(zhǎng)度；
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
默認(rèn)的負(fù)載因子站蝠，負(fù)載因子用于擴(kuò)容汰具，當(dāng)HashMap中的元素?cái)?shù)量大于：capacity * loadFactor后，HashMap就會(huì)執(zhí)行擴(kuò)容流程菱魔。
/**
* 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;
當(dāng)鏈表的長(zhǎng)度超過一定長(zhǎng)度之和留荔，鏈表就會(huì)被升級(jí)為紅黑樹，用于解決因?yàn)楣Ｅ鲎卜浅?yán)重的情況下的數(shù)據(jù)查詢效率低下問題澜倦，最壞情況下聚蝶，如果沒有引入紅黑樹的情況下，get操作的時(shí)間復(fù)雜度將達(dá)到O(N)藻治，而引入紅黑樹碘勉，最壞情況下get操作的時(shí)間復(fù)雜度為O(lgN)；8是默認(rèn)的鏈表樹化閾值桩卵，當(dāng)某個(gè)hash槽內(nèi)的鏈表的長(zhǎng)度超過8之后验靡，這條鏈表將演變?yōu)榧t黑樹倍宾。
/**
* 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;
紅黑樹也有可能會(huì)降級(jí)為鏈表，當(dāng)在resize的時(shí)候胜嗓，發(fā)現(xiàn)hash槽內(nèi)的結(jié)構(gòu)為紅黑樹高职，但是紅黑樹的節(jié)點(diǎn)數(shù)量小于等于6的時(shí)候，紅黑樹將降級(jí)為鏈表辞州。
/**
* 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;
鏈表升級(jí)為紅黑樹還需要一個(gè)條件怔锌，就是table的長(zhǎng)度要大于64，否則是不會(huì)執(zhí)行升級(jí)操作的变过，會(huì)轉(zhuǎn)而執(zhí)行一次resize操作埃元。
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
table和上文中的結(jié)構(gòu)圖中的數(shù)組對(duì)應(yīng)。
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
下次數(shù)組擴(kuò)容閾值媚狰，這個(gè)值是通過：capacity * loadFactor計(jì)算出來的亚情，每次擴(kuò)容都會(huì)計(jì)算出下一次擴(kuò)容的閾值，這個(gè)閾值說的是元素?cái)?shù)量哈雏。
三第焰、 HashMap數(shù)據(jù)插入流程
下面來跟著源碼來學(xué)習(xí)一下HashMap的put操作流程：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
首先需要注意的是hash這個(gè)方法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
如果key是null第租，則hash的計(jì)算結(jié)構(gòu)為0屋谭，這里就有一個(gè)關(guān)鍵信息蚕脏，如果一個(gè)HashMap中存在key為null的entry生真，那么這個(gè)entry一定在table數(shù)組的第一個(gè)位置悬蔽，這是因?yàn)閔ash計(jì)算的結(jié)果直接影響了數(shù)據(jù)插入的hash槽位置奕筐，這一點(diǎn)稍后再看岛啸。
如果key不為null泪酱，則會(huì)拿key對(duì)象的hashCode來進(jìn)行計(jì)算派殷，這里的計(jì)算稱為“擾動(dòng)”，為什么要這樣操作呢墓阀？本質(zhì)上是為了降低哈希碰撞的概率毡惜，這里需要引出HashMap中定位哈希槽的尋址算法。
HashMap的table數(shù)組容量只能是2的冪次方斯撮，這樣的話经伙，2的冪次方的數(shù)有一個(gè)特性，那就是：hash & (len - 1) = hash % len勿锅，這樣帕膜，在計(jì)算entry的哈希槽位置的時(shí)候，只需要位運(yùn)算就可以快速得到結(jié)果溢十，不需要執(zhí)行取模運(yùn)算垮刹，位運(yùn)算的速度非常快张弛，要比取模運(yùn)算快很多荒典。
回到上面的問題酪劫，為什么要對(duì)key對(duì)象的hashCode執(zhí)行擾動(dòng)呢？因?yàn)橛?jì)算哈希槽位置的時(shí)候需要和table數(shù)組的長(zhǎng)度進(jìn)行&運(yùn)算种蝶，在絕大部分場(chǎng)景下契耿，table數(shù)組的長(zhǎng)度不會(huì)很大，這就導(dǎo)致hashCode的高位很大概率不能有效參加尋址計(jì)算螃征，所以將key的hashCode的高16位于低16位執(zhí)行了異或運(yùn)算搪桂，這樣得到的hash值會(huì)均勻很多。
接下來繼續(xù)看put操作的流程：
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict
// 1
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 2
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 3
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 4
else {
// 5
Node<K,V> e; K k;
// 6
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 7
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 8
else {
// 9
for (int binCount = 0; ; ++binCount) {
// 10
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 11
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 12
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 13
p = e;
}
}
// 14
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
?
return oldValue;
}
}
?
// 15
if (++size > threshold)
resize();
?
return null;
}
下面根據(jù)注釋的編號(hào)來看一下對(duì)應(yīng)位置的含義：
（1）這里主要關(guān)注tab和p兩個(gè)變量盯滚，tab是table數(shù)組的一個(gè)引用踢械，p是當(dāng)前拿到的Node引用，這個(gè)Node可能為null魄藕；
（2）這里將table賦值給了tab變量内列，并且判斷了tab數(shù)組是否為空，如果為空背率，表示是首次執(zhí)行put操作话瞧，table還沒有被初始化出來，需要執(zhí)行初始化操作寝姿，這里直接調(diào)用resize方法就可以完成初始化操作交排，關(guān)于resize，下一小節(jié)再重點(diǎn)分析饵筑。
（3）(n - 1) & hash計(jì)算出來的就是這個(gè)key對(duì)應(yīng)的哈希槽埃篓，這個(gè)算法上面已經(jīng)分析過，p變量拿到了當(dāng)前哈希槽的頭節(jié)點(diǎn)根资，并進(jìn)行了判斷架专，如果是null，則說明此時(shí)這個(gè)哈希槽內(nèi)部沒有哈希沖突玄帕，直接創(chuàng)建一個(gè)新的Node插入這個(gè)槽即可部脚；
（4）此時(shí)，說明p變量不為null桨仿，這個(gè)時(shí)候問題比較復(fù)雜睛低，這個(gè)p可能是一個(gè)鏈表頭節(jié)點(diǎn)，也可能是一個(gè)紅黑樹根節(jié)點(diǎn)服傍，這是結(jié)構(gòu)上的可能性钱雷，接下來需要做的，就是判斷p代表的結(jié)構(gòu)上是否存在即將要插入的key吹零，如果存在罩抗，則說明節(jié)點(diǎn)已經(jīng)存在，執(zhí)行更新操作即可灿椅，如果不存在套蒂，則需要執(zhí)行插入操作钞支，看接下來的流程；
（5）同樣操刀，e變量存儲(chǔ)的是代表存儲(chǔ)key的Node烁挟，可能為null，如果key壓根沒有被存儲(chǔ)過骨坑，那么e最終就是null撼嗓，否則就是存儲(chǔ)key的Node的一個(gè)引用；
（6）這里是判斷哈希槽的頭結(jié)點(diǎn)是否是存儲(chǔ)key的節(jié)點(diǎn)欢唾，這是典型的判斷方法且警，先對(duì)比hash，然后對(duì)比key礁遣，對(duì)比key的時(shí)候要特別注意斑芜，除了使用“==”來進(jìn)行比較，還使用了key對(duì)象的equals方法祟霍；如果判斷通過杏头，則e就指向了已經(jīng)存在的代表存儲(chǔ)key的Node；
（7）如果執(zhí)行到這沸呐，說明p（哈希槽的頭結(jié)點(diǎn)）不是代表存儲(chǔ)key的Node大州，那么就要繼續(xù)后面的流程，這里首先判斷了一下p的結(jié)構(gòu)垂谢，如果是TreeNode，說明p代表的是紅黑樹的頭結(jié)點(diǎn)疮茄，那就是要紅黑樹的節(jié)點(diǎn)插入方法putTreeVal來進(jìn)行滥朱，關(guān)于紅黑樹，后續(xù)再仔細(xì)學(xué)習(xí)力试，本文點(diǎn)到為止徙邻。
（8）執(zhí)行到這里，說明p代表的是一條鏈表的頭結(jié)點(diǎn)畸裳，需要在p這條鏈表中查找一下是否存在表示key的Node缰犁；
（9）開始迭代鏈表，來查找key怖糊；
（10）e此時(shí)表示的是p的next帅容，如果e為null，說明鏈表迭代到了末尾伍伤，此時(shí)依然沒有發(fā)現(xiàn)key并徘，則說明鏈表中根本不存在key節(jié)點(diǎn)，直接把key節(jié)點(diǎn)插入到末尾即可扰魂；
（11）這里有一個(gè)判斷麦乞，binCount如果超過了TREEIFY_THRESHOLD蕴茴，則需要將鏈表升級(jí)為紅黑樹，通過treeifyBin方法來實(shí)現(xiàn)這個(gè)功能姐直；
（12）如果e節(jié)點(diǎn)就是key節(jié)點(diǎn)倦淀，那么就可以結(jié)束了，e就是key節(jié)點(diǎn)的一個(gè)引用声畏；
（13）p = e撞叽，就是將p向前移動(dòng)，繼續(xù)判斷砰识，簡(jiǎn)單的鏈表迭代能扒；
（14）如果此時(shí)e不為null，說明鏈表中存在key節(jié)點(diǎn)辫狼，那么本次put操作其實(shí)是一次replace操作初斑；
（15）執(zhí)行到這里，說明put操作插入了一個(gè)新的Node膨处，如果插入后HashMap中的Node數(shù)量超過了本次擴(kuò)容閾值见秤，那么就要執(zhí)行resize操作，resize操作將在下一小節(jié)詳細(xì)展開分析真椿；
四鹃答、 HashMap擴(kuò)容機(jī)制
擴(kuò)容對(duì)于HashMap是一個(gè)很重要的操作，如果沒有擴(kuò)容機(jī)制突硝，因?yàn)橛泄Ｅ鲎驳陌l(fā)生测摔，會(huì)使得鏈表或者紅黑樹的節(jié)點(diǎn)數(shù)量過多，導(dǎo)致查詢效率較低解恰。下面锋八，就從源碼的角度來分析一下HashMap的擴(kuò)容是如何完成的：
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
// 1
Node<K,V>[] oldTab = table;
// 2
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 3
int oldThr = threshold;
// 4
int newCap, newThr = 0;
// 5
if (oldCap > 0) {
// 6
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 7
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 8
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 9
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 10
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 11
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 12
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 13
table = newTab;
// 14
if (oldTab != null) {
// 15
for (int j = 0; j < oldCap; ++j) {
// 16
Node<K,V> e;
// 17
if ((e = oldTab[j]) != null) {
// 18
oldTab[j] = null;
// 19
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 20
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 21
else { // preserve order
// 22
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 23
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 24
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 25
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 26
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
resize操作很復(fù)雜，下面根據(jù)代碼注釋來看一下每個(gè)位置都在做什么：
（1）oldTab變量指向table护盈，這個(gè)沒有特別難以理解挟纱；
（2）oldCap就是當(dāng)前table的大小，也就是擴(kuò)容前的table大小腐宋，table可能未初始化紊服，則oldCap就是0；
（3胸竞、4）變量賦值欺嗤，新老容量和擴(kuò)容閾值；
-
（5卫枝、6剂府、7）oldCap大于0，則說明table已經(jīng)初始化過剃盾，擴(kuò)容的時(shí)候腺占，新的容量是老的table的兩倍淤袜，這里需要處理一下超過最大容量的問題，如果table數(shù)組已經(jīng)達(dá)到最大了衰伯，那么就不要再繼續(xù)擴(kuò)容了铡羡，生死有命富貴在天吧嘿嘿
；
（8）這種情況下是說在創(chuàng)建HashMap的時(shí)候指定了初始化大小意鲸，那新的table的容量就是當(dāng)前的擴(kuò)容閾值烦周；
（9）執(zhí)行到這里，說明table還沒創(chuàng)建怎顾，但是創(chuàng)建HashMap的時(shí)候沒有指定初始容量读慎，那么本次其實(shí)就是執(zhí)行初始化table的工作；
（10）計(jì)算新的擴(kuò)容閾值槐雾；
（11夭委、12、13）創(chuàng)建好新的數(shù)組募强，大小是原來的兩倍株灸，并使用newTab表示；
（14）執(zhí)行到這里擎值，如果本次只是初始化table數(shù)組慌烧，那么其實(shí)resize的工作已經(jīng)完成了，但是如果不是初始化table鸠儿，而是執(zhí)行正常的擴(kuò)容操作屹蚊，那么就需要執(zhí)行數(shù)據(jù)遷移的工作，所謂數(shù)據(jù)遷移进每，就是將Node從原來的table中遷移到擴(kuò)容出來的數(shù)組中淑翼；
（15）循環(huán)原來的table數(shù)組，逐個(gè)遷移數(shù)據(jù)品追；
（16）e變量用來表示當(dāng)前遍歷到的Node；
（17）原table數(shù)組中當(dāng)前哈希槽可能是空的冯丙，如果是空的肉瓦，就說明沒有數(shù)據(jù)需要遷移，繼續(xù)處理下一個(gè)哈希槽就可以胃惜，如果當(dāng)前哈希槽有節(jié)點(diǎn)泞莉，那么就需要對(duì)當(dāng)前哈希槽內(nèi)的數(shù)據(jù)執(zhí)行遷移操作；
（18）e變量已經(jīng)拿到了當(dāng)前需要遷移的哈希槽的頭結(jié)點(diǎn)引用船殉，執(zhí)行oldTab[j] = null鲫趁，就是為了減少引用，盡快讓垃圾得到回收利虫；
（19）這種情況很簡(jiǎn)單挨厚，當(dāng)前需要遷移的哈希槽內(nèi)部只有一個(gè)節(jié)點(diǎn)堡僻，那么就直接將該節(jié)點(diǎn)遷移到新的table中正確的位置就可以了；
（20）執(zhí)行到這疫剃，表示哈希槽內(nèi)是一顆紅黑樹钉疫，需要使用紅黑樹的節(jié)點(diǎn)遷移方法，這部分暫時(shí)不做分析巢价；
（21）執(zhí)行到這牲阁，說明需要遷移的是一條鏈表，下面就開始將這條鏈表上的節(jié)點(diǎn)遷移到新table中正確的位置上去壤躲；
（22）這里需要引出一個(gè)關(guān)鍵知識(shí)點(diǎn)城菊，哈希槽數(shù)據(jù)遷移方案，得益于哈希數(shù)組的大小是2的冪次方這個(gè)特性碉克，對(duì)于一個(gè)節(jié)點(diǎn)凌唬，在擴(kuò)容后，它對(duì)應(yīng)的哈希位置只可能存在兩種情況棉胀，要么還是當(dāng)前位置（在新數(shù)組中）法瑟，要么是當(dāng)前位置+oldCap；這是為什么呢唁奢？來看一個(gè)例子：
我們假設(shè)擴(kuò)容前數(shù)組長(zhǎng)度為2霎挟，則擴(kuò)容后數(shù)組的長(zhǎng)度為4，原數(shù)組的數(shù)組下標(biāo)為1的位置上存在一條鏈表需要遷移到新數(shù)組中去麻掸，這條鏈表長(zhǎng)度為3酥夭，根據(jù)哈希槽位置計(jì)算方法：hash & (len -1)，原來的len = 2脊奋， len - 1 = 1熬北，新的len = 4， len - 1 = 3诚隙；用二進(jìn)制表示為：01 => 11讶隐，如果繼續(xù)擴(kuò)容，則(len - 1)的變化規(guī)則為:01 => 11 => 111 => 1111 => ...久又，可以看到巫延，沒擴(kuò)容一次，hash值的高位就會(huì)多一位來參與哈希計(jì)算地消，多一位的這位hash數(shù)二進(jìn)制表現(xiàn)為：要么是0炉峰，要么是1，只有這兩種可能脉执，如果為0疼阔，則相當(dāng)于計(jì)算出來的哈希槽位置和原來一樣，如果為1，則哈希槽位置會(huì)+oldCap婆廊，比如對(duì)于k1和k2迅细，假設(shè)k1的hash計(jì)算結(jié)果為3，二進(jìn)制表示為：11否彩，則原來的下標(biāo)為 (11 & 01) = b01 = 1疯攒，擴(kuò)容后下標(biāo)計(jì)算為：（11 & 11） = b11 = 3，3 = 1 + 2 = oldIndex + oldCap列荔；有了這個(gè)知識(shí)點(diǎn)敬尺，那么就可以繼續(xù)來看22這個(gè)位置上的代碼了，這里有兩組變量贴浙，loHead和loTail是一組砂吞，hiHead和hiTail是一組，這兩組分別表示上面分析的兩種情況崎溃，也就是loHead和loTail表示那些擴(kuò)容后依然在原來下標(biāo)的Node蜻直，hiHead和hiTail表示那些擴(kuò)容后需要移動(dòng)到oldIdex + oldCap位置上的Node；
（23）這里袁串，如果e節(jié)點(diǎn)的hash&oldCap==0概而，說明本次新參與的高位二進(jìn)制位0，那這個(gè)節(jié)點(diǎn)擴(kuò)容后還是在當(dāng)前的index囱修；
（24）這里表示e節(jié)點(diǎn)擴(kuò)容后需要移動(dòng)到index + oldCap的位置上去赎瑰；
-
（25、26）到這里破镰，需要將兩條鏈表放到新數(shù)組正確的位置上去餐曼，這樣就完成了擴(kuò)容操作狗
；
五鲜漩、 HashMap數(shù)據(jù)查詢機(jī)制
數(shù)據(jù)查詢比較簡(jiǎn)單源譬，我們來分析一下HashMap的get操作是如何完成的；
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
上來首先計(jì)算了key的hash孕似，然后在調(diào)用getNode來實(shí)現(xiàn)節(jié)點(diǎn)查找踩娘，接下來看一下getNode方法的實(shí)現(xiàn)；
final Node<K,V> getNode(int hash, Object key) {
// 1
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 2
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 3
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 4
if ((e = first.next) != null) {
// 5
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 6
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 7
return null;
}
（1）tab變量指向當(dāng)前table喉祭，first是當(dāng)前哈希槽的第一個(gè)節(jié)點(diǎn)的引用养渴，e用于迭代鏈表；
（2）首先tab賦值臂拓，然后需要判斷當(dāng)前table是否為空，以及first賦值及檢測(cè)是否為空习寸，如果這些檢測(cè)沒通過胶惰，則說明當(dāng)前HashMap中不可能存在key節(jié)點(diǎn)，直接返回null即可霞溪；
（3）如果first節(jié)點(diǎn)就是需要找到的key節(jié)點(diǎn)孵滞，則直接返回first節(jié)點(diǎn)中捆；
（4）如果當(dāng)前哈希槽只有一個(gè)節(jié)點(diǎn)，那么到此搜索結(jié)束坊饶，沒有找到key節(jié)點(diǎn)泄伪，否則，繼續(xù)在first結(jié)構(gòu)上查找匿级；
（5）如果當(dāng)前槽內(nèi)是一顆紅黑樹蟋滴，則通過紅黑樹的查找方法來查找，這個(gè)分支暫時(shí)不看痘绎；
（6）否則津函，當(dāng)前槽內(nèi)就是一條鏈表，那么就需要迭代這條鏈表來找到目標(biāo)節(jié)點(diǎn)孤页；
（7）執(zhí)行到這里尔苦，說明HashMap中不存在key節(jié)點(diǎn)；
六行施、 HashMap數(shù)據(jù)更新機(jī)制
數(shù)據(jù)更新操作主要看一下remove操作是如何實(shí)現(xiàn)的：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
還是會(huì)先計(jì)算key的哈希值允坚，然后調(diào)用removeNode方法來執(zhí)行刪除操作；下面來看一下removeNode方法的實(shí)現(xiàn)細(xì)節(jié)：
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// 1
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 2
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
// 3
Node<K,V> node = null, e; K k; V v;
// 4
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 5
else if ((e = p.next) != null) {
// 6
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
// 7
else {
do {
// 8
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 9
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 10
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 11
else if (node == p)
tab[index] = node.next;
// 12
else
p.next = node.next;
++modCount;
// 13
--size;
return node;
}
}
return null;
}
（1）tab是當(dāng)前table的引用蛾号，p指向定位到哈希槽的頭結(jié)點(diǎn)稠项，index是當(dāng)前key節(jié)點(diǎn)的哈希槽位置；
（2）獲取到p節(jié)點(diǎn)须教，如果p節(jié)點(diǎn)為null皿渗，說明當(dāng)前HashMap中不可能存在key，所以刪除失敗轻腺，返回null乐疆，結(jié)束刪除流程；
（3）node表示找到的key節(jié)點(diǎn)贬养，也就是指向?qū)⒁粍h除掉的Node挤土；
（4）這個(gè)分支表示當(dāng)前槽內(nèi)的頭結(jié)點(diǎn)就是所要?jiǎng)h除的Node，賦值給node變量误算；
（5）表示槽內(nèi)的頭節(jié)點(diǎn)并不是所要?jiǎng)h除的節(jié)點(diǎn)仰美，那么就要繼續(xù)在p結(jié)構(gòu)中查找，需要判斷一些槽內(nèi)是否就一個(gè)p節(jié)點(diǎn)儿礼，如果是咖杂，那么就可以結(jié)束刪除流程，當(dāng)前HashMap中不可能存在key節(jié)點(diǎn)蚊夫；
（6）如果p結(jié)構(gòu)是一顆紅黑樹诉字，那么就要使用查找紅黑樹的方法查找節(jié)點(diǎn)；
（7）否則，就要在鏈表p中找到key節(jié)點(diǎn)壤圃；
（8）迭代整個(gè)p鏈表陵霉，找到key節(jié)點(diǎn)，并賦值給node變量伍绳，但可能沒找到踊挠，此時(shí)node為null；
（9）如果node為null冲杀，則說明沒有找到需要?jiǎng)h除的數(shù)據(jù)效床，也就是不存在需要?jiǎng)h除的節(jié)點(diǎn)，否則漠趁，就要執(zhí)行刪除操作扁凛；
（10）如果需要?jiǎng)h除的node節(jié)點(diǎn)是一個(gè)紅黑樹節(jié)點(diǎn)，那么就調(diào)用紅黑樹的節(jié)點(diǎn)刪除方法闯传；
（11）如果node和p相等谨朝，那么就說明需要?jiǎng)h除的節(jié)點(diǎn)是鏈表的頭結(jié)點(diǎn)，只需要將頭結(jié)點(diǎn)移動(dòng)到next即可實(shí)現(xiàn)節(jié)點(diǎn)刪除甥绿；
（12）否則字币，就要?jiǎng)h除node節(jié)點(diǎn)，此時(shí)共缕，p節(jié)點(diǎn)就是node節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)洗出，刪除node節(jié)點(diǎn)只需要執(zhí)行 p.next = node.next就可以實(shí)現(xiàn)；
（13）刪除一個(gè)節(jié)點(diǎn)之后图谷，需要將size減1翩活；
七、 HashMap并發(fā)安全問題分析
我們都知道便贵，HashMap是線程不安全的菠镇，所謂線程不安全，就是使用不當(dāng)在并發(fā)環(huán)境下使用了HashMap承璃，那么就會(huì)發(fā)生不可預(yù)料的問題利耍，一個(gè)典型的問題就是cpu 100%問題，這個(gè)問題在java 7中是因?yàn)閿U(kuò)容的時(shí)候鏈表成環(huán)造成的盔粹，這個(gè)成環(huán)是因?yàn)閖ava 7在遷移節(jié)點(diǎn)的時(shí)候使用的是頭插法隘梨，在java 8中使用了尾插法避免了這個(gè)問題，但是java 8中依然存在100%的問題舷嗡，在java 8中是因?yàn)榧t黑樹父子節(jié)點(diǎn)成環(huán)了轴猎。
下面，來簡(jiǎn)單分析一下java 7中鏈表成環(huán)的問題：
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
// 1
Entry<K,V> next = e.next;
// 2
int i = indexFor(e.hash, newCapacity);
// 3
e.next = newTable[i];
// 4
newTable[i] = e;
// 5
e = next;
}
}
}
如圖所示进萄，在擴(kuò)容前捻脖，位置1上有一條長(zhǎng)度為3的鏈表烦秩，擴(kuò)容后數(shù)組的長(zhǎng)度為4，這條鏈表的key=5的節(jié)點(diǎn)會(huì)被遷移到新數(shù)組位置為1的位置上郎仆，其余兩個(gè)節(jié)點(diǎn)會(huì)按照尾插法遷移到新數(shù)組位置為3的位置上。
假設(shè)兩個(gè)線程同時(shí)指向擴(kuò)容兜蠕，thread1執(zhí)行到代碼位置（1）的時(shí)候失去cpu扰肌，thread2此時(shí)獲得cpu并完成了數(shù)據(jù)遷移，之后熊杨，thread1重新獲得cpu曙旭，開始執(zhí)行遷移操作，此時(shí)e執(zhí)行key=3的節(jié)點(diǎn)晶府，next指向key=7的節(jié)點(diǎn)桂躏，而此時(shí)thread2完成遷移后，key=7的節(jié)點(diǎn)的next為key=3的節(jié)點(diǎn)川陆，此時(shí)已經(jīng)成環(huán)剂习，此時(shí)如果有線程執(zhí)行g(shù)et等查詢操作，那么就可能陷入死循環(huán)较沪；如果thread1可以繼續(xù)執(zhí)行遷移鳞绕，執(zhí)行注釋中（3）這行代碼后，就將key=3的節(jié)點(diǎn)的next指向了key=7的節(jié)點(diǎn)尸曼，執(zhí)行（4）后们何，key=3的節(jié)點(diǎn)成了頭結(jié)點(diǎn)，執(zhí)行（5）后控轿，e指向了key=7的節(jié)點(diǎn)冤竹，接著繼續(xù)下一輪遷移；這樣茬射，這個(gè)遷移永遠(yuǎn)也完成不了鹦蠕，只會(huì)不斷在更新槽位的頭結(jié)點(diǎn)，死循環(huán)了躲株。所以片部，如果是在并發(fā)環(huán)境下，我們應(yīng)該使用線程安全的并發(fā)HashMap霜定，
<pre style="margin: 0px; padding: 0px; background-color: rgb(255, 255, 255); color: rgb(0, 0, 0); font-family: "Source Code Pro"; font-size: 12pt;">ConcurrentHashMap是最好的選擇档悠，當(dāng)然還有其他的方案，但是如果可以使用</pre>
ConcurrentHashMap望浩，其他方案都不推薦辖所。
參考資料：
為什么HashMap線程不安全 http://www.reibang.com/p/e2f75c8cce01
java 8HashMap源碼分析 http://www.reibang.com/p/d5f0a99966f7
