前言

HashMap是Java程序員使用頻率最高的用于映射(鍵值對)處理的數(shù)據(jù)類型。隨著JDK版本的更新管搪，JDK1.8對HashMap底層的實現(xiàn)進行了優(yōu)化，例如引入紅黑樹的數(shù)據(jù)結(jié)構(gòu)和擴容的優(yōu)化等铡买。本文結(jié)合JDK1.7和JDK1.8的區(qū)別更鲁，來談?wù)?code>HashMap的結(jié)構(gòu)實現(xiàn)和功能原理。

如無特別說明奇钞，本文是基于JDK8澡为。

簡介

Java為數(shù)據(jù)結(jié)構(gòu)中的映射定義了一個接口java.util.Map，此接口主要有四個常用的實現(xiàn)類蛇券，分別是HashMap缀壤、Hashtable樊拓、LinkedHashMap和TreeMap纠亚，類繼承關(guān)系如下圖所示：

下面針對各個實現(xiàn)類的特點做一些說明：

• HashMap：它根據(jù)key的hashCode來存儲數(shù)據(jù)，大多數(shù)情況下可以直接定位到它的值筋夏，因而具有很快的訪問速度蒂胞。HashMap最多只允許一條記錄的key為null，允許多條記錄的value為null条篷。HashMap非線程安全骗随，即任一時刻可以有多個線程同時寫HashMap，但可能會導(dǎo)致數(shù)據(jù)的不一致赴叹。如果需要滿足線程安全鸿染，可以用 Collections的synchronizedMap(Map<K,V> m)方法使HashMap具有線程安全的能力，但多線程環(huán)境下更推薦使用ConcurrentHashMap乞巧。

• Hashtable：Hashtable是遺留類涨椒，很多映射的常用功能與HashMap類似，不同的是它承自Dictionary類绽媒，并且是線程安全的蚕冬，任一時間只有一個線程能寫Hashtable，并發(fā)性不如ConcurrentHashMap是辕，因為ConcurrentHashMap引入了分段鎖（JDK1.7中采用分段鎖技術(shù)囤热、JDK1.8中采用的是CAS）。Hashtable不建議再在新代碼中使用获三，不需要線程安全的場合可以用HashMap替換旁蔼，需要線程安全的場合可以用ConcurrentHashMap替換锨苏。

• LinkedHashMap：LinkedHashMap 繼承自 HashMap，在 HashMap 基礎(chǔ)上牌芋，通過維護一條雙向鏈表蚓炬，解決了HashMap不能隨時保持遍歷順序和插入順序一致的問題。詳細可查看：LinkedHashMap 源碼詳細分析（JDK1.8）

• TreeMap：TreeMap實現(xiàn)SortedMap接口躺屁，能夠把它保存的記錄根據(jù)key排序肯夏，默認是按鍵kwy的值升序排序，也可以指定排序的比較器犀暑，當用Iterator遍歷TreeMap時驯击，得到的記錄是排過序的。如果使用排序的映射耐亏，建議使用TreeMap徊都。在使用TreeMap時，key必須實現(xiàn)Comparable接口或者在構(gòu)造TreeMap傳入自定義的Comparator广辰，否則會在運行時拋出java.lang.ClassCastException類型的異常暇矫。

對于上述四種Map類型的類，要求映射中的key是不可變對象择吊。不可變對象是該對象在創(chuàng)建后它的哈希值不會被改變李根。如果對象的哈希值發(fā)生變化，Map對象很可能就定位不到映射的位置了几睛。

通過上面的比較房轿，我們知道了HashMap是Java的Map家族中一個普通成員，鑒于它可以滿足大多數(shù)場景的使用條件所森，所以是使用頻度最高的一個囱持。下文我們主要結(jié)合源碼，從存儲結(jié)構(gòu)焕济、常用方法分析纷妆、擴容以及安全性等方面深入講解HashMap的工作原理。

內(nèi)部實現(xiàn)

要搞清楚HashMap晴弃，首先需要知道HashMap是什么掩幢，即它的存儲結(jié)構(gòu)；其次弄明白HashMap能干什么肝匆，即它的功能實現(xiàn)粒蜈。下面我們針對這兩個方面詳細展開講解。

一旗国、存儲結(jié)構(gòu)-字段

HashMap采用的數(shù)據(jù)機構(gòu)是數(shù)組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）實現(xiàn)的枯怖，如下如所示。

