厲害了！把 HashMap 剖析的只剩渣了！
前言
HashMap是一個(gè)非常重要的集合，日常使用也非常的頻繁，同時(shí)也是面試重點(diǎn)。本文并不打算講解基礎(chǔ)的使用api，而是深入HashMap的底層，講解關(guān)于HashMap的重點(diǎn)知識(shí)。需要讀者對(duì)散列表和HashMap有一定的認(rèn)識(shí)。
HashMap本質(zhì)上是一個(gè)散列表，那么就離不開(kāi)散列表的三大問(wèn)題：散列函數(shù)、哈希沖突、擴(kuò)容方案;同時(shí)作為一個(gè)數(shù)據(jù)結(jié)構(gòu)，必須考慮多線(xiàn)程并發(fā)訪(fǎng)問(wèn)的問(wèn)題，也就是線(xiàn)程安全。這四大重點(diǎn)則為學(xué)習(xí)HashMap的重點(diǎn)，也是HashMap設(shè)計(jì)的重點(diǎn)。
HashMap屬于Map集合體系的一部分，同時(shí)繼承了Serializable接口可以被序列化，繼承了Cloneable接口可以被復(fù)制。他的的繼承結(jié)構(gòu)如下：
img
HashMap并不是全能的，對(duì)于一些特殊的情景下的需求官方拓展了一些其他的類(lèi)來(lái)滿(mǎn)足，如線(xiàn)程安全的ConcurrentHashMap、記錄插入順序的LinkHashMap、給key排序的TreeMap等。
文章內(nèi)容主要講解四大重點(diǎn)：散列函數(shù)、哈希沖突、擴(kuò)容方案、線(xiàn)程安全，再補(bǔ)充關(guān)鍵的源碼分析和相關(guān)的問(wèn)題。
本文所有內(nèi)容如若未特殊說(shuō)明，均為JDK1.8版本。
哈希函數(shù)
哈希函數(shù)的目標(biāo)是計(jì)算key在數(shù)組中的下標(biāo)。判斷一個(gè)哈希函數(shù)的標(biāo)準(zhǔn)是：散列是否均勻、計(jì)算是否簡(jiǎn)單。
HashMap哈希函數(shù)的步驟：
- 對(duì)key對(duì)象的hashcode進(jìn)行擾動(dòng)
- 通過(guò)取模求得數(shù)組下標(biāo)
擾動(dòng)是為了讓hashcode的隨機(jī)性更高，第二步取模就不會(huì)讓所以的key都聚集在一起，提高散列均勻度。擾動(dòng)可以看到hash()方法：
- static final int hash(Object key) {
- int h;
- // 獲取到key的hashcode，在高低位異或運(yùn)算
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
- }
也就是低16位是和高16位進(jìn)行異或，高16位保持不變。一般的數(shù)組長(zhǎng)度都會(huì)比較短，取模運(yùn)算中只有低位參與散列;高位與低位進(jìn)行異或，讓高位也得以參與散列運(yùn)算，使得散列更加均勻。具體運(yùn)算如下圖(圖中為了方便采用8位進(jìn)行演示，32位同理)：
img
對(duì)hashcode擾動(dòng)之后需要對(duì)結(jié)果進(jìn)行取模。HashMap在jdk1.8并不是簡(jiǎn)單使用%進(jìn)行取模，而是采用了另外一種更加高性能的方法。HashMap控制數(shù)組長(zhǎng)度為2的整數(shù)次冪，好處是對(duì)hashcode進(jìn)行求余運(yùn)算和讓hashcode與數(shù)組長(zhǎng)度-1進(jìn)行位與運(yùn)算是相同的效果。如下圖：
img
但位與運(yùn)算的效率卻比求余高得多，從而提升了性能。在擴(kuò)容運(yùn)算中也利用到了此特性，后面會(huì)講。取模運(yùn)算的源碼看到putVal()方法，該方法在put()方法中被調(diào)用：
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- boolean evict) {
- ...
- // 與數(shù)組長(zhǎng)度-1進(jìn)行位與運(yùn)算，得到下標(biāo)
- if ((p = tab[i = (n - 1) & hash]) == null)
- ...
- }
完整的hash計(jì)算過(guò)程可以參考下圖：
img
上面我們提到HashMap的數(shù)組長(zhǎng)度為2的整數(shù)次冪，那么HashMap是如何控制數(shù)組的長(zhǎng)度為2的整數(shù)次冪的?修改數(shù)組長(zhǎng)度有兩種情況：
- 初始化時(shí)指定的長(zhǎng)度
- 擴(kuò)容時(shí)的長(zhǎng)度增量
先看第一種情況。默認(rèn)情況下，如未在HashMap構(gòu)造器中指定長(zhǎng)度，則初始長(zhǎng)度為16。16是一個(gè)較為合適的經(jīng)驗(yàn)值，他是2的整數(shù)次冪，同時(shí)太小會(huì)頻繁觸發(fā)擴(kuò)容、太大會(huì)浪費(fèi)空間。如果指定一個(gè)非2的整數(shù)次冪，會(huì)自動(dòng)轉(zhuǎn)化成大于該指定數(shù)的最小2的整數(shù)次冪。如指定6則轉(zhuǎn)化為8，指定11則轉(zhuǎn)化為16。結(jié)合源碼來(lái)分析，當(dāng)我們初始化指定一個(gè)非2的整數(shù)次冪長(zhǎng)度時(shí)，HashMap會(huì)調(diào)用tableSizeFor()方法：
- public HashMap(int initialCapacity, float loadFactor) {
- ...
- this.loadFactor = loadFactor;
- // 這里調(diào)用了tableSizeFor方法
- this.threshold = tableSizeFor(initialCapacity);
- }
- static final int tableSizeFor(int cap) {
- // 注意這里必須減一
- int n = cap - 1;
- n |= n >>> 1;
- n |= n >>> 2;
- n |= n >>> 4;
- n |= n >>> 8;
- n |= n >>> 16;
- return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
- }
tableSizeFor()方法的看起來(lái)很復(fù)雜，作用是使得最高位1后續(xù)的所有位都變?yōu)?，最后再+1則得到剛好大于initialCapacity的最小2的整數(shù)次冪數(shù)。如下圖(這里使用了8位進(jìn)行模擬，32位也是同理)：
img
那為什么必須要對(duì)cap進(jìn)行-1之后再進(jìn)行運(yùn)算呢?如果指定的數(shù)剛好是2的整數(shù)次冪，如果沒(méi)有-1結(jié)果會(huì)變成比他大兩倍的數(shù)，如下：
- 00100 --高位1之后全變1--> 00111 --加1---> 01000
第二種改變數(shù)組長(zhǎng)度的情況是擴(kuò)容。HashMap每次擴(kuò)容的大小都是原來(lái)的兩倍，控制了數(shù)組大小一定是2的整數(shù)次冪，相關(guān)源碼如下：
- final Node<K,V>[] resize() {
- ...
- if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
- oldCap >= DEFAULT_INITIAL_CAPACITY)
- // 設(shè)置為原來(lái)的兩倍
- newThr = oldThr << 1;
- ...
- }
小結(jié)
- HashMap通過(guò)高16位與低16位進(jìn)行異或運(yùn)算來(lái)讓高位參與散列，提高散列效果;
- HashMap控制數(shù)組的長(zhǎng)度為2的整數(shù)次冪來(lái)簡(jiǎn)化取模運(yùn)算，提高性能;
- HashMap通過(guò)控制初始化的數(shù)組長(zhǎng)度為2的整數(shù)次冪、擴(kuò)容為原來(lái)的2倍來(lái)控制數(shù)組長(zhǎng)度一定為2的整數(shù)次冪。
哈希沖突解決方案
再優(yōu)秀的hash算法永遠(yuǎn)無(wú)法避免出現(xiàn)hash沖突。hash沖突指的是兩個(gè)不同的key經(jīng)過(guò)hash計(jì)算之后得到的數(shù)組下標(biāo)是相同的。解決hash沖突的方式很多，如開(kāi)放定址法、再哈希法、公共溢出表法、鏈地址法。HashMap采用的是鏈地址法，jdk1.8之后還增加了紅黑樹(shù)的優(yōu)化，如下圖：
img
出現(xiàn)沖突后會(huì)在當(dāng)前節(jié)點(diǎn)形成鏈表，而當(dāng)鏈表過(guò)長(zhǎng)之后，會(huì)自動(dòng)轉(zhuǎn)化成紅黑樹(shù)提高查找效率。紅黑樹(shù)是一個(gè)查找效率很高的數(shù)據(jù)結(jié)構(gòu)，時(shí)間復(fù)雜度為O(logN)，但紅黑樹(shù)只有在數(shù)據(jù)量較大時(shí)才能發(fā)揮它的優(yōu)勢(shì)。關(guān)于紅黑樹(shù)的轉(zhuǎn)化，HashMap做了以下限制。
- 當(dāng)鏈表的長(zhǎng)度>=8且數(shù)組長(zhǎng)度>=64時(shí)，會(huì)把鏈表轉(zhuǎn)化成紅黑樹(shù)。
- 當(dāng)鏈表長(zhǎng)度>=8，但數(shù)組長(zhǎng)度<64時(shí)，會(huì)優(yōu)先進(jìn)行擴(kuò)容，而不是轉(zhuǎn)化成紅黑樹(shù)。
- 當(dāng)紅黑樹(shù)節(jié)點(diǎn)數(shù)<=6，自動(dòng)轉(zhuǎn)化成鏈表。
那就有了以下問(wèn)題：
為什么需要數(shù)組長(zhǎng)度到64才會(huì)轉(zhuǎn)化紅黑樹(shù)?
當(dāng)數(shù)組長(zhǎng)度較短時(shí)，如16，鏈表長(zhǎng)度達(dá)到8已經(jīng)是占用了最大限度的50%，意味著負(fù)載已經(jīng)快要達(dá)到上限，此時(shí)如果轉(zhuǎn)化成紅黑樹(shù)，之后的擴(kuò)容又會(huì)再一次把紅黑樹(shù)拆分平均到新的數(shù)組中，這樣非但沒(méi)有帶來(lái)性能的好處，反而會(huì)降低性能。所以在數(shù)組長(zhǎng)度低于64時(shí)，優(yōu)先進(jìn)行擴(kuò)容。
為什么要大于等于8轉(zhuǎn)化為紅黑樹(shù)，而不是7或9?
樹(shù)節(jié)點(diǎn)的比普通節(jié)點(diǎn)更大，在鏈表較短時(shí)紅黑樹(shù)并未能明顯體現(xiàn)性能優(yōu)勢(shì)，反而會(huì)浪費(fèi)空間，在鏈表較短是采用鏈表而不是紅黑樹(shù)。在理論數(shù)學(xué)計(jì)算中(裝載因子=0.75)，鏈表的長(zhǎng)度到達(dá)8的概率是百萬(wàn)分之一;把7作為分水嶺，大于7轉(zhuǎn)化為紅黑樹(shù)，小于7轉(zhuǎn)化為鏈表。紅黑樹(shù)的出現(xiàn)是為了在某些極端的情況下，抗住大量的hash沖突，正常情況下使用鏈表是更加合適的。
注意，紅黑樹(shù)在jdk1.8之后出現(xiàn)的，jdk1.7采用的是數(shù)組+鏈表模式。
小結(jié)
- HashMap采用鏈地址法，當(dāng)發(fā)生沖突時(shí)會(huì)轉(zhuǎn)化為鏈表，當(dāng)鏈表過(guò)長(zhǎng)會(huì)轉(zhuǎn)化為紅黑樹(shù)提高效率。
- HashMap對(duì)紅黑樹(shù)進(jìn)行了限制，讓紅黑樹(shù)只有在極少數(shù)極端情況下進(jìn)行抗壓。
擴(kuò)容方案
當(dāng)HashMap中的數(shù)據(jù)越來(lái)越多，那么發(fā)生hash沖突的概率也就會(huì)越來(lái)越高，通過(guò)數(shù)組擴(kuò)容可以利用空間換時(shí)間，保持查找效率在常數(shù)時(shí)間復(fù)雜度。那什么時(shí)候進(jìn)行擴(kuò)容?由HashMap的一個(gè)關(guān)鍵參數(shù)控制：裝載因子。
裝載因子=HashMap中節(jié)點(diǎn)數(shù)/數(shù)組長(zhǎng)度，他是一個(gè)比例值。當(dāng)HashMap中節(jié)點(diǎn)數(shù)到達(dá)裝載因子這個(gè)比例時(shí)，就會(huì)觸發(fā)擴(kuò)容;也就是說(shuō)，裝載因子控制了當(dāng)前數(shù)組能夠承載的節(jié)點(diǎn)數(shù)的閾值。如數(shù)組長(zhǎng)度是16，裝載因子是0.75，那么可容納的節(jié)點(diǎn)數(shù)是16*0.75=12。裝載因子的數(shù)值大小需要仔細(xì)權(quán)衡。裝載因子越大，數(shù)組利用率越高，同時(shí)發(fā)生哈希沖突的概率也就越高;裝載因子越小，數(shù)組利用率降低，但發(fā)生哈希沖突的概率也降低了。所以裝載因子的大小需要權(quán)衡空間與時(shí)間之間的關(guān)系。在理論計(jì)算中，0.75是一個(gè)比較合適的數(shù)值，大于0.75哈希沖突的概率呈指數(shù)級(jí)別上升，而小于0.75沖突減少并不明顯。HashMap中的裝載因子的默認(rèn)大小是0.75，沒(méi)有特殊要求的情況下，不建議修改他的值。
那么在到達(dá)閾值之后，HashMap是如何進(jìn)行擴(kuò)容的呢?HashMap會(huì)把數(shù)組長(zhǎng)度擴(kuò)展為原來(lái)的兩倍，再把舊數(shù)組的數(shù)據(jù)遷移到新的數(shù)組，而HashMap針對(duì)遷移做了優(yōu)化：使用HashMap數(shù)組長(zhǎng)度是2的整數(shù)次冪的特點(diǎn)，以一種更高效率的方式完成數(shù)據(jù)遷移。
JDK1.7之前的數(shù)據(jù)遷移比較簡(jiǎn)單，就是遍歷所有的節(jié)點(diǎn)，把所有的節(jié)點(diǎn)依次通過(guò)hash函數(shù)計(jì)算新的下標(biāo)，再插入到新數(shù)組的鏈表中。這樣會(huì)有兩個(gè)缺點(diǎn)：1、每個(gè)節(jié)點(diǎn)都需要進(jìn)行一次求余計(jì)算;2、插入到新的數(shù)組時(shí)候采用的是頭插入法，在多線(xiàn)程環(huán)境下會(huì)形成鏈表環(huán)。jdk1.8之后進(jìn)行了優(yōu)化，原因在于他控制數(shù)組的長(zhǎng)度始終是2的整數(shù)次冪，每次擴(kuò)展數(shù)組都是原來(lái)的2倍，帶來(lái)的好處是key在新的數(shù)組的hash結(jié)果只有兩種：在原來(lái)的位置，或者在原來(lái)位置+原數(shù)組長(zhǎng)度。具體為什么我們可以看下圖：
img
從圖中我們可以看到，在新數(shù)組中的hash結(jié)果，僅僅取決于高一位的數(shù)值。如果高一位是0，那么計(jì)算結(jié)果就是在原位置，而如果是1，則加上原數(shù)組的長(zhǎng)度即可。這樣我們只需要判斷一個(gè)節(jié)點(diǎn)的高一位是1 or 0就可以得到他在新數(shù)組的位置，而不需要重復(fù)hash計(jì)算。HashMap把每個(gè)鏈表拆分成兩個(gè)鏈表，對(duì)應(yīng)原位置或原位置+原數(shù)組長(zhǎng)度，再分別插入到新的數(shù)組中，保留原來(lái)的節(jié)點(diǎn)順序，如下：
img
小結(jié)
- 裝載因子決定了HashMap擴(kuò)容的閾值，需要權(quán)衡時(shí)間與空間，一般情況下保持0.75不作改動(dòng);
- HashMap擴(kuò)容機(jī)制結(jié)合了數(shù)組長(zhǎng)度為2的整數(shù)次冪的特點(diǎn)，以一種更高的效率完成數(shù)據(jù)遷移，同時(shí)避免頭插法造成鏈表環(huán)。
線(xiàn)程安全
HashMap作為一個(gè)集合，主要功能則為CRUD，也就是增刪查改數(shù)據(jù)，那么就肯定涉及到多線(xiàn)程并發(fā)訪(fǎng)問(wèn)數(shù)據(jù)的情況。并發(fā)產(chǎn)生的問(wèn)題，需要我們特別關(guān)注。
HashMap并不是線(xiàn)程安全的，在多線(xiàn)程的情況下無(wú)法保證數(shù)據(jù)的一致性。舉個(gè)例子：HashMap下標(biāo)2的位置為null，線(xiàn)程A需要將節(jié)點(diǎn)X插入下標(biāo)2的位置，在判斷是否為null之后，線(xiàn)程被掛起;此時(shí)線(xiàn)程B把新的節(jié)點(diǎn)Y插入到下標(biāo)2的位置;恢復(fù)線(xiàn)程A，節(jié)點(diǎn)X會(huì)直接插入到下標(biāo)2，覆蓋節(jié)點(diǎn)Y，導(dǎo)致數(shù)據(jù)丟失，如下圖：
jdk1.7及以前擴(kuò)容時(shí)采用的是頭插法，這種方式插入速度快，但在多線(xiàn)程環(huán)境下會(huì)造成鏈表環(huán)，而鏈表環(huán)會(huì)在下一次插入時(shí)找不到鏈表尾而發(fā)生死循環(huán)。
那如果結(jié)果數(shù)據(jù)一致性問(wèn)題呢?解決這個(gè)問(wèn)題有三個(gè)方案：
- 采用Hashtable
- 調(diào)用Collections.synchronizeMap()方法來(lái)讓HashMap具有多線(xiàn)程能力
- 采用ConcurrentHashMap
前兩個(gè)方案的思路是相似的，均是每個(gè)方法中，對(duì)整個(gè)對(duì)象進(jìn)行上鎖。Hashtable是老一代的集合框架，很多的設(shè)計(jì)均以及落后，他在每一個(gè)方法中均加上了synchronize關(guān)鍵字保證線(xiàn)程安全。
- // Hashtable
- public synchronized V get(Object key) {...}
- public synchronized V put(K key, V value) {...}
- public synchronized V remove(Object key) {...}
- public synchronized V replace(K key, V value) {...}
- ...
第二種方法是返回一個(gè)SynchronizedMap對(duì)象，這個(gè)對(duì)象默認(rèn)每個(gè)方法會(huì)鎖住整個(gè)對(duì)象。如下源碼：
img
這里的mutex是什么呢?直接看到構(gòu)造器：
- final Object mutex; // Object on which to synchronize
- SynchronizedMap(Map<K,V> m) {
- this.m = Objects.requireNonNull(m);
- // 默認(rèn)為本對(duì)象
- mutex = this;
- }
- SynchronizedMap(Map<K,V> m, Object mutex) {
- this.m = m;
- this.mutex = mutex;
- }
可以看到默認(rèn)鎖的就是本身，效果和Hashtable其實(shí)是一樣的。這種簡(jiǎn)單粗暴鎖整個(gè)對(duì)象的方式造成的后果是：
- 鎖是非常重量級(jí)的，會(huì)嚴(yán)重影響性能。
- 同一時(shí)間只能有一個(gè)線(xiàn)程進(jìn)行讀寫(xiě)，限制了并發(fā)效率。
ConcurrentHashMap的設(shè)計(jì)就是為了解決此問(wèn)題。他通過(guò)降低鎖粒度+CAS的方式來(lái)提高效率。簡(jiǎn)單來(lái)說(shuō)，ConcurrentHashMap鎖的并不是整個(gè)對(duì)象，而是一個(gè)數(shù)組的一個(gè)節(jié)點(diǎn)，那么其他線(xiàn)程訪(fǎng)問(wèn)數(shù)組其他節(jié)點(diǎn)是不會(huì)互相影響，極大提高了并發(fā)效率;同時(shí)ConcurrentHashMap讀操作并不需要獲取鎖，如下圖：
img
關(guān)于ConcurrentHashMap和Hashtable的更多內(nèi)容，限于篇幅，我會(huì)在另一篇文章講解。那么，使用了上述的三種解決方案是不是絕對(duì)線(xiàn)程安全?先觀(guān)察下面的代碼：
- ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
- map.put("abc","123");
- Thread1:
- if (map.containsKey("abc")){
- String s = map.get("abc");
- }
- Thread2:
- map.remove("abc");
當(dāng)Thread1調(diào)用containsKey之后釋放鎖，Thread2獲得鎖并把“abc”移除再釋放鎖，這個(gè)時(shí)候Thread1讀取到的s就是一個(gè)null了，也就出現(xiàn)了問(wèn)題了。所以ConcurrentHashMap類(lèi)或者Collections.synchronizeMap()方法或者Hashtable都只能在一定的限度上保證線(xiàn)程安全，而無(wú)法保證絕對(duì)線(xiàn)程安全。
關(guān)于線(xiàn)程安全，還有一個(gè)fast-fail問(wèn)題，即快速失敗。當(dāng)使用HashMap的迭代器遍歷HashMap時(shí)，如果此時(shí)HashMap發(fā)生了結(jié)構(gòu)性改變，如插入新數(shù)據(jù)、移除數(shù)據(jù)、擴(kuò)容等，那么Iteractor會(huì)拋出fast-fail異常，防止出現(xiàn)并發(fā)異常，在一定限度上保證了線(xiàn)程安全。如下源碼：
- final Node<K,V> nextNode() {
- ...
- if (modCount != expectedModCount)
- throw new ConcurrentModificationException();
- ...
- }
創(chuàng)建Iteractor對(duì)象時(shí)會(huì)記錄HashMap的modCount變量，每當(dāng)HashMap發(fā)生結(jié)構(gòu)性改變時(shí)，modCount會(huì)加1。在迭代時(shí)判斷HashMap的modCount和自己保存的expectedModCount是否一致即可判斷是否發(fā)生了結(jié)構(gòu)性改變。
fast-fail異常只能當(dāng)做遍歷時(shí)的一種安全保證，而不能當(dāng)做多線(xiàn)程并發(fā)訪(fǎng)問(wèn)HashMap的手段。若有并發(fā)需求，還是需要使用上述的三種方法。
小結(jié)
- HashMap并不能保證線(xiàn)程安全，在多線(xiàn)程并發(fā)訪(fǎng)問(wèn)下會(huì)出現(xiàn)意想不到的問(wèn)題，如數(shù)據(jù)丟失等
- HashMap1.8采用尾插法進(jìn)行擴(kuò)容，防止出現(xiàn)鏈表環(huán)導(dǎo)致的死循環(huán)問(wèn)題
- 解決并發(fā)問(wèn)題的的方案有Hashtable、Collections.synchronizeMap()、ConcurrentHashMap。其中最佳解決方案是ConcurrentHashMap
- 上述解決方案并不能完全保證線(xiàn)程安全
- 快速失敗是HashMap迭代機(jī)制中的一種并發(fā)安全保證
源碼解析
關(guān)鍵變量的理解
HashMap源碼中有很多的內(nèi)部變量，這些變量會(huì)在下面源碼分析中經(jīng)常出現(xiàn)，首先需要理解這些變量的意義。
- // 存放數(shù)據(jù)的數(shù)組
- transient Node<K,V>[] table;
- // 存儲(chǔ)的鍵值對(duì)數(shù)目
- transient int size;
- // HashMap結(jié)構(gòu)修改的次數(shù)，主要用于判斷fast-fail
- transient int modCount;
- // 最大限度存儲(chǔ)鍵值對(duì)的數(shù)目(threshodl=table.length*loadFactor)，也稱(chēng)為閾值
- int threshold;
- // 裝載因子，表示可最大容納數(shù)據(jù)數(shù)量的比例
- final float loadFactor;
- // 靜態(tài)內(nèi)部類(lèi)，HashMap存儲(chǔ)的節(jié)點(diǎn)類(lèi)型；可存儲(chǔ)鍵值對(duì)，本身是個(gè)鏈表結(jié)構(gòu)。
- static class Node<K,V> implements Map.Entry<K,V> {...}
擴(kuò)容
HashMap源碼中把初始化操作也放到了擴(kuò)容方法中，因而擴(kuò)容方法源碼主要分為兩部分：確定新的數(shù)組大小、遷移數(shù)據(jù)。詳細(xì)的源碼分析如下，我打了非常詳細(xì)的注釋?zhuān)蛇x擇查看。擴(kuò)容的步驟在上述已經(jīng)講過(guò)了，讀者可以自行結(jié)合源碼，分析HashMap是如何實(shí)現(xiàn)上述的設(shè)計(jì)。
- final Node<K,V>[] resize() {
- // 變量分別是原數(shù)組、原數(shù)組大小、原閾值；新數(shù)組大小、新閾值
- Node<K,V>[] oldTab = table;
- int oldCap = (oldTab == null) ? 0 : oldTab.length;
- int oldThr = threshold;
- int newCap, newThr = 0;
- // 如果原數(shù)組長(zhǎng)度大于0
- if (oldCap > 0) {
- // 如果已經(jīng)超過(guò)了設(shè)置的最大長(zhǎng)度(1<<30,也就是最大整型正數(shù))
- if (oldCap >= MAXIMUM_CAPACITY) {
- // 直接把閾值設(shè)置為最大正數(shù)
- threshold = Integer.MAX_VALUE;
- return oldTab;
- }
- else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
- oldCap >= DEFAULT_INITIAL_CAPACITY)
- // 設(shè)置為原來(lái)的兩倍
- newThr = oldThr << 1;
- }
- // 原數(shù)組長(zhǎng)度為0，但最大限度不是0，把長(zhǎng)度設(shè)置為閾值
- // 對(duì)應(yīng)的情況就是新建HashMap的時(shí)候指定了數(shù)組長(zhǎng)度
- else if (oldThr > 0)
- newCap = oldThr;
- // 第一次初始化，默認(rèn)16和0.75
- // 對(duì)應(yīng)使用默認(rèn)構(gòu)造器新建HashMap對(duì)象
- else {
- newCap = DEFAULT_INITIAL_CAPACITY;
- newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
- }
- // 如果原數(shù)組長(zhǎng)度小于16或者翻倍之后超過(guò)了最大限制長(zhǎng)度，則重新計(jì)算閾值
- if (newThr == 0) {
- float ft = (float)newCap * loadFactor;
- newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
- (int)ft : Integer.MAX_VALUE);
- }
- threshold = newThr;
- @SuppressWarnings({"rawtypes","unchecked"})
- // 建立新的數(shù)組
- Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
- table = newTab;
- if (oldTab != null) {
- // 循環(huán)遍歷原數(shù)組，并給每個(gè)節(jié)點(diǎn)計(jì)算新的位置
- for (int j = 0; j < oldCap; ++j) {
- Node<K,V> e;
- if ((e = oldTab[j]) != null) {
- oldTab[j] = null;
- // 如果他沒(méi)有后繼節(jié)點(diǎn)，那么直接使用新的數(shù)組長(zhǎng)度取模得到新下標(biāo)
- if (e.next == null)
- newTab[e.hash & (newCap - 1)] = e;
- // 如果是紅黑樹(shù)，調(diào)用紅黑樹(shù)的拆解方法
- else if (e instanceof TreeNode)
- ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
- // 新的位置只有兩種可能：原位置，原位置+老數(shù)組長(zhǎng)度
- // 把原鏈表拆成兩個(gè)鏈表，然后再分別插入到新數(shù)組的兩個(gè)位置上
- // 不用多次調(diào)用put方法
- else {
- // 分別是原位置不變的鏈表和原位置+原數(shù)組長(zhǎng)度位置的鏈表
- Node<K,V> loHead = null, loTail = null;
- Node<K,V> hiHead = null, hiTail = null;
- Node<K,V> next;
- // 遍歷老鏈表，判斷新增判定位是1or0進(jìn)行分類(lèi)
- do {
- next = e.next;
- if ((e.hash & oldCap) == 0) {
- if (loTail == null)
- loHead = e;
- else
- loTail.next = e;
- loTail = e;
- }
- else {
- if (hiTail == null)
- hiHead = e;
- else
- hiTail.next = e;
- hiTail = e;
- }
- } while ((e = next) != null);
- // 最后賦值給新的數(shù)組
- if (loTail != null) {
- loTail.next = null;
- newTab[j] = loHead;
- }
- if (hiTail != null) {
- hiTail.next = null;
- newTab[j + oldCap] = hiHead;
- }
- }
- }
- }
- }
- // 返回新數(shù)組
- return newTab;
- }
添加數(shù)值
調(diào)用put()方法添加鍵值對(duì)，最終會(huì)調(diào)用putVal()來(lái)真正實(shí)現(xiàn)添加邏輯。代碼解析如下：
- public V put(K key, V value) {
- // 獲取hash值，再調(diào)用putVal方法插入數(shù)據(jù)
- return putVal(hash(key), key, value, false, true);
- }
- // onlyIfAbsent表示是否覆蓋舊值，true表示不覆蓋，false表示覆蓋，默認(rèn)為false
- // evict和LinkHashMap的回調(diào)方法有關(guān)，不在本文討論范圍
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- boolean evict) {
- // tab是HashMap內(nèi)部數(shù)組，n是數(shù)組的長(zhǎng)度，i是要插入的下標(biāo)，p是該下標(biāo)對(duì)應(yīng)的節(jié)點(diǎn)
- Node<K,V>[] tab; Node<K,V> p; int n, i;
- // 判斷數(shù)組是否是null或者是否是空，若是，則調(diào)用resize()方法進(jìn)行擴(kuò)容
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- // 使用位與運(yùn)算代替取模得到下標(biāo)
- // 判斷當(dāng)前下標(biāo)是否是null，若是則創(chuàng)建節(jié)點(diǎn)直接插入，若不是，進(jìn)入下面else邏輯
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
- else {
- // e表示和當(dāng)前key相同的節(jié)點(diǎn)，若不存在該節(jié)點(diǎn)則為null
- // k是當(dāng)前數(shù)組下標(biāo)節(jié)點(diǎn)的key
- Node<K,V> e; K k;
- // 判斷當(dāng)前節(jié)點(diǎn)與要插入的key是否相同，是則表示找到了已經(jīng)存在的key
- if (p.hash == hash &&
- ((k = p.key) == key || (key != null && key.equals(k))))
- e = p;
- // 判斷該節(jié)點(diǎn)是否是樹(shù)節(jié)點(diǎn)，如果是調(diào)用紅黑樹(shù)的方法進(jìn)行插入
- else if (p instanceof TreeNode)
- e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- // 最后一種情況是直接鏈表插入
- else {
- for (int binCount = 0; ; ++binCount) {
- if ((e = p.next) == null) {
- p.next = newNode(hash, key, value, null);
- // 長(zhǎng)度大于等于8時(shí)轉(zhuǎn)化為紅黑樹(shù)
- // 注意，treeifyBin方法中會(huì)進(jìn)行數(shù)組長(zhǎng)度判斷，
- // 若小于64，則優(yōu)先進(jìn)行數(shù)組擴(kuò)容而不是轉(zhuǎn)化為樹(shù)
- if (binCount >= TREEIFY_THRESHOLD - 1)
- treeifyBin(tab, hash);
- break;
- }
- // 找到相同的直接跳出循環(huán)
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- break;
- p = e;
- }
- }
- // 如果找到相同的key節(jié)點(diǎn)，則判斷onlyIfAbsent和舊值是否為null
- // 執(zhí)行更新或者不操作，最后返回舊值
- if (e != null) {
- V oldValue = e.value;
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
- }
- // 如果不是更新舊值，說(shuō)明HashMap中鍵值對(duì)數(shù)量發(fā)生變化
- // modCount數(shù)值+1表示結(jié)構(gòu)改變
- ++modCount;
- // 判斷長(zhǎng)度是否達(dá)到最大限度，如果是則進(jìn)行擴(kuò)容
- if (++size > threshold)
- resize();
- // 最后返回null（afterNodeInsertion是LinkHashMap的回調(diào)）
- afterNodeInsertion(evict);
- return null;
- }
代碼中關(guān)于每個(gè)步驟有了詳細(xì)的解釋?zhuān)@里來(lái)總結(jié)一下：
- 總體上分為兩種情況：找到相同的key和找不到相同的key。找了需要判斷是否更新并返回舊value，沒(méi)找到需要插入新的Node、更新節(jié)點(diǎn)數(shù)并判斷是否需要擴(kuò)容。
- 查找分為三種情況：數(shù)組、鏈表、紅黑樹(shù)。數(shù)組下標(biāo)i位置不為空且不等于key，那么就需要判斷是否樹(shù)節(jié)點(diǎn)還是鏈表節(jié)點(diǎn)并進(jìn)行查找。
- 鏈表到達(dá)一定長(zhǎng)度后需要擴(kuò)展為紅黑樹(shù)，當(dāng)且僅當(dāng)鏈表長(zhǎng)度>=8且數(shù)組長(zhǎng)度>=64。
最后畫(huà)一張圖總體再加深一下整個(gè)流程的印象：
img
其他問(wèn)題
為什么jdk1.7以前控制數(shù)組的長(zhǎng)度為素?cái)?shù)，而jdk1.8之后卻采用的是2的整數(shù)次冪?
答：素?cái)?shù)長(zhǎng)度可以有效減少哈希沖突;JDK1.8之后采用2的整數(shù)次冪是為了提高求余和擴(kuò)容的效率，同時(shí)結(jié)合高低位異或的方法使得哈希散列更加均勻。
為何素?cái)?shù)可以減少哈希沖突?若能保證key的hashcode在每個(gè)數(shù)字之間都是均勻分布，那么無(wú)論是素?cái)?shù)還是合數(shù)都是相同的效果。例如hashcode在1~20均勻分布，那么無(wú)論長(zhǎng)度是合數(shù)4，還是素?cái)?shù)5，分布都是均勻的。而如果hashcode之間的間隔都是2，如1,3,5...,那么長(zhǎng)度為4的數(shù)組，位置2和位置4兩個(gè)下標(biāo)無(wú)法放入數(shù)據(jù)，而長(zhǎng)度為5的數(shù)組則沒(méi)有這個(gè)問(wèn)題。長(zhǎng)度為合數(shù)的數(shù)組會(huì)使間隔為其因子的hashcode聚集出現(xiàn)，從而使得散列效果降低。
為什么插入HashMap的數(shù)據(jù)需要實(shí)現(xiàn)hashcode和equals方法?對(duì)這兩個(gè)方法有什么要求?
答：通過(guò)hashcode來(lái)確定插入下標(biāo)，通過(guò)equals比較來(lái)尋找數(shù)據(jù);兩個(gè)相等的key的hashcode必須相等，但擁有相同的hashcode的對(duì)象不一定相等。
這里需要區(qū)分好他們之間的區(qū)別：hashcode就像一個(gè)人的名，相同的人名字肯定相等，但是相同的名字不一定是同個(gè)人;equals比較內(nèi)容是否相同，一般由對(duì)象覆蓋重寫(xiě)，默認(rèn)情況下比較的是引用地址;“==”引用隊(duì)形比較的是引用地址是否相同，值對(duì)象比較的是值是否相同。
HashMap中需要使用hashcode來(lái)獲取key的下標(biāo)，如果兩個(gè)相同的對(duì)象的hashcode不同，那么會(huì)造成HashMap中存在相同的key;所以equals返回相同的key他們的hashcode一定要相同。HashMap比較兩個(gè)元素是否相同采用了三種比較方法結(jié)合：p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))) 。
最后
關(guān)于HashMap的內(nèi)容很難在一篇文章講完，他的設(shè)計(jì)到的內(nèi)容非常多，如線(xiàn)程安全的設(shè)計(jì)可以延伸到ConcurrentHashMap與Hashtable，這兩個(gè)類(lèi)與HashMap的區(qū)別以及內(nèi)部設(shè)計(jì)均非常重要，這些內(nèi)容我將在另外的文章做補(bǔ)充。最后，希望文章對(duì)你有幫助。
