在一次面試經(jīng)驗中岗宣，被問及了ConcurrentHashMap蚂会，當(dāng)時說的不好，回來翻書耗式、上網(wǎng)總結(jié)了點東西胁住，供大家學(xué)習(xí)和交流，話說面試真是可以學(xué)到一些東西刊咳，好了閑話少說彪见，進(jìn)入正題吧。
1.多線程環(huán)境下的下HashMap為什么會導(dǎo)致程序死循環(huán)
眾所周知
在多線程的環(huán)境娱挨，HashMap的put操作會導(dǎo)致程序死循環(huán)余指，例如如下代碼：
/**
* @Description: HashMap出現(xiàn)死循環(huán).
* @Author: ZhaoWeiNan .
* @CreatedTime: 2017/6/7 .
* @Version: 1.0 .
*/
public class Demo1 {
public static void main(String[] args){
final Map<String,String> map = new HashMap<>();
//開啟10000個線程，在map里面put值
for (int i = 0 ; i < 10000 ; i ++){
new Thread(new Runnable() {
@Override
public void run() {
map.put(UUID.randomUUID().toString(),"");
}
}).start();
}
}
}
分析原因
HashMap詳細(xì)的原理就不給大家標(biāo)示碉碉，大家可以去百度看看，以后有時間在為大家總結(jié)淮韭，這里簡單說一下垢粮。
HashMap是由數(shù)組和鏈表組成的，貼一點HashMap的源碼：
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
//Entry<K,V>組成的數(shù)組table
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//Entry<K,V>有以下屬性
static class Entry<K,V> implements Map.Entry<K,V> {
//key 鍵
final K key;
//value 值
V value;
//鏈表元素的尾靠粪，指向下一個元素
Entry<K,V> next;
//由hash算法得出的hash值
int hash;
當(dāng)加入元素時候蜡吧，會使用hash算法算出這個key在table中的索引，然后看table該索引上是否存在元素庇配，如果不存在斩跌，把該Entry<K,V>插入到table的這個索引位置上，如果存在元素捞慌，就說明發(fā)生了沖突耀鸦，然后就從table該索引位置上的節(jié)點為頭的鏈表上遍歷比較，如果key的hash值和鏈表中節(jié)點的hash相等啸澡，并且key相等袖订，就把value存到鏈表元素的value中，把原來的value返回出來嗅虏，如果沒有相等的洛姑，就在鏈表的最末端的節(jié)點后面新加一個節(jié)點。
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
//通過hash算法計算key的hash皮服，hash算法源碼就不給出了
int hash = hash(key);
//通過算出的hash值楞艾，算出key在數(shù)組table中的索引i
int i = indexFor(hash, table.length);
//遍歷鏈表節(jié)點，去比較hash和key與節(jié)點 e.key 是否相等
for (HashMap.Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
//如果有相等的節(jié)點龄广，把 value 賦值到節(jié)點的value上硫眯，返回原來的節(jié)點e的value
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//沒有沖突或者相等的節(jié)點就新加一個節(jié)點
addEntry(hash, key, value, i);
return null;
}
分析addEntry方法：
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
//當(dāng)size大于初始化的threshold的時候，需要調(diào)用resize方法擴容
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
分析擴容方法resize,該方法主要做了擴容择同，并且創(chuàng)建了個新的Entry<K,V>數(shù)組table,并且調(diào)用transfer方法把老的數(shù)組table中的元素轉(zhuǎn)存到新的數(shù)組table中去：
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//創(chuàng)建新的數(shù)組
Entry[] newTable = new Entry[newCapacity];
//調(diào)用transfer方法两入，把老數(shù)組中的元素轉(zhuǎn)存到新數(shù)組中去
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
再分析轉(zhuǎn)存方法transfer，在這有循環(huán)敲才，有鏈表的next節(jié)點賦值裹纳，可以猜測是因為單鏈表形成了環(huán)造成的死循環(huán)
void transfer(Entry[] newTable, boolean rehash) {
//把舊的數(shù)據(jù)轉(zhuǎn)存到新的table中
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
//在這有循環(huán)，有鏈表的next節(jié)點賦值紧武，
Entry<K,V> next = e.next; //(1)
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;
}
}
}
分析執(zhí)行過程：
//假設(shè)map只能放置兩個元素剃氧，其中的threshold為1
Map<Integer,String> map = new HashMap<>(2);
//并且為了方便分析，
//假設(shè)hashMap阻星，計算索引的方法為偶數(shù)的index為0她我，奇數(shù)的index為1
//現(xiàn)在添加兩個元素
map.put(1,"A");
map.put(3,"B");
那么，現(xiàn)在map的存儲情況如下：
當(dāng)我們再次put 一組數(shù)據(jù)的時候番舆，map.put(2,"C")時，由于計算出索引是0矾踱，所以添加的時候需要擴容恨狈，此時如果在多線程環(huán)境下，假設(shè)：線程1執(zhí)行到transfer方法(1)位置處呛讲，線程2獲得了cpu執(zhí)行權(quán)禾怠，線程2進(jìn)行了擴容，執(zhí)行了轉(zhuǎn)存方法transfer把舊的table變成新的table（在線程2的私有棧中）嗎贝搁，在寫到內(nèi)存中
//先獲取table中的元素e
for (Entry<K,V> e : table) {
while(null != e) {
//進(jìn)入while循環(huán)吗氏，獲取節(jié)點e的next節(jié)點，直到next節(jié)點為null
//循環(huán)結(jié)束
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//計算出e節(jié)點在新table中的索引
int i = indexFor(e.hash, newCapacity);
//把節(jié)點e轉(zhuǎn)存到新table中
//沖突鏈表轉(zhuǎn)存的方式為頭插法
//即的節(jié)點e的next節(jié)點作為節(jié)點e的頭
//換種方式講雷逆，在新的table中弦讽，節(jié)點e變成了next
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
執(zhí)行過程如圖：
此時，線程1獲取cpu執(zhí)行權(quán)膀哲，按照上述過程進(jìn)行數(shù)據(jù)轉(zhuǎn)存執(zhí)行過程如下往产，第一次進(jìn)入循環(huán)中：
while(null != e) {
//第一次進(jìn)入循環(huán)時
/*假設(shè)此時線程1讀取的線程1棧中的數(shù)據(jù)
沖突鏈的結(jié)構(gòu)還是 k:1 v:A(e) -> k:3 v:B(next) -> null
k:1 v:A 為當(dāng)前節(jié)點e,e.next為節(jié)點k:3 v:B,節(jié)點k:3 v:B的next為null
*/
Entry<K,V> next = e.next;
//next 為 節(jié)點k:3 v:B
......
}
第二次進(jìn)入循環(huán)中：
for (Entry<K,V> e : table) {
while(null != e) {
//第二次進(jìn)入循環(huán)
/*假設(shè)此時線程1讀取的線程是線程2寫入到內(nèi)存中的數(shù)據(jù)
此時，節(jié)點e為 k:3 v:B某宪，但是線程2中節(jié)點e k:3 v:B的next
指向了節(jié)點 k:1 v:A仿村，所以獲取的next節(jié)點不為空，
循環(huán)沒有結(jié)束兴喂，
其實蔼囊，沖突鏈已經(jīng)成了環(huán)，所以while無法結(jié)束衣迷，程序陷入了死循環(huán)畏鼓。
*/
Entry<K,V> next = e.next;
......
}
}
根據(jù)上述分析，HashMap在多線程情況下蘑险，put的時候滴肿，擴容條用轉(zhuǎn)存方法transfer時，沖突鏈可能會形成環(huán)佃迄，導(dǎo)致while循環(huán)無法結(jié)束泼差，所以導(dǎo)致文章開頭所描述的情形，創(chuàng)建一萬個線程呵俏，每個線程put一個隨機UUID堆缘，執(zhí)行過程中，有時會發(fā)生死循環(huán)的現(xiàn)象普碎。
歡迎大家來交流吼肥，指出文中一些說錯的地方，有錯誤的地方希望大家多多提出來，讓我加深認(rèn)識缀皱。
ConcurrentHashMap的實現(xiàn)原理與使用斗这，放到下幾篇文章里面說吧。
謝謝大家啤斗！
