hashmap設計源碼

㈠ hashmap底層實現原理

hashmap底層實現原理是SortedMap介面能夠把它保存的記錄根據鍵排序，默認是按鍵值的升序排序，也可以指定排序的比較器，當用Iterator遍歷TreeMap時，得到的記錄是排過序的。

如果使用排序的映射，建議使用TreeMap。在使用TreeMap時，key必須實現Comparable介面或者在構造TreeMap傳入自定義的Comparator，否則會在運行時拋出java.lang.ClassCastException類型的異常。

Hashtable是遺留類，很多映射的常用功能與HashMap類似，不同的是它承自Dictionary類，並且是線程安全的，任一時間只有一個線程能寫Hashtable

從結構實現來講，HashMap是：數組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）實現的。

(1)hashmap設計源碼擴展閱讀

從源碼可知，HashMap類中有一個非常重要的欄位，就是 Node[] table，即哈希桶數組。Node是HashMap的一個內部類，實現了Map.Entry介面，本質是就是一個映射(鍵值對)，除了K，V，還包含hash和next。

HashMap就是使用哈希表來存儲的。哈希表為解決沖突，採用鏈地址法來解決問題，鏈地址法，簡單來說，就是數組加鏈表的結合。在每個數組元素上都一個鏈表結構，當數據被Hash後，得到數組下標，把數據放在對應下標元素的鏈表上。

如果哈希桶數組很大，即使較差的Hash演算法也會比較分散，如果哈希桶數組數組很小，即使好的Hash演算法也會出現較多碰撞，所以就需要在空間成本和時間成本之間權衡，其實就是在根據實際情況確定哈希桶數組的大小，並在此基礎上設計好的hash演算法減少Hash碰撞。

㈡ HashMap源碼分析

HashMap（jdk 1.8）
  使用哈希表存儲鍵值對，底層是一個存儲Node的table數組。其基本的運行邏輯是，table數組的每一個元素是一個槽，用於存儲Node對象，向Hash表中插入鍵值對時，首先計算鍵的hash值，並對數組容量（即數組長度）取余，定位該鍵值對應放在哪個槽中，若槽中已經存在元素（即哈希沖突），將Node節點插入到沖突鏈表尾端，當該槽中結點超過一定數量（默認為8）並且哈希表容量超過一定值（默認為64）時，對該鏈表進行樹化。低於一定數量（默認為6）後進行resize時，樹形結構又會鏈表化。當哈希表的總節點數超過閾值時，對哈希表進行擴容，容量翻倍。

由於哈希表需要用到key的哈希函數，因此對於自定義類作為key使用哈希表時，需要重寫哈希函數，保證相等的key哈希值相同。

由於擴容或樹化過程Node節點的位置會發生改變，因此哈希表是無序的，不同時期遍歷同一張哈希表，得到的節點順序會不同。

成員變數

    Hash表的成員變數主要有存儲鍵值對的table數組，size，裝載因子loadFactory，閾值theshold，容量capacity。

table數組：

哈希表的實質就是table數組，它用來存儲鍵值對。哈希表中內部定義了Node類來封裝鍵值對。

 Node類實現了Map的Entry介面。包括key，value，下一個Node指針和key的hash值。

 容量Capacity：

HashMap中沒有專門的屬性存儲容量，容量等於table.lenth，即數組的長度，默認初始化容量為16。初始化時，可以指定哈希表容量，但容量必須是2的整數次冪，在初始化過程中，會調用tableSizeFor函數，得到一個不小於指定容量的2的整數次冪，暫時存入到threshold中。

注意，若容量設置過大，那麼遍歷整個哈希表需要耗費更多的時間。

    閾值threshold：

指定當前hash表最多存儲多少個鍵值對，當size超過閾值時，hash表進行擴容，擴容後容量翻倍。

   loadFactory：

threshold=capacity*loadFactory。

裝填因子的大小決定了哈希表存儲鍵值對數量的能力，它直接影響哈希表的查找性能。初始化時可以指定loadFactory的值，默認為0.75。

 初始化過程

哈希表有3個構造函數，用戶可以指定哈希表的初始容量和裝填因子，但初始化過程只是簡單填入這兩個參數，table數組並沒有初始化。注意，這里的initialCapacity會向上取2的整數次冪並暫時保存到threshold中。

table數組的初始化是在第一次插入鍵值對時觸發，實際在resize函數中進行初始化。

hash過程與下標計算

哈希表是通過key的哈希值決定Node放入哪個槽中， 在java8中 ，hash表沒有直接用key的哈希值，而是自定義了hash函數。

哈希表中的key可以為null，若為null，哈希值為0，否則哈希值（一共32位）的高16位不變，低16位與高16位進行異或操作，得到新的哈希值。（h >>> 16，表示無符號右移16位，高位補0，任何數跟0異或都是其本身，因此key的hash值高16位不變。）