這里需要講明白兩個問題：數(shù)據(jù)底層具體存儲的是什么能曾？這樣的存儲方式有什么優(yōu)點呢度硝？

(1) 從源碼可知肿轨，HashMap類中有一個非常重要的字段，就是 Node[] table蕊程，即哈希桶數(shù)組椒袍，明顯它是一個Node的數(shù)組。我們來看Node（JDK1.8）是何物藻茂。

(2)HashMap就是使用哈希表來存儲的。哈希表為解決沖突掀序，可以采用 開放地址法 和 鏈地址法 等來解決問題帆焕，Java中HashMap采用了鏈地址法。鏈地址法不恭，簡單來說叶雹，就是數(shù)組+鏈表的結(jié)合。在每個數(shù)組元素上都一個鏈表結(jié)構(gòu)换吧，當數(shù)據(jù)被Hash后折晦，得到數(shù)組下標，把數(shù)據(jù)放在對應(yīng)下標元素的鏈表上式散。例如程序執(zhí)行下面代碼：

map.put("河南大學(xué)","河南·開封");

系統(tǒng)將調(diào)用"河南大學(xué)"這個key的hashCode()方法得到其hashCode值（該方法適用于每個Java對象）筋遭，然后再通過Hash算法的后兩步運算（高位運算和取模運算打颤，下文有介紹）來定位該鍵值對的存儲位置暴拄，有時兩個key會定位到相同的位置，表示發(fā)生了Hash碰撞编饺。當然Hash算法計算結(jié)果越分散均勻乖篷，Hash碰撞的概率就越小，map的存取效率就會越高透且。

如果哈希桶數(shù)組很大撕蔼，即使較差的Hash算法也會比較分散，如果哈希桶數(shù)組數(shù)組很小秽誊，即使好的Hash算法也會出現(xiàn)較多碰撞鲸沮，所以就需要在空間成本和時間成本之間權(quán)衡，其實就是在根據(jù)實際情況確定哈希桶數(shù)組的大小锅论，并在此基礎(chǔ)上設(shè)計好的hash算法減少Hash碰撞讼溺。那么通過什么方式來控制map使得Hash碰撞的概率又小，哈希桶數(shù)組（Node[] table）占用空間又少呢最易？答案就是好的Hash算法和擴容機制怒坯。

在理解Hash和擴容流程之前炫狱，我們得先了解下HashMap的幾個字段。從HashMap的默認構(gòu)造函數(shù)源碼可知剔猿，構(gòu)造函數(shù)就是對下面幾個字段進行初始化视译，源碼如下：

     int threshold;           
     final float loadFactor;   
     int modCount;  
     int size;

首先，Node[] table的初始化長度length(默認值是16)归敬，loadFactor為負載因子(默認值是0.75)酷含，threshold是HashMap所能容納的最大數(shù)據(jù)量的Node(鍵值對)個數(shù)。threshold = length * loadFactor汪茧，比如length=16第美、loadFactor=0.75f，那么threshold=16 * 0.75=12陆爽。也就是說什往，在數(shù)組定義好長度之后，負載因子越大慌闭，所能容納的鍵值對個數(shù)越多别威。

結(jié)合負載因子的定義公式可知，threshold就是在此loadFactor和length(數(shù)組長度)對應(yīng)下允許的最大元素數(shù)目驴剔，超過這個數(shù)目就重新resize(擴容)省古，擴容后的HashMap容量是之前容量的兩倍。默認的負載因子0.75是對空間和時間效率的一個平衡選擇丧失，建議大家不要修改豺妓，除非在時間和空間比較特殊的情況下，如果內(nèi)存空間很多而又對時間效率要求很高布讹，可以降低負載因子loadFactor的值琳拭；相反，如果內(nèi)存空間緊張而對時間效率要求不高描验，可以增加負載因子loadFactor的值白嘁，這個值可以大于1咬扇。

size這個字段其實很好理解衬吆，就是HashMap中實際存在的鍵值對數(shù)量饭豹。注意和table的長度length踱稍、容納最大鍵值對數(shù)量threshold的區(qū)別配乱。而modCount字段主要用來記錄HashMap內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)阳啥，主要用于迭代的快速失敗铐姚。強調(diào)一點证九，內(nèi)部結(jié)構(gòu)發(fā)生變化指的是結(jié)構(gòu)發(fā)生變化彭谁，例如put新鍵值對吸奴，但是某個key對應(yīng)的value值被覆蓋不屬于結(jié)構(gòu)變化。

