HashMap在并發(fā)編程環(huán)境下有什么問題啊?
代碼回顧
1.7 的時候截珍，HashMap 在多并發(fā)環(huán)境下论熙，多線程擴(kuò)容螃成，有可能引起的死循環(huán)問題：
如1.7 的時候犹菱，HashMap的底層是由數(shù)組加鏈表來實現(xiàn)的朗儒，如下所示：
當(dāng)往HashMap中put一個鍵值對時：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
方法addEntry(hash, key, value, i);
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
當(dāng)達(dá)到擴(kuò)容條件為 if ((size >= threshold) && (null != table[bucketIndex])) 成立時颊乘，會發(fā)生 resize(2 * table.length); 擴(kuò)容。
比如 table的初始容量為8,加載因子為0.75,此時閾值為6醉锄，table已有三個元素乏悄，現(xiàn)在put一個元素 Entry8 , Entry8 被散列到table[5]處，而table[5] != null,此時滿足擴(kuò)容條件.
擴(kuò)容時先生成一個是table大小2倍的newTable榆鼠，然后把table中的元素遷移到newTable中
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
遷移的工作就由 transfer方法來完成纲爸，這個方法就是引起死循環(huán)的原因所在.
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
環(huán)的形成
現(xiàn)在我們來模擬一下環(huán)是如何形成的，設(shè)HashMap的初始容量為4妆够，先往HashMap中依次put三個元素<5,”B”>识啦、<9,”C”>、<1,”A”>神妹，它們都被散列到table[1]處颓哮，形成了鏈
假設(shè)一個HashMap已經(jīng)到了Resize的臨界點。此時有兩個線程Thread1和Thread2鸵荠，在同一時刻對HashMap進(jìn)行Put操作：
此時達(dá)到Resize條件冕茅，兩個線程各自進(jìn)行resize的第一步，也就是擴(kuò)容：
此時蛹找， 這時候姨伤，兩個線程都走到了rehash的步驟。假設(shè)線程1執(zhí)行完 transfer 方法中的 Entry<K,V> next = e.next 語句后時間片用完庸疾，掛起
此時乍楚，線程1內(nèi)的 e 指向 <1,“A”>，next指向<9,”C”> 届慈，如下圖所示：
線程2 生成完newTable后用transfer方法進(jìn)行遷移徒溪，執(zhí)行完后與線程1一樣忿偷，e指向<1,”A”>,next指向<9,”C”>
線程2 然后繼續(xù)執(zhí)行循環(huán)體下面的語句
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
// 繼續(xù)執(zhí)行
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// 此時 e = <1,A>
// 下面的語句會把運行時的變量的值填進(jìn)去
//注意: <1,A> 代表了指向 <1,A>的引用，就是此e的值
e.next = newTable[i];
// <1,A>.next = newTable[1];
newTable[i] = e;
// newTable[1] = <1,A>;
e = next;
// <1,A> = <9,C>;
// 此時e的指針指向了<9,C>
}
}
線程2執(zhí)行完之后為下圖 ：
然后線程2按照同樣的邏輯進(jìn)行第二次循環(huán)（while循環(huán)）臊泌，下圖是第二遍循環(huán)后的結(jié)果 ：
然后線程2按照同樣的邏輯進(jìn)行第三遍循環(huán)鲤桥，執(zhí)行后的結(jié)果 ：
此時，線程2時間片用完渠概，線程1得到時間片茶凳，開始執(zhí)行 :
注意，此時線程1的e指向<1,A>,next指向<9,C>,在線程2操作鏈表的時候播揪，線程1 中的e,next指向的元素沒變(一直是紅色的e和next)
線程一和線程二整體圖為：
然后線程1開始執(zhí)行循環(huán)內(nèi)剩下的代碼 ：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
// 繼續(xù)執(zhí)行
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// 此時 e = <1,A>
// 下面的語句會把運行時的變量的值填進(jìn)去
//注意: <1,A> 代表了指向 <1,A>的引用慧妄，就是此e的值
e.next = newTable[i];
// <1,A>.next = newTable[1];
newTable[i] = e;
// newTable[1] = <1,A>;
e = next;
// <1,A> = <9,C>;
// 此時e的指針指向了<9,C>
}
}
線程1執(zhí)行完之后為下圖 ：
線程1繼續(xù)執(zhí)行第二遍循環(huán) :
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
// next = <1,A>
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// 此時 e = <9,C>
e.next = newTable[i];
// <9,C>.next = newTable[1];
newTable[i] = e;
// newTable[1] = <9,C>;
e = next;
// <9,C> = <1,A>;
// 此時e的指針指向了<1,A>
}
}
執(zhí)行完之后如下圖所示：
線程1繼續(xù)第三遍循環(huán)（注意：此次循環(huán)會形成環(huán)）：
先執(zhí)行
然后執(zhí)行
此時環(huán)已經(jīng)形成
然后執(zhí)行剩余的兩行代碼
newTable[i] = e;
// newTable[1] = <1,A>;
e = next;
// e = null;
執(zhí)行完，e 為 null,退出循環(huán)
死循環(huán)的發(fā)生
當(dāng)形成環(huán)后,當(dāng)往HashMap中put元素的時候剪芍，這個元素恰巧落在了table[1]（不管有沒有更新table），而這個元素的Key不在table[1]這條鏈上窟蓝，此時會發(fā)生死循環(huán)
或者在get元素的時候罪裹，該元素恰巧落在table[1]上，并且該元素的Key不在該鏈上运挫，會發(fā)生死循環(huán) ：
死循環(huán)是這樣形成的状共， 核心就是線程2修改了原來的鏈表結(jié)構(gòu)，而線程1卻以原來的邏輯執(zhí)行遷移 谁帕。
jdk1.8 會產(chǎn)生死循環(huán)么峡继？
JDK 8 用 head 和 tail 來保證鏈表的順序和之前一樣； 并且采用尾插法匈挖，避免了這種死循環(huán)的產(chǎn)生碾牌， 但是還會有數(shù)據(jù)丟失等弊端（并發(fā)本身的問題）。
那并發(fā)下我還想使用散列表這種數(shù)據(jù)結(jié)構(gòu)怎么辦呢 儡循？
多線程情況下還是建議使用 ConcurrentHashMap舶吗，鎖的粒度較小，較HashTable或者 Collections.synchronizedMap() 性能要好一些 择膝。
