1.8 HashMap
HashMap主要是數(shù)組+單鏈表+紅黑樹組成灰羽。其實(shí)就是在一定條件下妆偏，數(shù)組index下的單鏈表轉(zhuǎn)化成紅黑樹，這是提升查找效率的诅炉。
原來jdk1.7的優(yōu)點(diǎn)是增刪效率高氓润，于是在jdk1.8的時(shí)候赂乐，不僅僅增刪效率高，而且查找效率也提升了咖气。
注意：不是說變成了紅黑樹效率就一定提高了挨措，只有在鏈表的長(zhǎng)度大于8，而且數(shù)組的長(zhǎng)度不小于64的時(shí)候才會(huì)將鏈表轉(zhuǎn)化為紅黑樹崩溪，
問題一：什么是紅黑樹呢浅役？
紅黑樹是一個(gè)自平衡的二叉查找樹，也就是說紅黑樹的查找效率是非常的高伶唯，查找效率會(huì)從鏈表的o(n)降低為o(logn)觉既。如果之前沒有了解過紅黑樹的話，也沒關(guān)系乳幸，你就記住紅黑樹的查找效率很高就OK了瞪讼。
問題二：為什么不一下子把整個(gè)鏈表變?yōu)榧t黑樹呢？
這個(gè)問題的意思是這樣的粹断，就是說我們?yōu)槭裁捶且鹊芥湵淼拈L(zhǎng)度大于等于8的時(shí)候尝艘，才轉(zhuǎn)變成紅黑樹？在這里可以從兩方面來解釋:
（1）構(gòu)造紅黑樹要比構(gòu)造鏈表復(fù)雜姿染，在鏈表的節(jié)點(diǎn)不多的時(shí)候，從整體的性能看來秒际， 數(shù)組+鏈表+紅黑樹的結(jié)構(gòu)可能不一定比數(shù)組+鏈表的結(jié)構(gòu)性能高悬赏。就好比殺雞焉用牛刀的意思。
（2）HashMap頻繁的擴(kuò)容娄徊，會(huì)造成底部紅黑樹不斷的進(jìn)行拆分和重組闽颇，這是非常耗時(shí)的。因此寄锐，也就是鏈表長(zhǎng)度比較長(zhǎng)的時(shí)候轉(zhuǎn)變成紅黑樹才會(huì)顯著提高效率兵多。
數(shù)據(jù)模型
重要屬性
總體和1.7的差不多尖啡，但注意1.7的節(jié)點(diǎn)是Entry，1.8是Node剩膘，還是單鏈表的時(shí)候就是Node衅斩，轉(zhuǎn)化為紅黑樹的時(shí)候就是TreeNode。
簡(jiǎn)要概括inti怠褐、put畏梆、get：
init
初始一個(gè)HashMap，可以傳入容量大小和負(fù)載因子奈懒，不傳容量大小的話默認(rèn)是16奠涌，負(fù)載因子默認(rèn)0.75，初始化的時(shí)候磷杏，僅僅是設(shè)置參數(shù)而已溜畅，還沒賦予table數(shù)組的內(nèi)存空間，即還沒有new對(duì)象极祸。真正賦予內(nèi)存空間慈格，是第一次執(zhí)行put操作的時(shí)候，后續(xù)源碼會(huì)詳細(xì)講解贿肩。put
傳入HashMap的是Key-Value對(duì)峦椰，進(jìn)行put的時(shí)候，主要首先對(duì)Key進(jìn)行hash擾動(dòng)計(jì)算汰规，計(jì)算出在數(shù)組的哪個(gè)下標(biāo)index汤功，然后采用尾插法的方式進(jìn)行添加，如果該index上的單鏈表溜哮，key存在就替換滔金，不同就用尾插法頂替，這里又分為替換的node是普通Node還是treeNode茂嗓，treeNode就進(jìn)行單獨(dú)的入紅黑樹處理餐茵。這里不展開。 如果put的時(shí)候述吸，是需要new Node的忿族，普通Node的話，單鏈表已經(jīng)超過到了8蝌矛，而且總Node數(shù)達(dá)到了64道批，就會(huì)進(jìn)行樹化，如果沒有到64入撒，僅僅是超過8隆豹，還是只會(huì)進(jìn)行擴(kuò)容而已。最后判斷如果總的size數(shù)超過了threshold茅逮，就會(huì)進(jìn)行擴(kuò)容璃赡。get
get無(wú)非就是找commonNode或TreeNode找到相應(yīng)的Node判哥，將其的value返回去即可。
源碼分析：
初始化init
也是僅僅給屬性賦予值碉考，但還沒初始化塌计，threshold這里和1.7有區(qū)別，它是傳入的大小的最接近中最小的2次冪數(shù)豆励，如傳入13夺荒，threshold計(jì)算出是16。這里需要注意良蒸，capacity沒傳入甚至是不會(huì)初始化threshold的技扼。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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); 和1.7的區(qū)別是這句，
}
put操作
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 分析2：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;
// 1. 若哈希表的數(shù)組tab為空嫩痰，則 通過resize() 創(chuàng)建
// 所以剿吻，初始化哈希表的時(shí)機(jī) = 第1次調(diào)用put函數(shù)時(shí)，即調(diào)用resize() 初始化創(chuàng)建
// 關(guān)于resize（）的源碼分析將在下面講解擴(kuò)容時(shí)詳細(xì)分析串纺，此處先跳過
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. 計(jì)算插入存儲(chǔ)的數(shù)組索引i：根據(jù)鍵值key計(jì)算的hash值 得到
// 此處的數(shù)組下標(biāo)計(jì)算方式 = i = (n - 1) & hash丽旅，同JDK 1.7中的indexFor（），上面已詳細(xì)描述
// 3. 插入時(shí)纺棺，需判斷是否存在Hash沖突：
// 若不存在（即當(dāng)前table[i] == null）榄笙，則直接在該數(shù)組位置新建節(jié)點(diǎn)，插入完畢
// 否則祷蝌，代表存在Hash沖突茅撞，即當(dāng)前存儲(chǔ)位置已存在節(jié)點(diǎn)，則依次往下判斷：a. 當(dāng)前位置的key是否與需插入的key相同巨朦、b. 判斷需插入的數(shù)據(jù)結(jié)構(gòu)是否為紅黑樹 or 鏈表
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); // newNode(hash, key, value, null)的源碼 = new Node<>(hash, key, value, next)
else {
Node<K,V> e; K k;
// a. 判斷 table[i]的元素的key是否與 需插入的key一樣米丘，若相同則 直接用新value 覆蓋 舊value
// 判斷原則：equals（）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// b. 繼續(xù)判斷：需插入的數(shù)據(jù)結(jié)構(gòu)是否為紅黑樹 or 鏈表
// 若是紅黑樹，則直接在樹中插入 or 更新鍵值對(duì)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); ->>分析3
// 若是鏈表,則在鏈表中插入 or 更新鍵值對(duì)
// i. 遍歷table[i]糊啡，判斷Key是否已存在：采用equals（） 對(duì)比當(dāng)前遍歷節(jié)點(diǎn)的key 與 需插入數(shù)據(jù)的key：若已存在拄查，則直接用新value 覆蓋 舊value
// ii. 遍歷完畢后仍無(wú)發(fā)現(xiàn)上述情況枉阵，則直接在鏈表尾部插入數(shù)據(jù)
// 注：新增節(jié)點(diǎn)后第美，需判斷鏈表長(zhǎng)度是否>8（8 = 桶的樹化閾值）：還需要判斷table是否已經(jīng)包含64個(gè)Node若是故黑，則把鏈表轉(zhuǎn)換為紅黑樹
else {
for (int binCount = 0; ; ++binCount) {
// 對(duì)于ii：若數(shù)組的下1個(gè)位置膀钠，表示已到表尾也沒有找到key值相同節(jié)點(diǎn)，則新建節(jié)點(diǎn) = 插入節(jié)點(diǎn)
// 注：此處是從鏈表尾插入个唧，與JDK 1.7不同（從鏈表頭插入钥顽，即永遠(yuǎn)都是添加到數(shù)組的位置坟冲，原來數(shù)組位置的數(shù)據(jù)則往后移）
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 插入節(jié)點(diǎn)后睛挚，若鏈表節(jié)點(diǎn)>數(shù)閾值，則將鏈表轉(zhuǎn)換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash); // 樹化操作
break;
}
// 對(duì)于i
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 更新p指向下一個(gè)節(jié)點(diǎn)急黎，繼續(xù)遍歷
p = e;
}
}
// 對(duì)i情況的后續(xù)操作：發(fā)現(xiàn)key已存在扎狱，直接用新value 覆蓋 舊value & 返回舊value
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 替換舊值時(shí)會(huì)調(diào)用的方法（默認(rèn)實(shí)現(xiàn)為空）
return oldValue;
}
}
++modCount;
// 插入成功后侧到，判斷實(shí)際存在的鍵值對(duì)數(shù)量size > 最大容量threshold
// 若 > ，則進(jìn)行擴(kuò)容 ->>分析4（但單獨(dú)講解淤击，請(qǐng)直接跳出該代碼塊）
if (++size > threshold)
resize();
afterNodeInsertion(evict);// 插入成功時(shí)會(huì)調(diào)用的方法（默認(rèn)實(shí)現(xiàn)為空）
return null;
}
/**
* 分析3：putTreeVal(this, tab, hash, key, value)
* 作用：向紅黑樹插入 or 更新數(shù)據(jù)（鍵值對(duì)）
* 過程：遍歷紅黑樹判斷該節(jié)點(diǎn)的key是否與需插入的key 相同：
* a. 若相同匠抗，則新value覆蓋舊value
* b. 若不相同，則插入
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
首次插入數(shù)據(jù)污抬，如果是空的table汞贸，就會(huì)resize，這里先不展開印机，就是初始化數(shù)組的意思矢腻。
傳入的key經(jīng)過hash，找到下標(biāo)index：
① 如果該index上沒有數(shù)據(jù)射赛，就新建一個(gè)Node放置上去多柑。
② 如果該下標(biāo)index有值，如果傳入key等于現(xiàn)存headNode的key楣责，結(jié)束if..else..判斷竣灌，然后headNode替換成NewValue并返回OldValue，結(jié)束秆麸。
③ 如果不是相同的key初嘹，接著else判斷，else if (p instanceof TreeNode)沮趣，
- 如果是treeNode屯烦，就是說這個(gè)headNode已經(jīng)形成紅黑樹了，那就入樹兔毒，無(wú)非就是更新或者新增漫贞。
- 如果不是treeNode，那就是單鏈表育叁，headNode的next如果是null迅脐，那就new一個(gè)Node進(jìn)行尾插法 的方式來插入，如果存在相同key就進(jìn)行替換豪嗽。
這里有個(gè)重要的點(diǎn)谴蔑，TREEIFY_THRESHOLD=8，這里是TREEIFY_THRESHOLD-1=7龟梦，>=7就擴(kuò)容隐锭，這里直接是由headNode的nextNode開始判斷，headNode就是-1计贰，正如注釋寫得 -1 for 1st钦睡，nextNode=0，開始循環(huán)判斷currentNode的nextNode是不是null躁倒，所以如果達(dá)到了7荞怒，而同時(shí)是0作為開始的洒琢，還有加上headNode，那么一共就是9褐桌，那么就是說衰抑，要單鏈表大于8，就達(dá)到了進(jìn)行樹化的第一個(gè)條件荧嵌，為什么說是第一個(gè)條件呛踊，因?yàn)閠reeifyBin(tab,hash)方法里頭進(jìn)行樹化還有一個(gè)條件是table需要滿足具有64個(gè)node。
如果任一不滿足啦撮，只會(huì)進(jìn)行resize擴(kuò)容谭网，而不會(huì)進(jìn)行樹化。
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash); // 樹化操作
break;
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
resize()擴(kuò)容
首次put逻族，和之后table達(dá)到指定條件進(jìn)行擴(kuò)容處理蜻底。
/**
* 分析4：resize（）
* 該函數(shù)有2種使用情況：1.初始化哈希表 2.當(dāng)前數(shù)組容量過小，需擴(kuò)容
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 擴(kuò)容前的數(shù)組（當(dāng)前數(shù)組）
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 擴(kuò)容前的數(shù)組的容量 = 長(zhǎng)度
int oldThr = threshold;// 擴(kuò)容前的數(shù)組的閾值
int newCap, newThr = 0;
// 針對(duì)情況2：若擴(kuò)容前的數(shù)組容量超過最大值聘鳞，則不再擴(kuò)充
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 針對(duì)情況2：若無(wú)超過最大值薄辅，就擴(kuò)充為原來的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 通過右移擴(kuò)充2倍
}
// 針對(duì)情況1：初始化哈希表（采用指定 or 默認(rèn)值）
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計(jì)算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每個(gè)bucket都移動(dòng)到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 鏈表優(yōu)化重hash的代碼塊
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
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里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
① 初次put進(jìn)行resize的操作，這時(shí)候是初始化table抠璃， 如果new HashMap()什么參數(shù)都不帶站楚，那么 oldCap=0，oldThr=threshold自然也是0搏嗡。這時(shí)候窿春，newCap 自然就是默認(rèn)值16，newThr自然是16*默認(rèn)因子0.75=12采盒。如果有傳入capacity旧乞，那么threshold就是最接近的最小2次冪，newCap就是它磅氨，即newTab是這個(gè)大小尺栖，之后oldCap是空的，直接返回newTab烦租。
②非初次put延赌，并達(dá)到條件，于是進(jìn)行resize叉橱。newCap 為 oldCap * 2挫以，newThr也是oldThr * 2，這時(shí)oldCap不是null窃祝，那么就開始進(jìn)行數(shù)據(jù)轉(zhuǎn)移掐松。
遍歷oldTab的每個(gè)下標(biāo)index，為空直接略過不需要處理，
不為空先判斷是不是只有一個(gè)Node：
- 是：與newTab進(jìn)行hash大磺，得到在newTab里的新下標(biāo)idnex泻仙，直接掛上去，結(jié)束量没。
- 否：判斷是不是treeNode：是的話，構(gòu)造回紅黑樹突想；否殴蹄， 是單鏈表的話，鏈表有兄弟節(jié)點(diǎn)猾担，遍歷單鏈表袭灯，Node與oldCap進(jìn)行異或運(yùn)算，結(jié)果==0绑嘹，放置在newTab的低位稽荧，否則放置在高位。
我們看到有4個(gè)變量工腋，Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null;姨丈，
低位頭、尾 擅腰； 高位頭蟋恬、尾，將單鏈表的各個(gè)Node趁冈，進(jìn)行異或運(yùn)算之后歼争，結(jié)果=0的，直接使用尾插法關(guān)聯(lián)起來渗勘，形成一個(gè)新鏈表沐绒，用于放置在oldTab的低位，頭就是loHead旺坠、尾就是loTail乔遮；不等于0就放置在高位，頭就是hiHead价淌、尾就是hiTail申眼，一樣的原理的。
它們各自形成高蝉衣、低單鏈表后括尸，可見代碼，低單鏈表原來在oldTab的什么位置病毡，轉(zhuǎn)移后就在newTab的什么位置濒翻，高單鏈表就放在newTab的oldTab[index]+oldTab.length的位置。簡(jiǎn)單來說，比如oldTab原本的length是16有送，元素本來就oldTab[2]淌喻，那么低單鏈表就放在newTab[2]處，而高單鏈表就是放在newTab[2+16]的位置雀摘。
全部轉(zhuǎn)移之后裸删，返回newTab，擴(kuò)容成功阵赠。
關(guān)于高低單鏈表計(jì)算
下標(biāo)index計(jì)算是 (n - 1) & hashcode涯塔，比如一開始n=16，就是oldTab的長(zhǎng)度為16清蚀，index=hashcode&15匕荸，然而15的二進(jìn)制是0000 1111，比如某個(gè)Node在oldTab的位置是index=7枷邪，那么這個(gè)Node的key的hashcode低4位必然是 0111榛搔。
隨著擴(kuò)容，在進(jìn)行高低單鏈表的分配時(shí)东揣，執(zhí)行的計(jì)算是e.hash & oldCap践惑，如果=0，就去低單鏈表救斑，那么什么時(shí)候=0呢童本，oldCap=0001 0000 ，Node的key的hashCode的低5位是 x 0111 脸候，因?yàn)槭?amp;運(yùn)算穷娱，低4位無(wú)論如何都是0的，x要么是0运沦，要么是1泵额，
Node的key的hashCode第五位：
- 0，與oldCap第五位1元素 & 運(yùn)算携添，就是0嫁盲，這個(gè)Node就去到 newTab中與舊index相同的位。用上面的例子說烈掠，Node在newTab的位置還是index=7羞秤。
- 1，與oldCap第五位1元素 & 運(yùn)算左敌，就是1瘾蛋，這個(gè)Node就去到 newTab中舊index+oldCap的位置。用上面的例子說矫限，Node在newTab的位置是index=7+16=23哺哼。
線程安全問題
1.8的hashMap不會(huì)出現(xiàn)死鏈情況佩抹，但還是會(huì)出現(xiàn)數(shù)據(jù)覆蓋和讀取數(shù)據(jù)丟失問題。
數(shù)據(jù)覆蓋
正常情況下取董，當(dāng)發(fā)生哈希沖突時(shí)棍苹，HashMap 是這樣的：
但多線程同時(shí)執(zhí)行 put 操作時(shí)，如果計(jì)算出來的索引位置是相同的茵汰，那會(huì)造成前一個(gè) key 被后一個(gè) key 覆蓋枢里，從而導(dǎo)致元素的丟失。
- put 的源碼：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步驟①：tab為空則創(chuàng)建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步驟②：計(jì)算index蹂午，并對(duì)null做處理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步驟③：節(jié)點(diǎn)key存在坡垫，直接覆蓋value
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) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//鏈表長(zhǎng)度大于8轉(zhuǎn)換為紅黑樹進(jìn)行處理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已經(jīng)存在直接覆蓋value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 步驟⑥、直接覆蓋
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 步驟⑦：超過最大容量 就擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
問題發(fā)生在步驟 ② 這里：
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
兩個(gè)線程都執(zhí)行了 if 語(yǔ)句画侣，假設(shè)線程 A 先執(zhí)行了 tab[i] = newNode(hash, key, value, null)，那 table 是這樣的：
接著堡妒，線程 B 執(zhí)行了 tab[i] = newNode(hash, key, value, null)配乱，那 table 是這樣的：
3 被干掉了。
數(shù)據(jù)讀取丟失
put 和 get 并發(fā)時(shí)會(huì)導(dǎo)致 get 到 null**
線程 A 執(zhí)行put時(shí)皮迟，因?yàn)樵貍€(gè)數(shù)超出閾值而出現(xiàn)擴(kuò)容搬泥，線程B 此時(shí)執(zhí)行g(shù)et，有可能導(dǎo)致這個(gè)問題伏尼。
注意來看 resize 源碼：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超過最大值就不再擴(kuò)充了忿檩，就只好隨你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 沒超過最大值，就擴(kuò)充為原來的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
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計(jì)算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
}
線程 A 執(zhí)行完 table = newTab 之后爆阶，線程 B 中的 table 此時(shí)也發(fā)生了變化燥透，此時(shí)去 get 的時(shí)候當(dāng)然會(huì) get 到 null 了，因?yàn)樵剡€沒有轉(zhuǎn)移辨图。
