[[355436]]

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

如果你是個 Java 程序員，那一定對 HashMap 不陌生，巧的是只要你去面試，大概率都會被問到 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ù)組 + 鏈表 的形式來實現(xiàn)的， 1.7 版本是這個樣子：

1.8 版本是這樣：

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

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

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

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

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

因為鏈表的時間復(fù)雜度是 n/2 ，紅黑樹時間復(fù)雜度是 logn ，當(dāng) n 等于 8 的時候， log8 要比 8/2 小，這個時候紅黑樹的查找速度會更快一些

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

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

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

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

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

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

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

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

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

擴容完畢之后，因為采用的是頭插法，所以后面的元素會放在頭部位置，那么就可能會這樣：

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

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

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

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

因為 HashMap 對 put 操作沒有進行加鎖的操作，那么就不能保證下一個線程 get 到的值，就一定是沒有被修改過的值，所以 HashMap 是不安全的

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

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

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

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

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

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