之所以這樣處理，是與table的下標計算有關

因為，table的長度都是2的冪，因此index僅與hash值的低n位有關（n-1為0000011111的形式），hash值的高位都被與操作置為0了，相當於hash值對n取余。

由於index僅與hash值的低n位有關，把哈希值的低16位與高16位進行異或處理，可以讓Node節點能更隨機均勻得放入哈希表中。

get函數：

V  get(Object key) 通過給定的key查找value

先計算key的哈希值，找到對應的槽，遍歷該槽中所有結點，如果結點中的key與查找的key相同或相等，則返回value值，否則返回null。

注意，如果返回值是null，並不一定是沒有這種KV映射，也有可能是該key映射的值value是null，即key-null的映射。也就是說，使用get方法並不能判斷這個key是否存在，只能通過containsKey方法來實現。

put函數

V put(K key, V value) 存放鍵值對

計算key的哈希值，找到哈希表中對應的槽，遍歷該鏈表，如果發現已經存在包含該key的Node，則把新的value放入該結點中，返回該結點的舊value值（舊value可能是null），如果沒有找到，則創建新結點插入到 鏈表尾端 （java7使用的是頭插法），返回null。插入結點後需要判斷該鏈表是否需要樹化，並且判斷整個哈希表是否需要擴容。

由該演算法可以看出，哈希表中不會有兩個key相同的鍵值對。

resize函數

    resize函數用來初始化或擴容table數組。主要做了兩件事。

1.根據table數組是否為空判斷初始化還是擴容，計算出相應的newCap和newThr，新建table數組並設置新的threshold。

2.若是進行擴容，則需要將原數組中的Node移植到新的數組中。

由於數組擴容，原來鍵值對可能存儲在新數組不同的槽中。但由於鍵值對位置是對數組容量取余（index=hash(key)&(Capacity-1)）,由於Capacity固定為2的整數次冪，並新的Capacity（newCap）是舊的兩倍（oldCap）。因此，只需要判斷每個Node中的hash值在oldCap二進制那一位上是否為0(hash&oldCap==0)，若為0，對newCap取余值與oldCap相同，Node在新數組中槽的位置不變，若為1，新的位置是就得位置加一個oldCap值。

因此hashMap的移植演算法是，遍歷舊的槽：

若槽為空，跳過。

若槽只有一個Node，計算該Node在新數組中的位置，放入新槽中。

若槽是一個鏈表，則遍歷這個鏈表，分別用loHead，loTail,hiHead,hiTail兩組指針建立兩個鏈表，把hash值oldCap位為0的Node節點放入lo鏈表中，hash值oldCap位為1的節點放入hi鏈表中，之後將兩個鏈表分別插入到新數組中，實現原鍵值對的移植。

lo鏈表放入新數組原來位置，hi鏈表放入新數組原來位置+oldCap中

樹化過程 ：

當一個槽中結點過多時，哈希表會將鏈表轉換為紅黑樹，此處挖個坑。

[總結] java8中hashMap的實現原理與7之間的區別：

1.hash值的計算方法不同 2.鏈表採用尾插法，之前是頭插法 3.加入了紅黑樹結構

㈢ 怎麼看hashmap和hashtable的源碼

HashMap是Hashtable的輕量級實現（非線程安全的實現），他們都完成了Map介面，主要區別在於HashMap准許空（Null）鍵值（Key），由於非線程安全，效率上可能高於Hashtable。我回答的通俗易懂把！！！

㈣ concurrenthashmap線程安全嗎

ConcurrentHashMap 是 Java 並發包中提供的一個線程安全且高效的 HashMap 實現，以彌補 HashMap 不適合在並發環境中操作使用的不足，本文就來分析下 ConcurrentHashMap 的實現原理，並對其實現原理進行分析！

一、摘要
在之前的集合文章中，我們了解到 HashMap 在多線程環境下操作可能會導致程序死循環的線上故障！

既然在多線程環境下不能使用 HashMap，那如果我們想在多線程環境下操作 map，該怎麼操作呢？

想必閱讀過小編之前寫的《HashMap 在多線程環境下操作可能會導致程序死循環》一文的朋友們一定知道，其中有一個解決辦法就是使用 java 並發包下的 ConcurrentHashMap 類！

今天呢，我們就一起來聊聊 ConcurrentHashMap 這個類！

二、簡介
眾所周知，在 Java 中，HashMap 是非線程安全的，如果想在多線程下安全的操作 map，主要有以下解決方法：

第一種方法，使用Hashtable線程安全類；

第二種方法，使用Collections.synchronizedMap方法，對方法進行加同步鎖；

第三種方法，使用並發包中的ConcurrentHashMap類；

在之前的文章中，關於 Hashtable 類，我們也有所介紹，Hashtable 是一個線程安全的類，Hashtable 幾乎所有的添加、刪除、查詢方法都加了synchronized同步鎖！

