概述
java8對(duì)java7中hashmap的實(shí)現(xiàn)進(jìn)行了一部分修改涩堤，最大的修改在于利用了紅黑樹，jdk7使用數(shù)組+鏈表實(shí)現(xiàn)hashmap躺率，jdk8使用數(shù)組+鏈表+紅黑樹實(shí)現(xiàn)hashmap，之所以jdk8要引入紅黑樹，因?yàn)閖dk7的單向鏈表可以無限延伸寝贡，時(shí)間復(fù)雜度取決于鏈表的長(zhǎng)度，為O(n)值依，為了降低這部分開銷圃泡，jdk8中，當(dāng)單向鏈表中元素達(dá)到8個(gè)的時(shí)候愿险，會(huì)將鏈表轉(zhuǎn)換為紅黑樹颇蜡，這些位置的查找的時(shí)間復(fù)雜度降低為O(logN)
java7使用Entry描述hashmap中的每個(gè)數(shù)據(jù)節(jié)點(diǎn)，java8在沒生成紅黑樹的時(shí)候辆亏，使用node來描述鏈表元素风秤，當(dāng)轉(zhuǎn)換紅黑樹的時(shí)候，使用treenode描述鏈表元素
哈希表
哈希表扮叨，又稱散列表缤弦，是一種數(shù)據(jù)結(jié)構(gòu)，一個(gè)哈希表包含一個(gè)數(shù)組彻磁，通過特殊的key來訪問數(shù)組中元素碍沐，哈希表主要思想是通過一個(gè)哈希函數(shù)，在key映射的位置去尋找存放值的地方
如下圖字典：尋找安存放的位置衷蜓，通過hash函數(shù)f(安)計(jì)算出an累提，從而放在第二位，哈希沖突：f(按)=an磁浇，追加在安后面斋陪，哈希沖突無法避免
哈希表的特性決定了哈希表具有較高性能，大多數(shù)查找或插入元素時(shí)間復(fù)雜度都為O(1)扯夭，時(shí)間主要花在計(jì)算hash值上鳍贾，如果使用的hash函數(shù)不夠好，會(huì)導(dǎo)致大量hash值映射在同一個(gè)地址上交洗，這樣哈希表就會(huì)退化成鏈表骑科，時(shí)間復(fù)雜度變O(n)，效率低下
jdk8版本hashmap結(jié)構(gòu)
jdk8版本hashmap源碼
基本屬性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 用于擴(kuò)容构拳，不會(huì)說到16才擴(kuò)容咆爽，沒到16的時(shí)候就會(huì)梁棠，這個(gè)閾值就是加載因子乘以容量，即12的時(shí)候就會(huì)擴(kuò)容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 變成紅黑樹的閾值=8
static final int TREEIFY_THRESHOLD = 8;
transient Node<K,V>[] table;
put(K key, V value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
//此處為了降低哈希沖突的幾率斗埂，在這里不直接返回hashCode而是分下面幾步
//1 獲取key的HashCode
//2 將獲取到的hashCode向右移16位
//3 移動(dòng)結(jié)果和原來的key的hashCode異或運(yùn)算 (相同的異或?yàn)?符糊，不相同異或?yàn)?)
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
元素在數(shù)組中存放的位置是由下面的i=(n-1)&hash決定的，這行代碼摘自putVal()呛凶，n為當(dāng)前數(shù)組的大小男娄，i為當(dāng)前元素存放的索引
測(cè)試代碼
HashMap map=new HashMap(1)
帶參數(shù)初始化
tableSizeFor結(jié)果為1，this.threshold擴(kuò)容閾值初始化為1漾稀，然后執(zhí)行下面代碼map.put("key1",111)模闲，發(fā)現(xiàn)tab是null，開始準(zhǔn)備調(diào)用擴(kuò)容方法初始化table
擴(kuò)容的時(shí)候崭捍，oldCap=0尸折，oldThr=1，newCap=newThr初始值為0殷蛇，在經(jīng)過else if完后实夹，newCap=1，在經(jīng)過if(newThr==0)后粒梦，newThr=（int）ft亮航，而ft=0.75，取int后未0匀们，即newThr新的擴(kuò)容閾值為0塞赂，只要table中元素超過0，就重新調(diào)用本方法昼蛀，然后初始化table，初始化完后返回到putVal方法
在putVal方法中圆存，首先將要放入的key1元素放入進(jìn)去
然后到最下邊叼旋，開始判斷是否需要擴(kuò)容，putVal放入一個(gè)元素后size=1沦辙，超過擴(kuò)容閾值0夫植，開始擴(kuò)容
然后resize部分代碼上邊部分如下，oldCap=1,oldThr=0,newCap在下面的1中變成2油讯，newThr經(jīng)過計(jì)算2*0.75=1.5變成1详民，然后完成新的table的初始化，準(zhǔn)備開始遷移
putVal
下面為變換紅黑樹的條件判斷以及判斷是否有節(jié)點(diǎn)的key跟待插入的key相同的邏輯
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 創(chuàng)建變量引用
Node<K,V>[] tab; Node<K,V> p; int n, i;
//先用局部變量拷貝一份成員變量陌兑，然后對(duì)局部變量判斷沈跨，另一個(gè)局部變量也對(duì)剛剛被賦值的局部變量判斷
if ((tab = table) == null || (n = tab.length) == 0)
// 數(shù)組沒初始化就進(jìn)行初始化
n = (tab = resize()).length;
// 尋址算法算出應(yīng)該放的位置沒有元素
if ((p = tab[i = (n - 1) & hash]) == null)
// 直接創(chuàng)建元素節(jié)點(diǎn)放入
tab[i] = newNode(hash, key, value, null);
else {
// e指針保存如果之前該key已經(jīng)有值了的舊值，k保存舊值的key
Node<K,V> e; K k;
// 如果要插入的位置的哈希跟要插入的key的hash結(jié)果相同并且【 key相同或者key不為空兔综，但是key和那個(gè)位置的key equals】
// 注意：***下面是if elseif else 三個(gè)分支６隽荨Ｄ辍！
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) {
// 認(rèn)為是同一個(gè)key的插入涧窒，則用局部變量e取出這個(gè)舊的節(jié)點(diǎn)
e = p;
} else if (p instanceof TreeNode) // 如果尋址算法算出的位置上的該節(jié)點(diǎn)是紅黑樹節(jié)點(diǎn)
// 用局部變量e取出這個(gè)舊的紅黑樹節(jié)點(diǎn)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 數(shù)組上的尋址算法算出的位置上該節(jié)點(diǎn)的key和要寫入的key不同心肪，走了上面兩個(gè)if以后，這里必定是鏈表節(jié)點(diǎn)
for (int binCount = 0; ; ++binCount) {
// 用e記錄節(jié)點(diǎn)p的下一個(gè)元素纠吴，如果不存在
if ((e = p.next) == null) {
// 直接將新元素插入作為p元素的后繼節(jié)點(diǎn)
p.next = newNode(hash, key, value, null);
// binCount=0的時(shí)候硬鞍，有2個(gè)節(jié)點(diǎn)，p節(jié)點(diǎn)和新插入的節(jié)點(diǎn)
// binCount=7的時(shí)候戴已，有9個(gè)節(jié)點(diǎn)固该，p節(jié)點(diǎn)+p后面的原本節(jié)點(diǎn)+新插入的節(jié)點(diǎn)
// binCount與新插入的節(jié)點(diǎn)無關(guān)系！９Ф浮蹬音！ 原來鏈表上有8個(gè)節(jié)點(diǎn)，現(xiàn)在先插入以后再判斷轉(zhuǎn)化為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 轉(zhuǎn)化為紅黑樹
treeifyBin(tab, hash);
break;
}
// 說明p節(jié)點(diǎn)后面還有節(jié)點(diǎn)休玩，e是p下一個(gè)節(jié)點(diǎn)著淆，如果e就是要插入的key的相同的key值，跳出
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 繼續(xù)進(jìn)行循環(huán)拴疤，將p的下一個(gè)節(jié)點(diǎn)e作為新的p永部，e指向更下一個(gè)節(jié)點(diǎn)
p = e;
}
}
// 如果e是null，說明沒有找到相同key的節(jié)點(diǎn) e是exists
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 如果允許覆蓋或者舊值為null （hashmap是允許key呐矾，value都可以是null的）
if (!onlyIfAbsent || oldValue == null)
// 將新的值賦值給那個(gè)節(jié)點(diǎn)
e.value = value;
afterNodeAccess(e); // hashmap自身并未實(shí)現(xiàn)該方法細(xì)節(jié)苔埋，子類實(shí)現(xiàn)
return oldValue; // 將之前的同key的節(jié)點(diǎn)的舊value返回
}
}
++modCount;
// 如果新加入元素以后的值大于擴(kuò)容閾值
if (++size > threshold)
// 進(jìn)行擴(kuò)容
resize();
afterNodeInsertion(evict); // hashmap自身并未實(shí)現(xiàn)該方法細(xì)節(jié)，子類實(shí)現(xiàn)
return null;
}
resize
擴(kuò)容過程主要完成了map的初始化以及容量到達(dá)閾值的時(shí)候創(chuàng)建新的數(shù)組蜒犯，并將舊數(shù)組數(shù)據(jù)遷移
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 后面判斷都是用局部變量去判斷的
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 舊的擴(kuò)容閾值
int oldThr = threshold;
// 聲明新的數(shù)組容量和新的擴(kuò)容閾值
int newCap, newThr = 0;
// 如果老的容量>0
if (oldCap > 0) {
// 如果老的數(shù)組容量已經(jīng)達(dá)到了最大容量了
if (oldCap >= MAXIMUM_CAPACITY) {
// 擴(kuò)容閾值修改為2^32
threshold = Integer.MAX_VALUE;
// 不進(jìn)行擴(kuò)容直接返回老的容量
return oldTab;
}
// 否則组橄，判斷將老的數(shù)組容量放大2倍以后如果沒超過最大容量且老的容量大于等于初始的默認(rèn)的初始容量16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 符合條件則將新的閾值變?yōu)槔祥撝档?倍
newThr = oldThr << 1; // double threshold
// 這里必要條件：老的容量小于最大容量2的30次冪
// 這里選擇條件：擴(kuò)容2倍后大于等于最大容量 或者老的數(shù)組容量小于默認(rèn)的容量16（如5，適配后變成8小于16）罚随，newThr這時(shí)候仍然為0
}
// 必要條件：oldCap=0
// 可能有兩種情況玉工，一種是oldThreshold=0（不帶初始容量初始化），一種是大于0（帶初始容量初始化）
else if (oldThr > 0) // initial capacity was placed in threshold
// 即帶初始容量參數(shù)初始化（new HashMap(initCapacity)）淘菩。oldThr在tableSizeFor被賦值遵班，直接將他賦值給新的*容量*。oldThr只是用來配置參數(shù)潮改，那時(shí)候還沒有實(shí)例化數(shù)組狭郑，這里才真正實(shí)例化，要用到上面的參數(shù)汇在。這時(shí)候newCap=oldThr翰萨，newThr=0(代碼頭部初始化的)
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 說明為不帶參數(shù)初始化（new HashMap()）
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 上面主要是為了堆newCap和newThr賦值，如果newThr沒有值說明走了if中的else if的else 或者 走了外圍的else if(oldThr>0)
/*
即可能存在 ：新擴(kuò)容后的容量大于最大容量 或者
老的容量小于默認(rèn)初始容量16（最有可能）
或者 oldThr>0
*/
// newCap已經(jīng)在if的elseif分支賦值了
if (newThr == 0) {
// 假設(shè)老的容量為8糕殉，加載因子是0.75缨历，則ft=6以蕴，newCap=1，則ft=0.75
float ft = (float)newCap * loadFactor;
// 如果新的容量小于最大容量并且新計(jì)算的float類型的擴(kuò)容閾值ft小于 float類型的最大容量辛孵，則新的擴(kuò)容閾值為該int類型的擴(kuò)容閾值
/**
帶參數(shù)初始化容量1丛肮，則首先執(zhí)行完：newCap=1，newThr=0魄缚，然后回到putValue方法宝与，放入要添加的元素以后發(fā)現(xiàn)大于擴(kuò)容閾值，開始擴(kuò)容
*/
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 創(chuàng)建新的數(shù)組用新的容量
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 這里讓table指向新的table的內(nèi)存地址冶匹，但是臨時(shí)變量oldTable還是指向了舊的數(shù)組的內(nèi)存地址
table = newTab;
// 如果為初始化這里已經(jīng)結(jié)束
if (oldTab != null) {
// 這里說明老的數(shù)組存在习劫，則遍歷
for (int j = 0; j < oldCap; ++j) {
// 游走指針，記錄每個(gè)被遍歷的元素
Node<K,V> e;
// 如果舊數(shù)組第一個(gè)元素存在
if ((e = oldTab[j]) != null) {
// 將舊數(shù)組第一個(gè)位置置空
oldTab[j] = null;
// 如果舊數(shù)組第一個(gè)元素所在的鏈表沒有后面的元素了
if (e.next == null)
// 將記錄的這個(gè)舊數(shù)組第一個(gè)元素使用 尋址算法嚼隘，再計(jì)算一次他的位置诽里，只能是原位置或者加上oldCapacity
newTab[e.hash & (newCap - 1)] = e;
// 如果舊數(shù)組第一個(gè)元素所在鏈表后面有元素，并且是紅黑樹節(jié)點(diǎn)
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 說明為鏈表節(jié)點(diǎn)飞蛹，開始遍歷第j個(gè)元素的鏈表節(jié)點(diǎn)
// 聲明低鏈表頭尾指針
Node<K,V> loHead = null, loTail = null;
// 聲明高鏈表頭尾指針
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 節(jié)點(diǎn)哈希值 和 舊的數(shù)組容量 與的結(jié)果 只能是0和舊的容量谤狡，從0開始一部分，從oldCap一部分卧檐， 又從0開始一部分
// 需要將此鏈表拆成兩個(gè)鏈表墓懂，放到新的數(shù)組中，并且保留原來的先后順序
// loHead霉囚、loTail 對(duì)應(yīng)一條鏈表捕仔，hiHead、hiTail 對(duì)應(yīng)另一條鏈表
// 低位鏈表
if ((e.hash & oldCap) == 0) {
// 如果低位鏈表此時(shí)沒有尾結(jié)點(diǎn)
if (loTail == null)
// 將當(dāng)前節(jié)點(diǎn)設(shè)置為低位鏈表的頭結(jié)點(diǎn)
loHead = e;
else
// 將低位鏈表之前的尾結(jié)點(diǎn)的next指針指向當(dāng)前節(jié)點(diǎn)
loTail.next = e;
// 將當(dāng)前節(jié)點(diǎn)設(shè)置為低位鏈表的尾結(jié)點(diǎn)
loTail = e;
}
// 高位鏈表盈罐，與的結(jié)果是舊的數(shù)組cap榜跌，操作同上，就是完成一個(gè)高位鏈表的初始化
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 某個(gè)節(jié)點(diǎn)上的高位鏈表和低位鏈表初始化完以后盅粪，將低位鏈表的頭部放到新鏈表的j角標(biāo)位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 將高位鏈表的頭部放到新鏈表的j+舊的數(shù)組容量的尋址位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
面試題
1. 為什么定義hashmap初始值是16是2的n次冪斜做，擴(kuò)容的時(shí)候新數(shù)組大小要是2的n次冪
核心：尋址算法
i是數(shù)組下標(biāo)，n是數(shù)組長(zhǎng)度湾揽，hash是要插入的entry的key的hash值
i =(n-1)&hash
2的次冪-1永遠(yuǎn)得到的結(jié)果的二進(jìn)制位最后面都是1，如
2-1
0000 0000 0000 0001
4-1
0000 0000 0000 0011
8-1
0000 0000 0000 0111
16-1
0000 0000 0000 1111
32-1
0000 0000 0001 1111
我們接下來按照如果數(shù)組長(zhǎng)度是2的次冪和不是2的次冪來做尋址算法比較笼吟，假如我們又4個(gè)entry等待插入库物，entry的key的hash計(jì)算結(jié)果分別為：
9 0000 0000 0001 1001
10 0000 0000 0001 1010
11 0000 0000 0001 1011
12 0000 0000 0001 1100
- 如果長(zhǎng)度是2的次冪，如默認(rèn)的數(shù)組長(zhǎng)度16贷帮，n-1=16-1=15 = 0000 0000 0000 1111
- 如果長(zhǎng)度不是2的次冪戚揭，如長(zhǎng)度為10，n-1=9=0000 0000 0001 1001
可以發(fā)現(xiàn)如果數(shù)組的長(zhǎng)度不使用2的n次冪的話撵枢，經(jīng)過尋址算法民晒，得到的結(jié)果會(huì)出現(xiàn)很多重復(fù)精居，增加了哈希碰撞的幾率。因此HashMap的初始容量是2的n次冪潜必。
下面我們看為什么擴(kuò)容也需要是2的冪次數(shù)靴姿，滿足2的冪就是相當(dāng)于每次擴(kuò)容都是翻倍
假設(shè)現(xiàn)在擴(kuò)容為長(zhǎng)度32，n-1=31=0000 0000 0001 1111則尋址算法結(jié)果為
可以看到磁滚，擴(kuò)容時(shí)在重新計(jì)算下標(biāo)位置時(shí)佛吓，只有兩種情況，一種是下標(biāo)不變垂攘，另一種是下標(biāo)變?yōu)椋涸聵?biāo)位置+擴(kuò)容前容量维雇，而上圖很明顯就是在擴(kuò)容器的與的二進(jìn)制結(jié)果的第一位加了1，等于是在原有的結(jié)果基礎(chǔ)上加了2的4次冪即擴(kuò)容前的容量16.這樣擴(kuò)容后節(jié)點(diǎn)移動(dòng)相對(duì)較少晒他，可以提高性能
總結(jié)：
HashMap計(jì)算添加元素的位置時(shí)吱型，使用的位運(yùn)算，這是特別高效的運(yùn)算陨仅；另外津滞，HashMap的初始容量是2的n次冪，擴(kuò)容也是2倍的形式進(jìn)行擴(kuò)容掂名，是因?yàn)槿萘渴?的n次冪据沈，可以使得添加的元素均勻分布在HashMap中的數(shù)組上，減少hash碰撞饺蔑，避免形成鏈表的結(jié)構(gòu)锌介，使得查詢效率降低！
2. hashmap初始化的時(shí)候可以指定數(shù)組長(zhǎng)度猾警，那是怎么保證輸入的值是2的n次冪
主要是通過如下代碼完成對(duì)輸入數(shù)組長(zhǎng)度轉(zhuǎn)化為2的n次冪
/**
* 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;
}
這一系列的無符號(hào)右移操作和按位或運(yùn)算返回的什么結(jié)果孔祸，我們可以通過一個(gè)測(cè)試來說明
public static void main(String[] args) throws Exception {
HashMap map = new HashMap();
Method tableSizeFor = map.getClass().getDeclaredMethod("tableSizeFor", int.class);
tableSizeFor.setAccessible(true);
List<Integer> list = Lists.newArrayList(3,4,15,16,17,31,32,33);
list.forEach(e-> {
try {
System.out.println(tableSizeFor.invoke(map,e));
} catch (IllegalAccessException | InvocationTargetException e1) {
e1.printStackTrace();
}
});
}
打印結(jié)果如下：
可以看出是用距離傳入的數(shù)組正向長(zhǎng)度最近的2次冪來替換該長(zhǎng)度
3. 什么時(shí)候擴(kuò)容以及加載因子為什么是0.75
/**
* The next size value at which to resize (capacity * load factor).
*
int threshold;
threshold是擴(kuò)容閾值，達(dá)到threshold就擴(kuò)容发皿，值為數(shù)組長(zhǎng)度 x 加載因子
至于加載因子為什么是0.75是因?yàn)椋涸诶硐肭闆r下崔慧，使用隨機(jī)哈希碼，在加載因子為0.75的情況下穴墅，節(jié)點(diǎn)出現(xiàn)在頻率在Hash桶（表）中遵循參數(shù)平均為0.5的泊松分布
4. 講述一下java8的hashmap的擴(kuò)容過程
根據(jù)我們?cè)诘谝坏烂嬖囶}中的結(jié)論 驗(yàn)證了 hashmap擴(kuò)容方法的注釋
當(dāng)超過限制的時(shí)候會(huì)resize惶室，然而又因?yàn)槲覀兪褂玫氖?次冪的擴(kuò)展(指長(zhǎng)度擴(kuò)為原來2倍)，所以玄货，元素的位置要么是在原位置皇钞，要么是在原位置再移動(dòng)2次冪的位置。
我們?cè)跀U(kuò)充HashMap的時(shí)候松捉，不需要重新計(jì)算hash夹界，只需要看看原來的hash值新增的第一個(gè)bit位“溃看那個(gè)bit是1還是0就好了可柿，是0的話索引沒變鸠踪，是1的話索引變成“原索引+oldCap”「闯猓可以看看下圖為16擴(kuò)充為32的resize示意圖：
這個(gè)設(shè)計(jì)非常的巧妙营密，既省去了重新計(jì)算hash值的時(shí)間，而且同時(shí)永票，由于新增的1bit是0還是1可以認(rèn)為是隨機(jī)的卵贱，因此resize的過程，均勻的把之前的沖突的節(jié)點(diǎn)分散到新的bucket了
5. 講述一下hashmap中用到的鏈表頭插法與尾插法
jdk1.7插入元素到單鏈表中采用頭插法侣集，jdk1.8采用的是尾插法键俱。
jdk1.7 插入鏈表的頭部,有一種看法是新插入的數(shù)據(jù)被查詢的概率比較大,插入到頭部查詢相對(duì)比較快. 但是在多線程環(huán)境中擴(kuò)容可能會(huì)造成循環(huán)鏈表,導(dǎo)致CPU100%
jdk1.8 改進(jìn):采用尾插法,在擴(kuò)容時(shí)不用重新計(jì)算hash值,元素索引值的變換是有規(guī)律的.
1.7版本的死循環(huán)問題
擴(kuò)容的時(shí)候，會(huì)遍歷原Entry數(shù)組世分，把所有的Entry重新Hash到新數(shù)組编振。為什么要重新Hash呢？因?yàn)殚L(zhǎng)度擴(kuò)大以后臭埋，Hash的規(guī)則也隨之改變踪央。
讓我們回顧一下Hash公式：
index = HashCode（Key） & （Length - 1）
當(dāng)原數(shù)組長(zhǎng)度為8時(shí)，Hash運(yùn)算是和111B做與運(yùn)算瓢阴；新數(shù)組長(zhǎng)度為16畅蹂，Hash運(yùn)算是和1111B做與運(yùn)算。Hash結(jié)果顯然不同
正常的rehash過程：
假如使用的hash算法就是簡(jiǎn)單的用key mod 一下也就是數(shù)組的長(zhǎng)度
最上面的是old hash 表荣恐，其中的Hash表的size=2, 所以key = 3, 7, 5液斜，在mod 2以后都沖突在table[1]這里了
接下來的三個(gè)步驟是Hash表 resize成4，然后所有的<key,value> 重新rehash的過程
并發(fā)下的rehash
有兩個(gè)線程叠穆，線程A和線程B少漆，線程A在執(zhí)行完Entry<K,V>next = e.next后被調(diào)度掛起，e指向key3硼被，next指向key7
然后線程B開始執(zhí)行示损，并且執(zhí)行完了整個(gè)rehash過程
線程A在線程B rehash后，指向了線程B重組后的原鏈表嚷硫，然后線程A開始執(zhí)行
【注意：之所以并發(fā)操作有問題检访，不是在線程內(nèi)部的newTable上，而是在線程A仔掸、B會(huì)操作oldTable脆贵，造成并發(fā)問題，因?yàn)榫€程B對(duì)oldTable中元素的指向的改變導(dǎo)致出現(xiàn)問題】
這里有個(gè)非常重要的地方嘉汰，擴(kuò)容后的newTable是方法參數(shù)，是屬于線程私有Ｗ辞凇Ｐ场双泪！注意
線程A的rehash過程：
- 此時(shí)e指向key3，next指向key7密似，而key7的next因?yàn)榫€程B的rehash仍然指向key3【導(dǎo)致問題核心】焙矛，新的table表是線程A的，表中無元素
- 執(zhí)行e.next=newTable[i]=null残腌，讓key3的next指向null村斟，然后讓key3成為3位置的頭號(hào)節(jié)點(diǎn)，然后next指針仍然是1步驟中指向key7抛猫，然后因?yàn)閑=next蟆盹，所以e指向key7
- e指向key7，next指針因?yàn)?步驟的原因仍然指向key3闺金，而key3的next是null逾滥，key7成為新的頭結(jié)點(diǎn)，下一步e指向key3
- e指向key3败匹，next指向null寨昙，因?yàn)閑.next=newTable[i]，所以key3的next指向key7掀亩，而key7的next一直指向key3舔哪，這時(shí)候環(huán)形鏈表就構(gòu)成了。又因?yàn)閑=next槽棍，next=null捉蚤，所以e指針和next指針均指向null
