Java集合篇：HashMap 与 ConcurrentHashMap 原理总结
一、HashMap原理總結：
1、什么是HashMap：
（1）HashMap 是基于 Map 接口的非同步實現，線程不安全，是為了快速存取而設計的；它采用 key-value 鍵值對的形式存放元素（并封裝成 Node 對象），允許使用 null 鍵和 null 值，但只允許存在一個鍵為 null，并且存放在 Node[0] 的位置，不過允許存在多個 value 為 null 的情況。
（2）在 JDK7 及之前的版本，HashMap 的數據結構可以看成“數組+鏈表”，在 JDK8 及之后的版本，數據結構可以看成"數組+鏈表+紅黑樹"，也就是說 HashMap ?底層采用數組實現，數組的每個位置都存儲一個單向鏈表，當鏈表的長度超過一定的閾值時，就會轉換成紅黑樹。轉換的目的是當鏈表中元素較多時，也能保證HashMap的存取效率（備注：鏈表轉為紅黑樹只有在數組的長度大于等于64才會觸發）
（3）HashMap 有兩個影響性能的關鍵參數：“初始容量”和“加載因子”：
- 容量 capacity：就是哈希表中數組的數量，默認初始容量是16，容量必須是2的N次冪，這是為了提高計算機的執行效率。
- 加載因子 loadfactor：在 HashMap 擴容之前，容量可以達到多滿的程度，默認值為 0.75
- 擴容閾值 threshold = capacity * loadfactor
（4）采用 Fail-Fast 機制，底層通過一個 modCount 值記錄修改的次數，對 HashMap 的修改操作都會增加這個值。迭代器在初始過程中會將這個值賦給 exceptedModCount ，在迭代的過程中，如果發現 modCount 和 exceptedModCount 的值不一致，代表有其他線程修改了Map，就立刻拋出異常。
2、HashMap 的 put() 方法添加元素的過程：
（1）重新計算 hash 值：
拿到 key 的 hashcode 值之后，調用 hash() 方法重新計算 hash 值，防止質量低下的 hashCode() 函數出現，從而使 hash 值的分布盡量均勻。
JDK8 及之后的版本，對 hash() 方法進行了優化，重新計算 hash 值時，讓 hashCode 的高16位參與異或運算，目的是即使 table 數組的長度較小，在計算元素存儲位置時，也能讓高位也參與運算。
（key == null）? 0 : ( h = key.hashcode()) ^ (h >>> 16)
（2）計算元素存放在數組中的哪個位置：
將重新計算出來的 hash 值與 (tablel.length-1) 進行位與&運算，得出元素應該放入數組的哪個位置。
為什么 HashMap 的底層數組長度總是2的n次方冪？因為當 length 為2的n次方時，h & (length - 1) 就相當于對 length 取模，而且速度比直接取模要快得多，二者等價不等效，這是HashMap在性能上的一個優化
（3）將 key-value 添加到數組中：
① 如果計算出的數組位置上為空，那么直接將這個元素插入放到該位置中。
② 如果數組該位置上已經存在鏈表，則使用 equals() 比較鏈表上是否存在 key 相同的節點，如果為true，則替換原元素；如果不存在，則在鏈表的尾部插入新節點（Jdk1.7及以前的版本使用的頭插法）
③ 如果插入元素后，如果鏈表的節點數是否超過8個，則調用 treeifyBin() 將鏈表節點轉為紅黑樹節點。
④ 最后判斷 HashMap 總容量是否超過閾值 threshold，則調用 resize() 方法進行擴容，擴容后數組的長度變成原來的2倍。
?在 HashMap 中，當發生hash沖突時，解決方式是采用拉鏈法，也就是將所有哈希值相同的記錄都放在同一個鏈表中，除此之外，解決hash沖突的方式有：
- 開放地址法（線性探測再散列、二次探測再散列、偽隨機探測再散列）：當沖突發生時，在散列表中形成一個探測序列，沿此序列逐個單元地查找，直到找到給定的關鍵字，或者碰到一個開放的地址為止（即該地址單元為空）。如果是插入的情況，在探查到開放的地址，則可將待插入的新結點存入該地址單元，如果是查找的情況，探查到開放的地址則表明表中無待查的關鍵字，即查找失敗。
- 再哈希法：產生沖突時，使用另外的哈希函數計算出一個新的哈希地址、直到沖突不再發生
- 建立一個公共溢出區：把沖突的記錄都放在另一個存儲空間，不放在表里面。
3、HashMap擴容的過程：
（1）重新建立一個新的數組，長度為原數組的兩倍；
（2）遍歷舊數組的每個數據，重新計算每個元素在新數組中的存儲位置。使用節點的hash值與舊數組長度進行位與運算，如果運算結果為0，表示元素在新數組中的位置不變；否則，則在新數組中的位置下標=原位置+原數組長度。
（3）將舊數組上的每個數據使用尾插法逐個轉移到新數組中，并重新設置擴容閾值。
問題：為什么擴容時節點重 hash 只可能分布在原索引位置或者 原索引長度+oldCap 位置呢？換句話說，擴容時使用節點的hash值跟oldCap進行位與運算，以此決定將節點分布到原索引位置或者原索引+oldCap位置上的原理是什么呢？
假設老表的容量為16，則新表容量為16*2=32，假設節點1的hash值為 0000 0000 0000 0000 0000 1111 0000 1010，節點2的hash值為 0000 0000 0000 0000 0000 1111 0001 1010。
那么節點1和節點2在老表的索引位置計算如下圖計算1，由于老表的長度限制，節點1和節點2的索引位置只取決于節點hash值的最后4位。再看計算2，計算2為元素在新表中的索引計算，可以看出如果兩個節點在老表的索引位置相同，則新表的索引位置只取決于節點hash值倒數第5位的值，而此位置的值剛好為老表的容量值16，此時節點在新表的索引位置只有兩種情況：原索引位置和 原索引+oldCap位置（在此例中即為10和10+16=26）。由于結果只取決于節點hash值的倒數第5位，而此位置的值剛好為老表的容量值16，因此此時新表的索引位置的計算可以替換為計算3，直接使用節點的hash值與老表的容量16進行位于運算，如果結果為0則該節點在新表的索引位置為原索引位置，否則該節點在新表的索引位置為 原索引+ oldCap 位置。
4、HashMap 鏈表轉換成紅黑樹：
當數組中某個位置的節點達到8個時，會觸發 treeifyBin() 方法將鏈表節點（Node）轉紅黑樹節點（TreeNode，間接繼承Node），轉成紅黑樹節點后，其實鏈表的結構還存在，通過next屬性維持，紅黑樹節點在進行操作時都會維護鏈表的結構，并不是轉為紅黑樹節點后，鏈表結構就不存在了。當數組中某個位置的節點在移除后達到6個時，并且該索引位置的節點為紅黑樹節點，會觸發 untreeify() 將紅黑樹節點轉化成鏈表節點。
HashMap 在進行插入和刪除時有可能會觸發紅黑樹的插入平衡調整（balanceInsertion方法）或刪除平衡調整（balanceDeletion ）方法，調整的方式主要有以下手段：左旋轉（rotateLeft方法）、右旋轉（rotateRight方法）、改變節點顏色（x.red = false、x.red = true），進行調整的原因是為了維持紅黑樹的數據結構。
當鏈表長過長時會轉換成紅黑樹，那能不能使用AVL樹替代呢？
AVL樹是完全平衡二叉樹，要求每個結點的左右子樹的高度之差的絕對值最多為1，而紅黑樹通過適當的放低該條件（紅黑樹限制從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長，結果是這個樹大致上是平衡的），以此來減少插入/刪除時的平衡調整耗時，從而獲取更好的性能，雖然會導致紅黑樹的查詢會比AVL稍慢，但相比插入/刪除時獲取的時間，這個付出在大多數情況下顯然是值得的。
5、HashMap 在 JDK7 和 JDK8 有哪些區別?
① 數據結構：在 JDK7 及之前的版本，HashMap 的數據結構可以看成“數組+鏈表”，在 JDK8 及之后的版本，數據結構可以看成"數組+鏈表+紅黑樹"，當鏈表的長度超過8時，鏈表就會轉換成紅黑樹
② 對數據重哈希：JDK8 及之后的版本，對 hash() 方法進行了優化，重新計算 hash 值時，讓 hashCode 的高16位參與異或運算，目的是在 table 的 length較小的時候，在進行計算元素存儲位置時，也讓高位也參與運算。
③ 在 JDK7 及之前的版本，在添加元素的時候，采用頭插法，所以在擴容的時候，會導致之前元素相對位置倒置了，在多線程環境下擴容可能造成環形鏈表而導致死循環的問題。DK1.8之后使用的是尾插法，擴容是不會改變元素的相對位置
④ 擴容時重新計算元素的存儲位置的方式：JDK7 及之前的版本重新計算存儲位置是直接使用 hash & (table.length-1)；JDK8 使用節點的hash值與舊數組長度進行位與運算，如果運算結果為0，表示元素在新數組中的位置不變；否則，則在新數組中的位置下標=原位置+原數組長度。
6、線程不安全的體現？如何變成線程安全：
無論在 JDK7 還是 JDK8 的版本中，HashMap 都是線程不安全的，HashMap 的線程不安全主要體現在以下兩個方面：
- 在JDK7及以前的版本，表現為在多線程環境下進行擴容，由于采用頭插法，位于同一索引位置的節點順序會反掉，導致可能出現死循環的情況
- 在JDK8及以后的版本，表現為在多線程環境下添加元素，可能會出現數據丟失的情況
如果想使用線程安全的 Map 容器，可以使用以下幾種方式：
（1）使用線程安全的 Hashtable，它底層的每個方法都使用了 synchronized 保證線程同步，所以每次都鎖住整張表，在性能方面會相對比較低。
除了線程安全性方面，Hashtable 和 HashMap 的不同之處還有：
- 繼承的父類：兩者都實現了 Map 接口，但 HashMap 繼承自 AbstractMap 類，而 Hashtable 繼承自 Dictionary 類
- 遍歷方式：HashMap 僅支持 Iterator 的遍歷方式，但 Hashtable 實現了 Enumeration 接口，所以支持Iterator和Enumeration兩種遍歷方式
- 使用方式：HashMap 允許 null 鍵和 null 值，Hashtable 不允許 null? 鍵和 null?值
- 數據結構：HashMap 底層使用“數組+鏈表+紅黑樹”，Hashtable 底層使用“數組+鏈表”
- 初始容量及擴容方式：HashMap 的默認初始容量為16，每次擴容為原來的2倍；Hashtable 默認初始容量為11，每次擴容為原來的2倍+1。
- 元素的hash值：HashMap的hash值是重新計算過的，Hashtable直接使用Object的hashCode；
之所以會出現初始容量以及元素hash值計算方式的不同，是因為 HashMap 和 Hashtable 設計時的側重點不同。Hashtable 的側重點是哈希結果更加均勻，使得哈希沖突減少，當哈希表的大小為素數時，簡單的取模哈希的結果會更加均勻。而 HashMap 則更加關注哈希的計算效率問題，在取模計算時，如果模數是2的冪，那么我們可以直接使用位運算來得到結果，效率要大大高于做除法。
有關 Hashtable 的內容，可以詳細閱讀：Hashtable原理詳解（JDK1.8）
（2）使用Collections.synchronizedMap()方法來獲取一個線程安全的集合，底層原理是使用synchronized來保證線程同步。
（3）使用 ConcurrentHashMap 集合。
JDK7 版本的 HahsMap 源碼解析：https://blog.csdn.net/a745233700/article/details/83108880
JDK8 版本的 HahsMap 源碼解析：https://blog.csdn.net/a745233700/article/details/85126716
二、ConcurrentHashMap 原理（JDK8）：
1、ConcurrentHashMap 的實現原理：
在 JDK8 及以上的版本中，ConcurrentHashMap 的底層數據結構依然采用“數組+鏈表+紅黑樹”，但是在實現線程安全性方面，拋棄了 JDK7 版本的 Segment分段鎖的概念，而是采用了 synchronized + CAS 算法來保證線程安全。在ConcurrentHashMap中，大量使用 Unsafe.compareAndSwapXXX 的方法，這類方法是利用一個CAS算法實現無鎖化的修改值操作，可以大大減少使用加鎖造成的性能消耗。這個算法的基本思想就是不斷比較當前內存中的變量值和你預期變量值是否相等，如果相等，則接受修改的值，否則拒絕你的而操作。因為當前線程中的值已經不是最新的值，你的修改很可能會覆蓋掉其他線程修改的結果。
2、擴容方法 transfer()：
ConcurrentHashMap 為了減少擴容帶來的時間影響，在擴容過程中沒有進行加鎖，并且支持多線程進行擴容操作。在擴容過程中主要使用 sizeCtl 和 transferIndex 這兩個屬性來協調多線程之間的并發操作，并且在擴容過程中大部分數據可以做到訪問不阻塞，整個擴容操作分為以下幾個步驟：
2.1、根據 CPU 核數和數組長度，計算每個線程應該處理的桶數量，如果CPU為單核，則使用一個線程處理所有桶
2.2、根據當前數組長度n，新建一個兩倍長度的數組 nextTable（該這個步驟是單線程執行的）
2.3、將原來 table 中的元素復制到 nextTable 中，這里允許多線程進行操作，具體操作步驟如下：
（1）初始化 ForwardingNode 對象，充當占位節點，hash 值為 -1，該占位對象存在時表示集合正在擴容狀態。
ForwardingNode 的 key、value、next 屬性均為 null ，nextTable 屬性指向擴容后的數組，它的作用主要有以下兩個：
- 占位作用，用于標識數組該位置的桶已經遷移完畢
- 作為一個轉發的作用，擴容期間如果遇到查詢操作，遇到轉發節點，會把該查詢操作轉發到新的數組上去，不會阻塞查詢操作。
（2）通過 for 循環從右往左依次遷移當前線程所負責數組：
① 如果當前桶沒有元素，則直接通過 CAS 放置一個 ForwardingNode 占位對象，以便查詢操作的轉發和標識當前位置已經被處理過。
② 如果線程遍歷到節點的 hash 值為 MOVE，也就是 -1（即 ForwardingNode 節點），則直接跳過，繼續處理下一個桶中的節點
③ 如果不滿足上面兩種情況，則直接給當前桶節點加上 synchronized 鎖，然后重新計算該桶的元素在新數組中的應該存放的位置，并進行數據遷移。重計算節點的存放位置時，通過 CAS 把低位節點 lowNode 設置到新數組的 i 位置，高位節點 highNode 設置到 i+n 的位置（i 表示在原數組的位置，n表示原數組的長度）
- 如果數組中的節點是鏈表結構，則順序遍歷鏈表并使用頭插法進行構造新鏈表
- 如果數組中的節點是紅黑樹結構，則for循環以鏈表方式遍歷整棵紅黑樹，使用尾插法拼接
④ 當前桶位置的數據遷移完成后，將 ForwardingNode 占位符對象設置到當前桶位置上，表示該位置已經被處理了
2.4、每當一條線程擴容結束就會更新一次 sizeCtl 的值，進行減 1 操作，當最后一條線程擴容結束后，需要重新檢查一遍數組，防止有遺漏未成功遷移的桶。擴容結束后，將 nextTable 設置為 null，表示擴容已結束，將 table 指向新數組，sizeCtl 設置為擴容閾值。
sizeCtl：是一個控制標識符，在不同的地方有不同用途，它不同的取值不同也代表不同的含義。在擴容時，它代表的是當前并發擴容的線程數量
- 負數代表正在進行初始化或擴容操作：-1代表正在初始化，-N 表示有N-1個線程正在進行擴容操作
- 正數或0代表hash表還沒有被初始化或下一次進行擴容的大小，這一點類似于擴容閾值的概念。
3、put() 方法的 helpTransfer() 協助擴容：
put() 在多線程情況下可能有以下兩種情況：
- 如果檢測到 ConcurrentHashMap 正在進行擴容操作，也就是當前桶位置上被插入了 ForwardingNode 節點，那么當前線程也要協助進行擴容，協助擴容時會調用 helpTransfer() 方法，當方法被調用的時候，當前 ConcurrentHashMap 一定已經有了 nextTable 對象，首先拿到這個 nextTable 對象，調用transfer方法。
- 如果檢測到要插入的節點是非空且不是 ForwardingNode ?節點，就對這個節點加鎖，這樣就保證了線程安全。盡管這個有一些影響效率，但是還是會比hashTable 的 synchronized 要好得多。
有關擴容的源碼解析可以閱讀該文章：https://blog.csdn.net/ZOKEKAI/article/details/90051567
三、ConcurrentHashMap 原理（JDK7）：
在第二部分我們提到 JDK8 和 JDK7 中 ConcurrentHashMap 的設計是不一樣的，那么下面我們就簡單介紹一下 JDK7 中 ConcurrentHashMap 的實現：
1、ConcurrentHashMap實現的原理：
在 JDK7 中，ConcurrentHashMap 使用“分段鎖”機制實現線程安全，數據結構可以看成是"Segment數組+HashEntry數組+鏈表"，一個 ConcurrentHashMap 實例中包含若干個 Segment 實例組成的數組，每個 Segment 實例又包含由若干個桶，每個桶中都是由若干個 HashEntry 對象鏈接起來的鏈表。
因為Segment 類繼承 ReentrantLock 類，所以能充當鎖的角色，通過 segment 段將 ConcurrentHashMap 劃分為不同的部分，就可以使用不同的鎖來控制對哈希表不同部分的修改，從而允許多個寫操作并發進行，默認支持 16 個線程執行并發寫操作，及任意數量線程的讀操作。
?2、ConcurrentHashMap 的 put() 方法添加元素的過程：
（1）對 key 值進行重哈希，并使用重哈希的結果與 segmentFor() 方法， 計算出元素具體分到哪個 segment 中。插入元素前，先使用 lock() 對該 segment 加鎖，之后再使用頭插法插入元素。如果其他線程經過計算也是放在這個 segment 下，則需要先獲取鎖，如果計算得出放在其他的 segment，則正常執行，不會影響效率，以此實現線程安全，這樣就能夠保證只要多個修改操作不發生在同一個 segment ?時，它們就可以并發進行。
（2）在將元素插入到 segment 前，會檢查本次插入會不會導致 segment 中元素的數量超過閾值，如果會，那么就先對 segment 進行擴容和重哈希操作，然后再進行插入。而重哈希操作，實際上是對 ConcurrentHashMap 的某個 segment 的重哈希，因此 ConcurrentHashMap 的每個 segment 段所包含的桶位也就不盡相同。
如果元素的 hash 值與原數組長度進行位與運算，得到的結果為0，那么元素在新桶的序號就是和原桶的序號是相等的；否則元素在新桶的序號就是原桶的序號加上原數組的長度
3、ConcurrentHashMap 讀操作為什么不需要加鎖？
（1）在 HashEntry 類中，key，hash 和 next 域都被聲明為 final 的，value 域被 volatile 所修飾，因此 HashEntry 對象幾乎是不可變的，通過 HashEntry 對象的不變性來降低讀操作對加鎖的需求
next 域被聲明為 final，意味著不能從hash鏈的中間或尾部添加或刪除節點，因為這需要修改 next 引用值，因此所有的節點的修改只能從頭部開始。但是對于 remove 操作，需要將要刪除節點的前面所有節點整個復制一遍，最后一個節點指向要刪除結點的下一個結點。
（2）用 volatile 變量協調讀寫線程間的內存可見性；
（3）若讀時發生指令重排序現象（也就是讀到 value 域的值為 null 的時候），則加鎖重讀；
4、ConcurrentHashMap 的跨端操作：
ConcurrentHashMap 的跨段操作：比如 size() 計算集合中元素的總個數。首先為了并發性的考慮，ConcurrentHashMap 并沒有使用全局計數器，而是分別在每個 segment 中使用一個 volatile 修飾的計數器count，這樣當需要更新計數器時，不用鎖定整個 ConcurrentHashMap。而 size() 在統計時，是先嘗試 RETRIES_BEFORE_LOCK 次（默認是兩次）通過不鎖住 Segment 的方式來統計各個 Segment 大小，如果統計的過程中，容器的count發生了變化，則再采用對所有 segment 段加鎖的方式來統計所有Segment的大小。
JDK7 版本的 ConcurrentHashMap 源碼解析：https://blog.csdn.net/a745233700/article/details/83120464
JDK8 版本的 ConcurrentHashMap 源碼解析：https://blog.csdn.net/a745233700/article/details/83123359
總結
以上是生活随笔為你收集整理的Java集合篇：HashMap 与 ConcurrentHashMap 原理总结的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Redis的分布式锁详解
- 下一篇： G1 垃圾收集器原理详解