在HashMap中，哈希桶數(shù)組table的長度length大小必須為2的n次方(一定是合數(shù))奄抽，這是一種非常規(guī)范的設(shè)計蔼两，常規(guī)的設(shè)計是把桶的大小設(shè)計為素數(shù)。相對來說素數(shù)導(dǎo)致沖突的概率要小于合數(shù)逞度。HashMap采用這種非常規(guī)設(shè)計额划，主要是為了在取模和擴容時做優(yōu)化，同時為了減少沖突档泽，HashMap定位哈希桶索引位置時俊戳，也加入了高位參與運算的過程。

這里存在一個問題馆匿，即使負載因子和Hash算法設(shè)計的再合理抑胎，也免不了會出現(xiàn)拉鏈過長的情況，一旦出現(xiàn)拉鏈過長渐北，則會嚴重影響HashMap的性能阿逃。于是，在JDK1.8版本中赃蛛，對數(shù)據(jù)結(jié)構(gòu)做了進一步的優(yōu)化恃锉，引入了紅黑樹。而當鏈表長度太長（默認超過8）時呕臂，鏈表就轉(zhuǎn)換為紅黑樹破托；當紅黑樹節(jié)點個數(shù)太少（默認少于6）時，紅黑樹就退化為鏈表歧蒋。

二土砂、功能實現(xiàn)-方法

HashMap的內(nèi)部功能實現(xiàn)很多，本文主要從根據(jù)key獲取哈希桶數(shù)組索引位置谜洽、put方法的詳細執(zhí)行萝映、擴容過程三個具有代表性的點深入展開講解。

1. 確定哈希桶數(shù)組索引位置

不管增加褥琐、刪除锌俱、查找鍵值對晤郑，定位到哈希桶數(shù)組的位置都是很關(guān)鍵的第一步敌呈。前面說過HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合，所以我們當然希望這個HashMap里面的元素位置盡量分布均勻些造寝，盡量使得每個位置上的元素數(shù)量只有一個磕洪，那么當我們用hash算法求得這個位置的時候，馬上就可以知道對應(yīng)位置的元素就是我們要的诫龙，不用遍歷鏈表析显，大大優(yōu)化了查詢的效率。HashMap定位數(shù)組索引位置签赃，直接決定了hash方法的離散性能谷异。先看看源碼的實現(xiàn)(方法一+方法二):

這里的Hash算法本質(zhì)上就是三步：取key的hashCode值分尸、高位運算、取模運算歹嘹。

對于任意給定的對象箩绍，只要它的hashCode()返回值相同，那么程序調(diào)用方法一所計算得到的Hash碼值總是相同的尺上。我們首先想到的就是把hash值對數(shù)組長度取模運算材蛛，這樣一來，元素的分布相對來說是比較均勻的怎抛。但是卑吭，模運算的消耗還是比較大的，在HashMap中是這樣做的：調(diào)用方法二來計算該對象應(yīng)該保存在table數(shù)組的哪個索引處马绝。

這個方法非常巧妙豆赏，它通過h & (table.length -1)來得到該對象的保存位，而HashMap底層數(shù)組的長度總是2的n次方富稻，這是HashMap在速度上的優(yōu)化河绽。當length總是2的n次方時，h& (length-1)運算等價于對length取模唉窃，也就是h%length耙饰，但是&比%具有更高的效率。

在JDK1.8的實現(xiàn)中纹份，優(yōu)化了高位運算的算法苟跪，通過hashCode()的高16位異或低16位(h = k.hashCode()) ^ (h >>> 16)實現(xiàn)的，主要是從速度蔓涧、功效件已、質(zhì)量來考慮的，這么做可以在數(shù)組table的length比較小的時候元暴，也能保證考慮到高低位都參與到Hash的計算中篷扩，同時不會有太大的開銷。

下面舉例說明下茉盏，n為table的長度鉴未。

2. 分析HashMap的put方法

HashMap的put方法執(zhí)行過程可以通過下圖來理解，自己有興趣可以去對比源碼更清楚地研究學(xué)習(xí)鸠姨。

