1.7中HashMap死循環(huán)分析
在多線程環(huán)境下，使用HashMap進(jìn)行put操作會(huì)引起死循環(huán)犬庇，導(dǎo)致CPU利用率接近100%，HashMap在并發(fā)執(zhí)行put操作時(shí)會(huì)引起死循環(huán)，是因?yàn)槎嗑€程會(huì)導(dǎo)致HashMap的Entry鏈表
形成環(huán)形數(shù)據(jù)結(jié)構(gòu)，一旦形成環(huán)形數(shù)據(jù)結(jié)構(gòu)躏筏，Entry的next節(jié)點(diǎn)永遠(yuǎn)不為空，就會(huì)產(chǎn)生死循環(huán)獲取Entry呈枉。那么這個(gè)死循環(huán)是如何生成的呢趁尼？我們來仔細(xì)分析下。
HashMap擴(kuò)容流程
原理
引發(fā)死循環(huán)猖辫，是在HashMap的擴(kuò)容操作中酥泞。
正常的擴(kuò)容操作是這個(gè)流程。HashMap的擴(kuò)容在put操作中會(huì)觸發(fā)擴(kuò)容啃憎，主要是三個(gè)方法：
綜合來說芝囤，HashMap一次擴(kuò)容的過程：
1、取當(dāng)前table的2倍作為新table的大小
2辛萍、根據(jù)算出的新table的大小new出一個(gè)新的Entry數(shù)組來悯姊，名為newTable
3、輪詢?cè)璽able的每一個(gè)位置贩毕，將每個(gè)位置上連接的Entry悯许，算出在新table上的位置，并以鏈表形式連接
4辉阶、原table上的所有Entry全部輪詢完畢之后先壕，意味著原table上面的所有Entry已經(jīng)移到了新的table上瘩扼，HashMap中的table指向newTable
實(shí)例
現(xiàn)在hashmap中有三個(gè)元素，Hash表的size=2, 所以key = 3, 7, 5垃僚，在mod 2以后都沖突在table[1]這里了集绰。
按照方法中的代碼
對(duì)table[1]中的鏈表來說，進(jìn)入while循環(huán)谆棺，此時(shí)e=key(3)栽燕，那么next=key(7)，經(jīng)過計(jì)算重新定位e=key(3)在新表中的位置包券，并把e=key(3)掛在newTable[3]的位置
這樣循環(huán)下去纫谅，將table[1]中的鏈表循環(huán)完成后，于是HashMap就完成了擴(kuò)容
并發(fā)下的擴(kuò)容
上面都是單線程下的擴(kuò)容溅固，當(dāng)多線程進(jìn)行擴(kuò)容時(shí)付秕，會(huì)是什么樣子呢？
初始的HashM還是：
我們現(xiàn)在假設(shè)有兩個(gè)線程并發(fā)操作侍郭，都進(jìn)入了擴(kuò)容操作询吴，
回顧我們的擴(kuò)容代碼，我們假設(shè)亮元，線程1執(zhí)行到Entry<K,V> next = e.next;時(shí)被操作系統(tǒng)調(diào)度掛起了猛计，而線程2執(zhí)行完成了擴(kuò)容操作
于是，在線程1,2看來爆捞，就應(yīng)該是這個(gè)樣子
接下來奉瘤，線程1被調(diào)度回來執(zhí)行：
1）
2）
3）
4）
5）
6）
7）
循環(huán)列表產(chǎn)生后，一旦線程1調(diào)用get（11,15之類的元素）時(shí)煮甥，就會(huì)進(jìn)入一個(gè)死循環(huán)的情況盗温，將CPU的消耗到100%。
總結(jié)
HashMap之所以在并發(fā)下的擴(kuò)容造成死循環(huán)成肘，是因?yàn)槁艟郑鄠€(gè)線程并發(fā)進(jìn)行時(shí)，因?yàn)橐粋€(gè)線程先期完成了擴(kuò)容双霍，將原Map的鏈表重新散列到自己的表中砚偶，并且鏈表變成了倒序，后一個(gè)線程再擴(kuò)容時(shí)洒闸，又進(jìn)行自己的散列染坯，再次將倒序鏈表變?yōu)檎蜴湵怼Ｓ谑切纬闪艘粋€(gè)環(huán)形鏈表丘逸，當(dāng)get表中不存在的元素時(shí)酒请，造成死循環(huán)。