相當於給整個哈希表加了一把大鎖，多線程訪問時候，只要有一個線程訪問或操作該對象，那其他線程只能阻塞等待需要的鎖被釋放，在競爭激烈的多線程場景中性能就會非常差，所以 Hashtable 不推薦使用！


再來看看第二種方法，使用Collections.synchronizedMap方法，我們打開 JDK 源碼，部分內容如下：


可以很清晰的看到，如果傳入的是 HashMap 對象，其實也是對 HashMap 做的方法做了一層包裝，裡面使用對象鎖來保證多線程場景下，操作安全，本質也是對 HashMap 進行全表鎖！

使用Collections.synchronizedMap方法，在競爭激烈的多線程環境下性能依然也非常差，所以不推薦使用！

上面 2 種方法，由於都是對方法進行全表鎖，所以在多線程環境下容易造成性能差的問題，因為** hashMap 是數組 + 鏈表的數據結構，如果我們把數組進行分割多段，對每一段分別設計一把同步鎖，這樣在多線程訪問不同段的數據時，就不會存在鎖競爭了，這樣是不是可以有效的提高性能？**

再來看看第三種方法，使用並發包中的ConcurrentHashMap類！

ConcurrentHashMap 類所採用的正是分段鎖的思想，將 HashMap 進行切割，把 HashMap 中的哈希數組切分成小數組，每個小數組有 n 個 HashEntry 組成，其中小數組繼承自ReentrantLock（可重入鎖），這個小數組名叫Segment， 如下圖：



當然，JDK1.7 和 JDK1.8 對 ConcurrentHashMap 的實現有很大的不同！

JDK1.8 對 HashMap 做了改造，當沖突鏈表長度大於 8 時，會將鏈表轉變成紅黑樹結構，上圖是 ConcurrentHashMap 的整體結構，參考 JDK1.7！

我們再來看看 JDK1.8 中 ConcurrentHashMap 的整體結構，內容如下：


JDK1.8 中 ConcurrentHashMap 類取消了 Segment 分段鎖，採用 CAS + synchronized 來保證並發安全，數據結構跟 jdk1.8 中 HashMap 結構類似，都是數組 + 鏈表（當鏈表長度大於 8 時，鏈表結構轉為紅黑二叉樹）結構。

ConcurrentHashMap 中 synchronized 只鎖定當前鏈表或紅黑二叉樹的首節點，只要節點 hash 不沖突，就不會產生並發，相比 JDK1.7 的 ConcurrentHashMap 效率又提升了 N 倍！

說了這么多，我們再一起來看看 ConcurrentHashMap 的源碼實現。

三、JDK1.7 中的 ConcurrentHashMap
JDK 1.7 的 ConcurrentHashMap 採用了非常精妙的分段鎖策略，打開源碼，可以看到 ConcurrentHashMap 的主存是一個 Segment 數組。


我們再來看看 Segment 這個類，在 ConcurrentHashMap 中它是一個靜態內部類，內部結構跟 HashMap 差不多，源碼如下：


存放元素的 HashEntry，也是一個靜態內部類，源碼如下：


HashEntry和HashMap中的 Entry非常類似，唯一的區別就是其中的核心數據如value ，以及next都使用了volatile關鍵字修飾，保證了多線程環境下數據獲取時的可見性！

從類的定義上可以看到，Segment 這個靜態內部類繼承了ReentrantLock類，ReentrantLock是一個可重入鎖，如果了解過多線程的朋友們，對它一定不陌生。

ReentrantLock和synchronized都可以實現對線程進行加鎖，不同點是：ReentrantLock可以指定鎖是公平鎖還是非公平鎖，操作上也更加靈活，關於此類，具體在以後的多線程篇幅中會單獨介紹。

因為ConcurrentHashMap的大體存儲結構和HashMap類似，所以就不對每個方法進行單獨分析介紹了，關於HashMap的分析，有興趣的朋友可以參閱小編之前寫的《深入分析 HashMap》一文。

ConcurrentHashMap 在存儲方面是一個 Segment 數組，一個 Segment 就是一個子哈希表，Segment 里維護了一個 HashEntry 數組，其中 Segment 繼承自 ReentrantLock，並發環境下，對於不同的 Segment 數據進行操作是不用考慮鎖競爭的，因此不會像 Hashtable 那樣不管是添加、刪除、查詢操作都需要同步處理。

理論上 ConcurrentHashMap 支持 concurrentLevel（通過 Segment 數組長度計算得來） 個線程並發操作，每當一個線程獨佔一把鎖訪問 Segment 時，不會影響到其他的 Segment 操作，效率大大提升！

上面介紹完了對象屬性，我們繼續來看看 ConcurrentHashMap 的構造方法，源碼如下：


