[[355436]]

本文轉(zhuǎn)載自微信公眾號「Java極客技術(shù)」，作者鴨血粉絲 。轉(zhuǎn)載本文請聯(lián)系Java極客技術(shù)公眾號。  

如果你是個(gè) Java 程序員，那一定對 HashMap 不陌生，巧的是只要你去面試，大概率都會(huì)被問到 HashMap 的相關(guān)內(nèi)容

那這篇文章你就一定要讀一讀了

HashMap 的底層數(shù)據(jù)結(jié)構(gòu)

先來聊聊 HashMap 的底層數(shù)據(jù)結(jié)構(gòu) HashMap 的底層數(shù)據(jù)結(jié)構(gòu)， 1.7 版本和 1.8 版本是有些不同的，但大體上都是 數(shù)組 + 鏈表 的形式來實(shí)現(xiàn)的， 1.7 版本是這個(gè)樣子：

1.8 版本是這樣：

很明顯就能看出來， 1.8 版本怎么多了一個(gè)樹?還是紅黑的?

這就要來分析 1.7 版本 HashMap 的實(shí)現(xiàn)有什么不足了

1.7 版本主要就是 數(shù)組 + 鏈表，那么如果有一個(gè) hash 值總是會(huì)發(fā)生碰撞，那么由此對應(yīng)的鏈表結(jié)構(gòu)也會(huì)越來越長，這個(gè)時(shí)候如果再想要進(jìn)行查詢操作，就會(huì)非常耗時(shí)，所以該如何優(yōu)化這一點(diǎn)就是 1.8 版本想要實(shí)現(xiàn)的

1.8 版本采用了 數(shù)組 + 鏈表 + 紅黑樹 的方式去實(shí)現(xiàn)，當(dāng)鏈表的長度大于 8 時(shí)，就會(huì)將鏈表轉(zhuǎn)為紅黑樹。

這個(gè)時(shí)候問題就來了，為什么會(huì)將鏈表轉(zhuǎn)紅黑樹的值設(shè)定為 8 ?

因?yàn)殒湵淼臅r(shí)間復(fù)雜度是 n/2 ，紅黑樹時(shí)間復(fù)雜度是 logn ，當(dāng) n 等于 8 的時(shí)候， log8 要比 8/2 小，這個(gè)時(shí)候紅黑樹的查找速度會(huì)更快一些

為什么是小于 6 的時(shí)候轉(zhuǎn)為鏈表，而不是 7 的時(shí)候就轉(zhuǎn)為鏈表呢?頻繁的從鏈表轉(zhuǎn)到紅黑樹，再從紅黑樹轉(zhuǎn)到鏈表，開銷會(huì)很大，特別是頻繁的從鏈表轉(zhuǎn)到紅黑樹時(shí)，需要旋轉(zhuǎn)

為什么將鏈表轉(zhuǎn)為紅黑樹，而不是平衡二叉樹( AVL 樹)呢?

• 因?yàn)?AVL 樹比紅黑樹保持著更加嚴(yán)格的平衡， AVL 樹中從根到最深葉的路徑最多為 1.44lg(n + 2) ，紅黑樹中則最多為 2lg( n + 1) ，所以 AVL 樹查找效果會(huì)比較快，如果是查找密集型任務(wù)使用 AVL 樹比較好，相反插入密集型任務(wù)，使用紅黑樹效果就比較 nice
• AVL 樹在每個(gè)節(jié)點(diǎn)上都會(huì)存儲(chǔ)平衡因子
• AVL 樹的旋轉(zhuǎn)比紅黑樹的旋轉(zhuǎn)更加難以平衡和調(diào)試，如果兩個(gè)都給 O(lgn) 查找， AVL 樹可能需要 O(log n) 旋轉(zhuǎn)，而紅黑樹最多需要兩次旋轉(zhuǎn)使其達(dá)到平衡

HashMap 為什么是線程不安全的?

HashMap 的線程不安全主要體現(xiàn)在兩個(gè)方面：擴(kuò)容時(shí)導(dǎo)致的死循環(huán) & 數(shù)據(jù)覆蓋

擴(kuò)容時(shí)導(dǎo)致的死循環(huán)，這個(gè)問題只會(huì)在 1.7 版本及以前出現(xiàn)，因?yàn)樵?1.7 版本及以前，擴(kuò)容時(shí)的實(shí)現(xiàn)，采用的是頭插法，這樣就會(huì)導(dǎo)致循環(huán)鏈表的問題

