本文通過源碼分析并發(fā)情況下jdk1.7中HashMap形成的著名的死循環(huán)問題。
進(jìn)入分析模式以前了解下幾個必備知識點：
1.JVM內(nèi)存模型
本文只做必要的簡單介紹
主內(nèi)存、工作內(nèi)存、執(zhí)行引擎
2.put源碼邏輯流程
3.HashMap.Entry結(jié)構(gòu)
好了, 熟悉以上知識點后，可以開始按照假定的線程執(zhí)行步驟來重現(xiàn)環(huán)的形成和死循環(huán)的發(fā)生
1.初始化一個Map
final Map<String, Object> map = new HashMap<String, Object>(4);
2.線程安全的put三個對象
map.put("1","S");
map.put("7","A");
map.put("13","C");
此時在堆中已經(jīng)為HashMap分配一塊內(nèi)存,結(jié)構(gòu)如下
3.用多線程制造并發(fā)put
ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
for(int i = 0; i<1000;i++){
? ? ? ? executor.execute(new Thread(){
public void run(){
map.put(Math.random()*10+"", "hello world");
}
});
}
executor.shutdown();
4.假設(shè)此時并發(fā)線程thread1發(fā)起操作put("17","A");擴(kuò)容觸發(fā)執(zhí)行到途中綠框那一行,cpu分配的時間片用完,上下文切換,table保存到thread1工作內(nèi)存中
5.假設(shè)此時并發(fā)線程thread2發(fā)起操作put("27","Aa");觸發(fā)擴(kuò)容發(fā)生;繼續(xù)假設(shè)thread2有夠多的時間片;可以循環(huán)足夠次數(shù)將原始的hashMap中的元素全部轉(zhuǎn)移，以下藍(lán)框內(nèi)代碼循環(huán)三次
6.轉(zhuǎn)移第一次循環(huán)后
7.轉(zhuǎn)移第二次循環(huán)后;讓我們假設(shè)第二次循環(huán)在newTable上的哈希后下標(biāo)和第一個元素是在同一下標(biāo)(此二連續(xù)的位置分配在同一下標(biāo)是后面形成環(huán)的必要條件)
8.轉(zhuǎn)移第三次循環(huán)后;讓我們假設(shè)第三次循環(huán)在newTable上的哈希后下標(biāo)和第一,第二個元素不是同一下標(biāo)
9.擴(kuò)容完成thread2將工作空間了的的newTable賦值給table
并加入新對象后
10.這時thread2執(zhí)行完成,thread1分配的CPU執(zhí)行周期爭取到了執(zhí)行時間
假設(shè)執(zhí)行此代碼的系統(tǒng)優(yōu)化結(jié)果是store-load;store-store指令未重排序
11.thread1接著綠色框框內(nèi)的往下執(zhí)行
12.thread1循環(huán)執(zhí)行
13.thread1循環(huán)執(zhí)行;形成環(huán)
14.thread1執(zhí)行賦值
15.死循環(huán)的形成有兩種情況:
a.此時thread3來put元素落在下標(biāo)5上且造成再一次擴(kuò)容,則會陷入死循環(huán)
b.get元素的key下標(biāo)值也是5且不是這兩個元素中的任何一個, 則會陷入死循環(huán)
源碼如下:
總結(jié): 根本原因是HashMap中的table是共享且非線程安全的。
在觸發(fā)擴(kuò)容條件時,并發(fā)對HashMap的table進(jìn)行擴(kuò)容時會對table逆序轉(zhuǎn)移,有可能造成環(huán)的形成,形成環(huán)之后循環(huán)取元素時造成死循環(huán)