this調用對應的構造方法，源碼如下：


從源碼上可以看出，ConcurrentHashMap 初始化方法有三個參數，initialCapacity（初始化容量）為 16、loadFactor（負載因子）為 0.75、concurrentLevel（並發等級）為 16，如果不指定則會使用默認值。

其中，值得注意的是 concurrentLevel 這個參數，雖然 Segment 數組大小 ssize 是由 concurrentLevel 來決定的，但是卻不一定等於 concurrentLevel，ssize 通過位移動運算，一定是大於或者等於 concurrentLevel 的最小的 2 的次冪！

通過計算可以看出，按默認的 initialCapacity 初始容量為 16，concurrentLevel 並發等級為 16，理論上就允許 16 個線程並發執行，並且每一個線程獨佔一把鎖訪問 Segment，不影響其它的 Segment 操作！

從之前的文章中，我們了解到 HashMap 在多線程環境下操作可能會導致程序死循環，仔細想想你會發現，造成這個問題無非是 put 和擴容階段發生的！

那麼這樣我們就可以從 put 方法下手了，來看看 ConcurrentHashMap 是怎麼操作的？

3.1、put 操作
ConcurrentHashMap 的 put 方法，源碼如下：


從源碼可以看出，這部分的 put 操作主要分兩步：

定位 Segment 並確保定位的 Segment 已初始化；

調用 Segment 的 put 方法；

真正插入元素的 put 方法，源碼如下：



從源碼可以看出，真正的 put 操作主要分以下幾步：

第一步，嘗試獲取對象鎖，如果獲取到返回 true，否則執行scanAndLockForPut方法，這個方法也是嘗試獲取對象鎖；

第二步，獲取到鎖之後，類似 hashMap 的 put 方法，通過 key 計算所在 HashEntry 數組的下標；

第三步，獲取到數組下標之後遍歷鏈表內容，通過 key 和 hash 值判斷是否 key 已存在，如果已經存在，通過標識符判斷是否覆蓋，默認覆蓋；

第四步，如果不存在，採用頭插法插入到 HashEntry 對象中；

第五步，最後操作完整之後，釋放對象鎖；

我們再來看看，上面提到的scanAndLockForPut這個方法，源碼如下：


scanAndLockForPut這個方法，操作也是分以下幾步：

當前線程嘗試去獲得鎖，查找 key 是否已經存在，如果不存在，就創建一個 HashEntry 對象；

如果重試次數大於最大次數，就調用lock()方法獲取對象鎖，如果依然沒有獲取到，當前線程就阻塞，直到獲取之後退出循環；

在這個過程中，key 可能被別的線程給插入，所以在第 5 步中，如果 HashEntry 存儲內容發生變化，重置重試次數；

通過scanAndLockForPut()方法，當前線程就可以在即使獲取不到segment鎖的情況下，完成需要添加節點的實例化工作，當獲取鎖後，就可以直接將該節點插入鏈表即可。

這個方法還實現了類似於自旋鎖的功能，循環式的判斷對象鎖是否能夠被成功獲取，直到獲取到鎖才會退出循環，防止執行 put 操作的線程頻繁阻塞，這些優化都提升了 put 操作的性能。

3.2、get 操作
get 方法就比較簡單了，因為不涉及增、刪、改操作，所以不存在並發故障問題，源碼如下：



由於 HashEntry 涉及到的共享變數都使用 volatile 修飾，volatile 可以保證內存可見性，所以不會讀取到過期數據。

3.3、remove 操作
remove 操作和 put 方法差不多，都需要獲取對象鎖才能操作，通過 key 找到元素所在的 Segment 對象然後移除，源碼如下：


與 get 方法類似，先獲取 Segment 數組所在的 Segment 對象，然後通過 Segment 對象去移除元素，源碼如下：


先獲取對象鎖，如果獲取到之後執行移除操作，之後的操作類似 hashMap 的移除方法，步驟如下：

先獲取對象鎖；

計算 key 的 hash 值在 HashEntry[]中的角標；

根據 index 角標獲取 HashEntry 對象；

循環遍歷 HashEntry 對象，HashEntry 為單向鏈表結構；

通過 key 和 hash 判斷 key 是否存在，如果存在，就移除元素，並將需要移除的元素節點的下一個，向上移；

最後就是釋放對象鎖，以便其他線程使用；

四、JDK1.8 中的 ConcurrentHashMap
雖然 JDK1.7 中的 ConcurrentHashMap 解決了 HashMap 並發的安全性，但是當沖突的鏈表過長時，在查詢遍歷的時候依然很慢！

在 JDK1.8 中，HashMap 引入了紅黑二叉樹設計，當沖突的鏈表長度大於 8 時，會將鏈表轉化成紅黑二叉樹結構，紅黑二叉樹又被稱為平衡二叉樹，在查詢效率方面，又大大的提高了不少。