②.根據(jù)鍵值key計算hash值得到插入的數(shù)組索引i讶迁，如果table[i]==null连茧，直接新建節(jié)點添加，轉(zhuǎn)向⑥，如果table[i]不為空啸驯，轉(zhuǎn)向③客扎；

③.判斷table[i]的首個元素是否和key一樣，如果相同直接覆蓋value罚斗，否則轉(zhuǎn)向④虐唠，這里的相同指的是hashCode以及equals；

④.判斷table[i] 是否為treeNode惰聂，即table[i] 是否是紅黑樹疆偿，如果是紅黑樹，則直接在樹中插入鍵值對搓幌，否則轉(zhuǎn)向⑤杆故；

⑤.遍歷table[i]，判斷鏈表長度是否大于8溉愁，大于8的話把鏈表轉(zhuǎn)換為紅黑樹处铛，在紅黑樹中執(zhí)行插入操作，否則進行鏈表的插入操作拐揭；遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可撤蟆；

⑥.插入成功后，判斷實際存在的鍵值對數(shù)量size是否超多了最大容量threshold堂污，如果超過家肯，進行擴容。

JDK1.8HashMap的put方法源碼如下:

3. 擴容機制

擴容(resize)就是重新計算容量盟猖，向HashMap對象里不停的添加元素讨衣，而HashMap對象內(nèi)部的數(shù)組無法裝載更多的元素時，對象就需要擴大數(shù)組的長度式镐，以便能裝入更多的元素反镇。當然Java里的數(shù)組是無法自動擴容的，方法是使用一個新的數(shù)組代替已有的容量小的數(shù)組娘汞，就像我們用一個小桶裝水歹茶，如果想裝更多的水，就得換大水桶你弦。

我們分析下resize的源碼惊豺，鑒于JDK1.8融入了紅黑樹，較復(fù)雜鳖目，為了便于理解我們?nèi)匀皇褂肑DK1.7的代碼扮叨，好理解一些，本質(zhì)上區(qū)別不大领迈，具體區(qū)別后文再說。

這里就是使用一個容量更大的數(shù)組來代替已有的容量小的數(shù)組（擴容后數(shù)組的大小為擴容前數(shù)組的2倍），transfer()方法將原有Entry數(shù)組的元素拷貝到新的Entry數(shù)組里狸捅。

newTable[i]的引用賦給了e.next衷蜓，也就是使用了單鏈表的頭插入方式，同一位置上新元素總會被放在鏈表的頭部位置尘喝；這樣先放在一個索引上的元素終會被放到Entry鏈的尾部(如果發(fā)生了hash沖突的話）磁浇，這一點和JDK8有區(qū)別（JDK8是尾插法），下文詳解朽褪。在舊數(shù)組中同一條Entry鏈上的元素置吓，通過重新計算索引位置后，有可能被放到了新數(shù)組的不同位置上缔赠。

下面舉個例子說明下擴容過程衍锚。假設(shè)了我們的hash算法就是簡單的用key mod 一下表的大小（也就是數(shù)組的長度）嗤堰。其中的哈希桶數(shù)組table的size=2戴质， 所以key = 3、7踢匣、5告匠，put順序依次為 5、7离唬、3后专。在mod 2以后都沖突在table[1]這里了。這里假設(shè)負載因子 loadFactor=1输莺，即當鍵值對的實際大小size 大于 table的實際大小時進行擴容行贪。接下來的三個步驟是哈希桶數(shù)組 resize成4，然后所有的Node重新rehash的過程模闲。

下面我們講解下JDK1.8做了哪些優(yōu)化建瘫。

經(jīng)過觀測可以發(fā)現(xiàn)，我們使用的是2次冪的擴展(指長度擴為原來2倍)尸折，所以啰脚，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置实夹￠吓ǎ看下圖可以明白這句話的意思，n為table的長度亮航，圖（a）表示擴容前的key1和key2兩種key確定索引位置的示例荸实，圖（b）表示擴容后key1和key2兩種key確定索引位置的示例，其中hash1是key1對應(yīng)的哈希與高位運算結(jié)果缴淋。

元素在重新計算hash之后准给，因為n變?yōu)?倍泄朴，那么n-1的范圍在高位多1bit(紅色)，因此新的index就會發(fā)生這樣的變化：