什么時(shí)候會(huì)觸發(fā)擴(kuò)容呢?如果存儲(chǔ)的數(shù)據(jù)，大于 當(dāng)前的 HashMap 長度( Capacity ) * 負(fù)載因子( LoadFactor ，默認(rèn)為 0.75) 時(shí)，就會(huì)發(fā)生擴(kuò)容。比如當(dāng)前容量是 16 ， 16 * 0.75 = 12 ，當(dāng)存儲(chǔ)第 13 個(gè)元素時(shí)，經(jīng)過判斷發(fā)現(xiàn)需要進(jìn)行擴(kuò)容，那么這個(gè)時(shí)候 HashMap 就會(huì)先進(jìn)行擴(kuò)容的操作

擴(kuò)容也不是簡簡單單的將原來的容量擴(kuò)大就完事兒了，擴(kuò)容時(shí)，首先創(chuàng)建一個(gè)新的 Entry 空數(shù)組，長度是原數(shù)組的 2 倍，擴(kuò)容完畢之后還會(huì)再進(jìn)行 ReHash ，也就是將原 Entry 數(shù)組里面的數(shù)據(jù)，重新 hash 到新數(shù)組里面去

假設(shè)現(xiàn)在有一個(gè) Entry 數(shù)組，大小是 2 ，那么當(dāng)我們插入第 2 個(gè)元素時(shí)，大于 2 * 0.75 那么此時(shí)就會(huì)發(fā)生擴(kuò)容，具體如下圖：

擴(kuò)容完畢之后，因?yàn)椴捎玫氖穷^插法，所以后面的元素會(huì)放在頭部位置，那么就可能會(huì)這樣：

剛開始記錄的是 A.next = B ，經(jīng)過擴(kuò)容之后是 B.next = A ，那么最后可能就是這樣了：

明顯看到造成了死循環(huán)，比較好的是， 1.8 版本之后采用了尾插法，解決了這個(gè)問題

還有個(gè)問題， 1.8 版本是沒有解決的，那就是數(shù)據(jù)覆蓋問題

假設(shè)現(xiàn)在線程 A 和線程 B 同時(shí)進(jìn)行 put 操作，特別巧的是這兩條不同的數(shù)據(jù) hash 值一樣，并且這個(gè)位置數(shù)據(jù)為 null ，那么是不是應(yīng)該讓線程 A 和 B 都執(zhí)行 put 操作。假設(shè)線程 A 在要進(jìn)行插入數(shù)據(jù)時(shí)被掛起，然后線程 B 正常執(zhí)行將數(shù)據(jù)插入了，然后線程 A 獲得了 CPU 時(shí)間片，也開始進(jìn)行數(shù)據(jù)插入操作，那么就將線程 B 的數(shù)據(jù)給覆蓋掉了

因?yàn)?HashMap 對 put 操作沒有進(jìn)行加鎖的操作，那么就不能保證下一個(gè)線程 get 到的值，就一定是沒有被修改過的值，所以 HashMap 是不安全的

那既然 HashMap 線程不安全，你給推薦一個(gè)安全的?

如果推薦的話，那肯定推薦 ConcurrentHashMap ，說到 ConcurrentHashMap 也有一個(gè)比較有趣的事情，那就是 ConcurrentHashMap 的 1.7 版本和 1.8 版本實(shí)現(xiàn)也是不一樣

在 1.7 版本， ConcurrentHashMap 采用的是分段鎖( ReentrantLock + Segment + HashEntry )實(shí)現(xiàn)，也就是將一個(gè) HashMap 分成多個(gè)段，然后每一段都分配一把鎖，這樣去支持多線程環(huán)境下的訪問。但是這樣鎖的粒度太大了，因?yàn)槟沔i的直接就是一段嘛

所以 1.8 版本又做了優(yōu)化，使用 CAS + synchronized + Node + 紅黑樹 來實(shí)現(xiàn)，這樣就將鎖的粒度降低了，同時(shí)使用 synchronized 來加鎖，相比于 ReentrantLock 來說，會(huì)節(jié)省比較多的內(nèi)存空間

HashMap 這塊，其實(shí)還可以擴(kuò)展，比如 HashMap 和 HashTable 的區(qū)別， ConcurrentHashMap 1.7 版本和 1.8 版本具體的實(shí)現(xiàn)，等等等等

但是這篇文章已經(jīng)比較長了，就寫到這里吧~