因為 HashMap 並不支持在多線程環境下使用， JDK1.8 中的 ConcurrentHashMap 和往期 JDK 中的 ConcurrentHashMa 一樣支持並發操作，整體結構和 JDK1.8 中的 HashMap 類似，相比 JDK1.7 中的 ConcurrentHashMap， 它拋棄了原有的 Segment 分段鎖實現，採用了 CAS + synchronized 來保證並發的安全性。

JDK1.8 中的 ConcurrentHashMap 對節點Node類中的共享變數，和 JDK1.7 一樣，使用volatile關鍵字，保證多線程操作時，變數的可見行！


其他的細節，與 JDK1.8 中的 HashMap 類似，我們來具體看看 put 方法！

4.1、put 操作
打開 JDK1.8 中的 ConcurrentHashMap 中的 put 方法，源碼如下：



當進行 put 操作時，流程大概可以分如下幾個步驟：

首先會判斷 key、value 是否為空，如果為空就拋異常！

接著會判斷容器數組是否為空，如果為空就初始化數組；

進一步判斷，要插入的元素f，在當前數組下標是否第一次插入，如果是就通過 CAS 方式插入；

在接著判斷f.hash == -1是否成立，如果成立，說明當前f是ForwardingNode節點，表示有其它線程正在擴容，則一起進行擴容操作；

其他的情況，就是把新的Node節點按鏈表或紅黑樹的方式插入到合適的位置；

節點插入完成之後，接著判斷鏈表長度是否超過8，如果超過8個，就將鏈表轉化為紅黑樹結構；

最後，插入完成之後，進行擴容判斷；

put 操作大致的流程，就是這樣的，可以看的出，復雜程度比 JDK1.7 上了一個台階。

4.1.1、initTable 初始化數組
我們再來看看源碼中的第 3 步 initTable()方法，如果數組為空就初始化數組，源碼如下：


sizeCtl 是一個對象屬性，使用了 volatile 關鍵字修飾保證並發的可見性，默認為 0，當第一次執行 put 操作時，通過Unsafe.compareAndSwapInt()方法，俗稱CAS，將 sizeCtl修改為 -1，有且只有一個線程能夠修改成功，接著執行 table 初始化任務。

如果別的線程發現sizeCtl<0，意味著有另外的線程執行 CAS 操作成功，當前線程通過執行Thread.yield()讓出 CPU 時間片等待 table 初始化完成。

4.1.2、helpTransfer 幫組擴容
我們繼續來看看 put 方法中第 5 步helpTransfer()方法，如果f.hash == -1成立，說明當前f是ForwardingNode節點，意味有其它線程正在擴容，則一起進行擴容操作，源碼如下：



這個過程，操作步驟如下：

第 1 步，對 table、node 節點、node 節點的 nextTable，進行數據校驗；

第 2 步，根據數組的 length 得到一個標識符號；

第 3 步，進一步校驗 nextTab、tab、sizeCtl 值，如果 nextTab 沒有被並發修改並且 tab 也沒有被並發修改，同時 sizeCtl < 0，說明還在擴容；

第 4 步，對 sizeCtl 參數值進行分析判斷，如果不滿足任何一個判斷，將sizeCtl + 1, 增加了一個線程幫助其擴容;

4.1.3、addCount 擴容判斷
我們再來看看源碼中的第 9 步 addCount()方法，插入完成之後，擴容判斷，源碼如下：



這個過程，操作步驟如下：

第 1 步，利用 CAS 將方法更新 baseCount 的值

第 2 步，檢查是否需要擴容，默認 check = 1，需要檢查；

第 3 步，如果滿足擴容條件，判斷當前是否正在擴容，如果是正在擴容就一起擴容；

第 4 步，如果不在擴容，將 sizeCtl 更新為負數，並進行擴容處理；

put 的流程基本分析完了，可以從中發現，裡面大量的使用了CAS方法，CAS 表示比較與替換，裡面有 3 個參數，分別是目標內存地址、舊值、新值，每次判斷的時候，會將舊值與目標內存地址中的值進行比較，如果相等，就將新值更新到內存地址里，如果不相等，就繼續循環，直到操作成功為止！

雖然使用的了CAS這種樂觀鎖方法，但是裡面的細節設計的很復雜，閱讀比較費神，有興趣的朋友們可以自己研究一下。

4.2、get 操作
get 方法操作就比較簡單了，因為不涉及並發操作，直接查詢就可以了，源碼如下：


從源碼中可以看出，步驟如下：

第 1 步，判斷數組是否為空，通過 key 定位到數組下標是否為空；

第 2 步，判斷 node 節點第一個元素是不是要找到，如果是直接返回；

第 3 步，如果是紅黑樹結構，就從紅黑樹裡面查詢；

第 4 步，如果是鏈表結構，循環遍歷判斷；