因此露氮，我們在擴充HashMap的時候祖灰，不需要像JDK1.7的實現(xiàn)那樣重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了畔规，是0的話索引沒變局扶，是1的話索引變成“原索引+oldCap”，可以看看下圖為16擴充為32的resize示意圖：

這個設(shè)計確實非常的巧妙叁扫，既省去了重新計算hash值的時間三妈，而且同時，由于新增的1bit是0還是1可以認為是隨機的莫绣，因此resize的過程畴蒲，均勻的把之前的沖突的節(jié)點分散到新的bucket了。這一塊就是JDK1.8新增的優(yōu)化點兔综。有一點注意區(qū)別饿凛，JDK1.7中rehash的時候，舊鏈表遷移新鏈表的時候软驰，如果在新表的數(shù)組索引位置相同涧窒，則鏈表元素會倒置，但是從上圖可以看出锭亏，JDK1.8不會倒置纠吴。有興趣的同學(xué)可以研究下JDK1.8的resize源碼，寫的很贊慧瘤，如下:

線程安全性

在多線程使用場景中戴已，應(yīng)該盡量避免使用線程不安全的HashMap，而使用線程安全的ConcurrentHashMap锅减。那么為什么說HashMap是線程不安全的糖儡，下面舉例子說明在并發(fā)的多線程使用場景中使用HashMap可能造成死循環(huán)。代碼例子如下(便于理解怔匣，仍然使用JDK1.7的環(huán)境)：

其中握联，map初始化為一個長度為2的數(shù)組，loadFactor=0.75每瞒，threshold=2*0.75=1金闽，也就是說當put第二個key的時候，map就需要進行resize剿骨。

通過設(shè)置斷點讓線程1和線程2同時debug到transfer()方法的首行代芜。注意此時兩個線程已經(jīng)成功添加數(shù)據(jù)。放開thread1的斷點至transfer方法的“Entry next = e.next;” 這一行浓利；然后放開線程2的的斷點挤庇，讓線程2進行resize钞速。結(jié)果如下圖。

注意罚随，Thread1的 e 指向了key(3)玉工，而next指向了key(7)羽资，其在線程二rehash后淘菩，指向了線程二重組后的鏈表。

線程一被調(diào)度回來執(zhí)行屠升，先是執(zhí)行 newTalbe[i] = e潮改， 然后是e = next，導(dǎo)致了e指向了key(7)腹暖，而下一次循環(huán)的next = e.next導(dǎo)致了next指向了key(3)汇在。

e.next = newTable[i] 導(dǎo)致 key(3).next 指向了 key(7)。注意：此時的key(7).next 已經(jīng)指向了key(3)脏答， 環(huán)形鏈表就這樣出現(xiàn)了糕殉。

于是，當我們用線程一調(diào)用map.get(11)時殖告，悲劇就出現(xiàn)了——死循環(huán)阿蝶。

JDK1.8與JDK1.7的性能對比

HashMap中，如果key經(jīng)過hash算法得出的數(shù)組索引位置全部不相同黄绩，即Hash算法非常好羡洁，那樣的話，getKey方法的時間復(fù)雜度就是O(1)爽丹，如果Hash算法技術(shù)的結(jié)果碰撞非常多筑煮，假如Hash算極其差，所有的Hash算法結(jié)果得出的索引位置一樣粤蝎，那樣所有的鍵值對都集中到一個桶中真仲，或者在一個鏈表中，或者在一個紅黑樹中初澎，時間復(fù)雜度分別為O(n)和O(lgn)秸应。

小結(jié)

(1) 擴容是一個特別耗性能的操作，所以當程序員在使用HashMap的時候谤狡，估算map的大小灸眼，初始化的時候給一個大致的數(shù)值，避免map進行頻繁的擴容墓懂。

(2) 負載因子是可以修改的焰宣，也可以大于1，但是建議不要輕易修改捕仔，除非情況非常特殊匕积。

(3) HashMap是線程不安全的盈罐，不要在并發(fā)的環(huán)境中同時操作HashMap，建議使用ConcurrentHashMap闪唆。

(4) JDK1.8引入紅黑樹大程度優(yōu)化了HashMap的性能盅粪。

(5) 還沒升級JDK1.8的，現(xiàn)在開始升級吧悄蕾。HashMap的性能提升僅僅是JDK1.8的冰山一角票顾。

參考文章
Java 8系列之重新認識HashMap

HashMap 源碼詳細分析(JDK1.8)