4.3、reomve 操作
reomve 方法操作和 put 類似，只是方向是反的，源碼如下：


replaceNode 方法，源碼如下：



從源碼中可以看出，步驟如下：

第 1 步，循環遍歷數組，接著校驗參數；

第 2 步，判斷是否有別的線程正在擴容，如果是一起擴容；

第 3 步，用 synchronized 同步鎖，保證並發時元素移除安全；

第 4 步，因為 check= -1，所以不會進行擴容操作，利用 CAS 操作修改 baseCount 值；

五、總結
雖然 HashMap 在多線程環境下操作不安全，但是在 java.util.concurrent 包下，java 為我們提供了 ConcurrentHashMap 類，保證在多線程下 HashMap 操作安全！

在 JDK1.7 中，ConcurrentHashMap 採用了分段鎖策略，將一個 HashMap 切割成 Segment 數組，其中 Segment 可以看成一個 HashMap， 不同點是 Segment 繼承自 ReentrantLock，在操作的時候給 Segment 賦予了一個對象鎖，從而保證多線程環境下並發操作安全。

但是 JDK1.7 中，HashMap 容易因為沖突鏈表過長，造成查詢效率低，所以在 JDK1.8 中，HashMap 引入了紅黑樹特性，當沖突鏈表長度大於 8 時，會將鏈表轉化成紅黑二叉樹結構。

在 JDK1.8 中，與此對應的 ConcurrentHashMap 也是採用了與 HashMap 類似的存儲結構，但是 JDK1.8 中 ConcurrentHashMap 並沒有採用分段鎖的策略，而是在元素的節點上採用 CAS + synchronized 操作來保證並發的安全性，源碼的實現比 JDK1.7 要復雜的多。

㈤ hashmap和concurrenthashmap的區別，hashmap的底層源碼

你好。 有並發訪問的時候用ConcurrentHashMap，效率比用鎖的HashMap好 功能上可以，但是畢竟ConcurrentHashMap這種數據結構要復雜些，如果能保證只在單一線程下讀寫，不會發生並發的讀寫，那麼就可以試用HashMap。ConcurrentHashMap讀不加鎖，寫...

㈥ HashMap底層實現原理剖析

Hashmap是一種非常常用的、應用廣泛的數據類型，最近研究到相關的內容，就正好復習一下。網上關於hashmap的文章很多，但到底是自己學習的總結，就發出來跟大家一起分享，一起討論。

1.HashMap的數據結構：在java 中 數據結構，最基本 也就兩種 一種數組 一種模擬指針。所有的數據結構都可以用這兩個基本結構來構造的，hashmap也不例外。Hashmap實際上是一個數組和鏈表的結合體。數組的默認長度為16，

2.hashMap源碼解析

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始化容量大小 

static final int MAXIMUM_CAPACITY = 1 << 30; ///容器最大值

static final float DEFAULT_LOAD_FACTOR = 0.75f; //載入影子

static final Entry[] EMPTY_TABLE = {}; //null 的hashMap

transient Entry[] table = (Entry[]) EMPTY_TABLE;///動態擴大容器時使用的一個hashMap

transient int size;//當前數據量

int threshold;//擴大容器時的大小 為 capacity * load factor

final float loadFactor;//使用率閥值，默認為：DEFAULT_LOAD_FACTOR

存取元素 ：調用put方法

public V put(K key, V value) { 

//判斷當前table 為Null 第一次Put 

 if (table == EMPTY_TABLE) {

     inflateTable(threshold);  //初始化容器的大小

 }

 if (key == null) 

 return putForNullKey(value); //判斷當前key 為null 將Null key添加到數組的第一個位置

 int hash = hash(key); //將當前key進行hash 詳情見下方

 int i = indexFor(hash, table.length); //調用完hash演算法後，詳情見下方

 for (Entry e = table[i]; e != null; e = e.next) { //循環判斷當前數組下標為Entry的實體 將當前key相同的替換為最新的值

            Object k;

            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

                V oldValue = e.value;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

            }

        }

        modCount++;

        addEntry(hash, key, value, i); //如果key都不同 則添加Entry.詳情見下方

        return null;

    }

hashMap的hash演算法剖析

final int hash(Object k) {

        int h = hashSeed;

        if (0 != h && k instanceof String) {  //判斷當前k是否為string 和

            return sun.misc.Hashing.stringHash32((String) k); //使用stringHash32演算法得出key   的hash值

        }

        h ^= k.hashCode(); //調用key的hashCode 得出值 後使用"或"運算符 

        h ^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^ (h >>> 4);

前面說過HashMap的數據結構是數組和鏈表的結合，所以我們當然希望這個HashMap裡面的 元素位置盡量的分布均勻些，盡量使得每個位置上的元素數量只有一個，那麼當我們用hash演算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，而不用再去遍歷鏈表，這樣就大大優化了查詢的效率。

一個十進制數32768(二進制1000 0000 0000 0000)，經過上述公式運算之後的結果是35080(二進制1000 1001 0000 1000)。看出來了嗎？或許這樣還看不出什麼，再舉個數字61440(二進制1111 0000 0000 0000)，運算結果是65263(二進制1111 1110 1110 1111)，現在應該很明顯了，它的目的是讓「1」變的均勻一點，散列的本意就是要盡量均勻分布。使用上述演算法後 "1"就變得很均勻了。

我們用table[index]表示已經找到的元素需要存儲的位置。先判斷該位置上有沒有元素（這個元素是HashMap內部定義的一個類Entity， 基本結構它包含三個類，key，value和指向下一個Entity的next）,沒有的話就創建一個Entity對象，在 table[index]位置上插入，這樣插入結束；如果有的話，通過鏈表的遍歷方式去逐個遍歷，看看有沒有已經存在的key，有的話用新的value替 換老的value；如果沒有，則在table[index]插入該Entity，把原來在table[index]位置上的Entity賦值給新的 Entity的next，這樣插入結束

    }

indexFor 返回當前數組下標 ，

static int indexFor(int h, int length) {

        return h & (length-1);

    }

那麼得到key 之後的hash如何得到數組下標呢 ？把h與HashMap的承載量（HashMap的默認承載量length是16，可以自動變長。在構造HashMap的時候也可以指定一個長 度。這個承載量就是上圖所描述的數組的長度。）進行邏輯與運算，即 h & (length-1)，這樣得到的結果就是一個比length小的正數，我們把這個值叫做index。其實這個index就是索引將要插入的值在數組中的 位置。第2步那個演算法的意義就是希望能夠得出均勻的index，這是HashTable的改進，HashTable中的演算法只是把key的 hashcode與length相除取余，即hash % length，這樣有可能會造成index分布不均勻。

首先來解釋一下為什麼數組大小為2的冪時hashmap訪問的性能最高？

看下圖，左邊兩組是數組長度為16（2的4次方），右邊兩組是數組長度為15。兩組的hashcode均為8和9，但是很明顯，當它們和1110「與」的時候，產生了相同的結果，也就是說它們會定位到數組中的同一個位置上去，這就產生了碰撞，8和9會被放到同一個鏈表上，那麼查詢的時候就需要遍歷這個鏈表，得到8或者9，這樣就降低了查詢的效率。同時，我們也可以發現，當數組長度為15的時候，hashcode的值會與14（1110）進行「與」，那麼最後一位永遠是0，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，數組可以使用的位置比數組長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率！ 

void addEntry(int hash, K key, V value, int bucketIndex) {

  //// 若HashMap的實際大小 不小於 「閾值」，則調整HashMap的大小

        if ((size >= threshold) && (null != table[bucketIndex])) {

            resize(2 * table.length);

            hash = (null != key) ? hash(key) : 0;

          //// 設置「bucketIndex」位置的元素為「新Entry」，// 設置「e」為「新Entry的下一個節點」

            bucketIndex = indexFor(hash, table.length);

        }

        createEntry(hash, key, value, bucketIndex);

    }

//將當前key 和value添加到Entry[]中

void createEntry(int hash, K key, V value, int bucketIndex) { 

        Entry e = table[bucketIndex];  //將第一個就得table 復制個新的entry 

        table[bucketIndex] = new Entry<>(hash, key, value, e); //將當前新的Entry 復制個table[bucketIndex]  舊的table[bucketIndex] 和新的table[buckIndex]之間用next關聯。第一個鍵值對A進來，通過計算其key的hash得到的index=0，記做:table[0] = A。一會後又進來一個鍵值對B，通過計算其index也等於0，現在怎麼辦？HashMap會這樣做: B.next = A ,table[0] = B,如果又進來C,index也等於0,那麼 C.next = B ,table[0] = C；這樣我們發現index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性鏈接在一起

        size++; //容量加1

    }

以上就是HashMap添加元素時的過程解析

那麼如何get元素呢？

public V get(Object key) {

 if (key == null) return getForNullKey(); //當前key是否為null 如果為null值返回table[0]這個value

    Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();

    }

final EntrygetEntry(Object key) {

 if (size == 0) { return null; }  //判斷容量是否大於0 

 int hash = (key == null) ? 0 : hash(key); //對當前key 進行hash hash後得到一個值

 for (Entry e = table[indexFor(hash, table.length)]; //獲取當前Entry 循環遍歷

            e != null;

            e = e.next) {

            Object k;

            if (e.hash == hash &&

                ((k = e.key) == key || (key != null && key.equals(k))))

                return e;

        }

        return null;

    }

擴展問題:

1.當前我們的hashMap中越來越大的之後，"碰撞"就越來越明顯，那麼如何解決碰撞呢？擴容！

當hashmap中的元素個數超過數組大小capti*loadFactor時，就會進行數組擴容，loadFactor的默認值為0.75，也就是說，默認情況下，數組大小為16，那麼當hashmap中元素個數超過16*0.75=12的時候，就把數組的大小擴展為2*16=32，即擴大一倍，然後重新計算每個元素在數組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經預知hashmap中元素的個數，那麼預設元素的個數能夠有效的提高hashmap的性能。比如說，我們有1000個元素new HashMap(1000), 但是理論上來講new HashMap(1024)更合適，不過上面annegu已經說過，即使是1000，hashmap也自動會將其設置為1024。 但是new HashMap(1024)還不是更合適的，因為0.75*1000 < 1000, 也就是說為了讓0.75 * size > 1000, 我們必須這樣new HashMap(2048)才最合適，既考慮了&的問題，也避免了resize的問題

HashMap的兩種遍歷方式

第一種

Map map = newHashMap();

Iterator iter = map.entrySet().iterator();

while(iter.hasNext()) {

Map.Entry entry = (Map.Entry) iter.next();

Object key = entry.getKey();

Object val = entry.getValue();

}

效率高,以後一定要使用此種方式！

第二種

Map map = newHashMap();

Iterator iter = map.keySet().iterator();

while(iter.hasNext()) {

Object key = iter.next();

Object val = map.get(key);

}

效率低,以後盡量少使用！

歸納

簡單地說，HashMap 在底層將 key-value 當成一個整體進行處理，這個整體就是一個 Entry 對象。HashMap 底層採用一個 Entry[] 數組來保存所有的 key-value 對，當需要存儲一個 Entry 對象時，會根據hash演算法來決定其在數組中的存儲位置，在根據equals方法決定其在該數組位置上的鏈表中的存儲位置；當需要取出一個Entry時，

也會根據hash演算法找到其在數組中的存儲位置，再根據equals方法從該位置上的鏈表中取出該Entry。

㈦ 2021-01-18：java中，HashMap的創建流程是什麼

jdk1.7創建流程：
三種構造器。
1.初始容量不能為負數，默認16。
2.初始容量大於最大容量時，初始容量等於最大容量。
3.負載因子必須大於0，默認0.75。
4.根據初始容量算出容量，容量是2的n次冪。
5.設置負載因子loadFactor 。
6.設置容量極限threshold。
7.設置table數組。
8.調用init()空方法。
參數為集合的構造器。
1.調用有兩個參數的構造器。
2.inflateTable方法。初始化table數組。
3.putAllForCreate方法。遍歷參數，放入當前map。
jdk1.8創建流程：
兩種構造器。
1.初始容量不能為負數，默認16。
2.初始容量大於最大容量時，初始容量等於最大容量。
3.負載因子必須大於0，默認0.75。
4.設置負載因子loadFactor 。
5.設置容量極限threshold，調用tableSizeFor方法，大於initialCapacity的最小的二次冪數值 。。
無參構造器。
1.只設置了負載因子，其他什麼都沒做。
參數為集合的構造器。
1.設置負載因子。
2.putMapEntries方法。遍歷參數，放入當前map。
***
[HashMap源碼分析（jdk7）](https://www.cnblogs.com/fsmly/p/11278561.html)
[JDK1.8中的HashMap實現](https://www.cnblogs.com/doufuyu/p/10874689.html)
[評論](https://user.qzone.qq.com/3182319461/blog/1610924590)

㈧ java查看hashmap的源碼發現並沒有向entrySet中裝入元素，而去可以如下遍歷。

幫助文檔上說：返回此映射所包含的映射關系的
collection
視圖。在返回的集合中，每個元素都是一個
Map.Entry。
entrySet僅僅是一個視圖而已，沒有具體的數據，其實還是從HashMap中獲取數據的。具體可以看entry和entrySet的源代碼就知道數據其實還是來自於table。

㈨ 同步的數據結構，例如concurrenthashmap的源碼理解以及內部實現原理，為什麼他是同

nized是針對整張Hash表的，即每次鎖住整張表讓線程獨占，ConcurrentHashMap允許多個修改操作並發進行，其關鍵在於使用了鎖分離技術。它使用了多個鎖來控制對hash表的不同部分進行的修改。ConcurrentHashMap內部使用段(Segment)來表示這些不同的部分，每個段其實就是一個小的hash table，它們有自己的鎖。只要多個修改操作發生在不同的段上，它們就可以並發進行。
有些方法需要跨段，比如size()和containsValue()，它們可能需要鎖定整個表而而不僅僅是某個段，這需要按順序鎖定所有段，操作完畢後，又按順序釋放所有段的鎖。這里「按順序」是很重要的，否則極有可能出現死鎖，在ConcurrentHashMap內部，段數組