我們一直在用的HashMap，你真正了解嗎？擴容機制又是什么？
來源:github.com/feigeswjtu
什么是HashMap?
HashMap是基于哈希表的Map接口的非同步實現(xiàn)。此實現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。
HashMap的數(shù)據(jù)結(jié)構(gòu)
在Java編程語言中，最基本的結(jié)構(gòu)就是兩種，一個是數(shù)組，另外一個是模擬指針（引用），所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個基本結(jié)構(gòu)來構(gòu)造的，HashMap也不例外。HashMap實際上是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體。
文字描述永遠要配上圖才能更好的講解數(shù)據(jù)結(jié)構(gòu)，HashMap的結(jié)構(gòu)圖如下。
從上圖中可以看出，HashMap底層就是一個數(shù)組結(jié)構(gòu)，數(shù)組中的每一項又是一個鏈表或者紅黑樹。當新建一個HashMap的時候，就會初始化一個數(shù)組。
下面先通過大概看下HashMap的核心成員。
public?class?HashMap<K,V>?extends?AbstractMap<K,V>
????implements?Map<K,V>,?Cloneable,?Serializable?{
????//?默認容量，默認為16，必須是2的冪
????static?final?int?DEFAULT_INITIAL_CAPACITY?=?1?<4;
????//?最大容量，值是2^30
????static?final?int?MAXIMUM_CAPACITY?=?1?<30
????//?裝載因子，默認的裝載因子是0.75
????static?final?float?DEFAULT_LOAD_FACTOR?=?0.75f;
????//?解決沖突的數(shù)據(jù)結(jié)構(gòu)由鏈表轉(zhuǎn)換成樹的閾值，默認為8
????static?final?int?TREEIFY_THRESHOLD?=?8;
????//?解決沖突的數(shù)據(jù)結(jié)構(gòu)由樹轉(zhuǎn)換成鏈表的閾值，默認為6
????static?final?int?UNTREEIFY_THRESHOLD?=?6;
????/*?當桶中的bin被樹化時最小的hash表容量。
?????*??如果沒有達到這個閾值，即hash表容量小于MIN_TREEIFY_CAPACITY，當桶中bin的數(shù)量太多時會執(zhí)行resize擴容操作。
?????*??這個MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。
?????*/
????static?final?int?MIN_TREEIFY_CAPACITY?=?64;
????static?class?Node<K,V>?implements?Map.Entry<K,V>?{
????????//...
????}
????//?存儲數(shù)據(jù)的數(shù)組
????transient?Node[]?table;
????//?遍歷的容器
????transient?Set>?entrySet;
????//?Map中KEY-VALUE的數(shù)量
????transient?int?size;
????/**
?????*?結(jié)構(gòu)性變更的次數(shù)。
?????*?結(jié)構(gòu)性變更是指map的元素數(shù)量的變化，比如rehash操作。
?????*?用于HashMap快速失敗操作，比如在遍歷時發(fā)生了結(jié)構(gòu)性變更，就會拋出ConcurrentModificationException。
?????*/
????transient?int?modCount;
????//?下次resize的操作的size值。
????int?threshold;
????//?負載因子，resize后容量的大小會增加現(xiàn)有size?*?loadFactor
????final?float?loadFactor;
}
HashMap的初始化
public?HashMap()?{
????this.loadFactor?=?DEFAULT_LOAD_FACTOR;?//?其他值都是默認值
}
通過源碼可以看出初始化時并沒有初始化數(shù)組table，那只能在put操作時放入了，為什么要這樣做？估計是避免初始化了HashMap之后不使用反而占用內(nèi)存吧，哈哈哈。
HashMap的存儲操作
public?V?put(K?key,?V?value)?{
????return?putVal(hash(key),?key,?value,?false,?true);
}
下面我們詳細講一下HashMap是如何確定數(shù)組索引的位置、進行put操作的詳細過程以及擴容機制(resize)
hash計算，確定數(shù)組索引位置
不管增加、刪除、查找鍵值對，定位到哈希桶數(shù)組的位置都是很關(guān)鍵的第一步。前面說過HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合，所以我們當然希望這個HashMap里面的元素位置盡量分布均勻些，盡量使得每個位置上的元素數(shù)量只有一個，那么當我們用hash算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，不用遍歷鏈表，大大優(yōu)化了查詢的效率。HashMap定位數(shù)組索引位置，直接決定了hash方法的離散性能。
看下源碼的實現(xiàn):
static?final?int?hash(Object?key)?{???//jdk1.8
???int?h;
???//?h?=?key.hashCode()?為第一步?取hashCode值
???//?h?^?(h?>>>?16)??為第二步?高位參與運算
???return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);
}
通過hashCode()的高16位異或低16位實現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、質(zhì)量來考慮的，這么做可以在數(shù)組table的length比較小的時候，也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷。
大家都知道上面代碼里的key.hashCode()函數(shù)調(diào)用的是key鍵值類型自帶的哈希函數(shù)，返回int型散列值。理論上散列值是一個int型，如果直接拿散列值作為下標訪問HashMap主數(shù)組的話，考慮到2進制32位帶符號的int表值范圍從?2147483648到2147483648。前后加起來大概40億的映射空間。只要哈希函數(shù)映射得比較均勻松散，一般應用是很難出現(xiàn)碰撞的。但問題是一個40億長度的數(shù)組，內(nèi)存是放不下的。你想，HashMap擴容之前的數(shù)組初始大小才16。所以這個散列值是不能直接拿來用的。用之前還要先做對數(shù)組的長度取模運算，得到的余數(shù)才能用來訪問數(shù)組下標。源碼中模運算是在這個indexFor( )函數(shù)里完成。
bucketIndex?=?indexFor(hash,?table.length);
//indexFor的代碼也很簡單，就是把散列值和數(shù)組長度做一個"與"操作，
static?int?indexFor(int?h,?int?length)?{
???return?h?&?(length-1);
}
順便說一下，這也正好解釋了為什么HashMap的數(shù)組長度要取2的整次冪。因為這樣（數(shù)組長度?1）正好相當于一個“低位掩碼”?！芭c”操作的結(jié)果就是散列值的高位全部歸零，只保留低位值，用來做數(shù)組下標訪問。以初始長度16為例，16?1=15。2進制表示是00000000 0000000000001111。和某散列值做“與”操作如下，結(jié)果就是截取了最低的四位值。
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101 //高位全部歸零，只保留末四位
但這時候問題就來了，這樣就算我的散列值分布再松散，要是只取最后幾位的話，碰撞也會很嚴重。更要命的是如果散列本身做得不好，分布上成等差數(shù)列的漏洞，恰好使最后幾個低位呈現(xiàn)規(guī)律性重復，就無比蛋疼。這時候“擾動函數(shù)”的價值就出來了，說到這大家應該都明白了，看下圖。
右位移16位，正好是32bit的一半，自己的高半?yún)^(qū)和低半?yún)^(qū)做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機性。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來。
putVal方法
HashMap的put方法執(zhí)行過程可以通過下圖來理解，自己有興趣可以去對比源碼更清楚地研究學習。
源碼以及解釋如下:
//?真正的put操作
final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,
????????????????boolean?evict)?{
????Node[]?tab;?Node?p;?int?n,?i;
????//?如果table沒有初始化，或者初始化的大小為0，進行resize操作
????if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)
????????n?=?(tab?=?resize()).length;
????//?如果hash值對應的桶內(nèi)沒有數(shù)據(jù)，直接生成結(jié)點并且把結(jié)點放入桶中
????if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)
????????tab[i]?=?newNode(hash,?key,?value,?null);
????//?如果hash值對應的桶內(nèi)有數(shù)據(jù)解決沖突，再放入桶中
????else?{
????????Node?e;?K?k;
????????//判斷put的元素和已經(jīng)存在的元素是相同(hash一致，并且equals返回true)
????????if?(p.hash?==?hash?&&
????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????e?=?p;
????????//?put的元素和已經(jīng)存在的元素是不相同(hash一致，并且equals返回true)
????????//?如果桶內(nèi)元素的類型是TreeNode，也就是解決hash解決沖突用的樹型結(jié)構(gòu)，把元素放入樹種
????????else?if?(p?instanceof?TreeNode)
????????????e?=?((TreeNode)p).putTreeVal(this,?tab,?hash,?key,?value);
????????else?{
????????????//?桶內(nèi)元素的類型不是TreeNode，而是鏈表時，把數(shù)據(jù)放入鏈表的最后一個元素上
????????????for?(int?binCount?=?0;?;?++binCount)?{
????????????????if?((e?=?p.next)?==?null)?{
????????????????????p.next?=?newNode(hash,?key,?value,?null);
????????????????????//?如果鏈表的長度大于轉(zhuǎn)換為樹的閾值(TREEIFY_THRESHOLD)，將存儲元素的數(shù)據(jù)結(jié)構(gòu)變更為樹
????????????????????if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1st
????????????????????????treeifyBin(tab,?hash);
????????????????????break;
????????????????}
????????????????//?如果查已經(jīng)存在key，停止遍歷
????????????????if?(e.hash?==?hash?&&
????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????????break;
????????????????p?=?e;
????????????}
????????}
????????//?已經(jīng)存在元素時
????????if?(e?!=?null)?{?//?existing?mapping?for?key
????????????V?oldValue?=?e.value;
????????????if?(!onlyIfAbsent?||?oldValue?==?null)
????????????????e.value?=?value;
????????????afterNodeAccess(e);
????????????return?oldValue;
????????}
????}
????++modCount;
????//?如果K-V數(shù)量大于閾值，進行resize操作
????if?(++size?>?threshold)
????????resize();
????afterNodeInsertion(evict);
????return?null;
}
擴容機制
HashMap的擴容機制用的很巧妙，以最小的性能來完成擴容。擴容后的容量就變成了變成了之前容量的2倍，初始容量為16，所以經(jīng)過rehash之后，元素的位置要么是在原位置，要么是在原位置再向高下標移動上次容量次數(shù)的位置，也就是說如果上次容量是16，下次擴容后容量變成了16+16，如果一個元素在下標為7的位置，下次擴容時，要不還在7的位置，要不在7+16的位置。
我們下面來解釋一下Java8的擴容機制是怎么做到的？n為table的長度，圖（a）表示擴容前的key1和key2兩種key確定索引位置的示例，圖（b）表示擴容后key1和key2兩種key確定索引位置的示例，其中hash1是key1對應的哈希與高位運算結(jié)果。
元素在重新計算hash之后，因為n變?yōu)?倍，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會發(fā)生這樣的變化：
因此，我們在擴充HashMap的時候，不需要像JDK1.7的實現(xiàn)那樣重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”，可以看看下圖為16擴充為32的resize示意圖：
而hash值的高位是否為1，只需要和擴容后的長度做與操作就可以了，因為擴容后的長度為2的次冪，所以高位必為1，低位必為0，如10000這種形式，源碼中有e.hash & oldCap來做到這個邏輯。
這個設計確實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由于新增的1bit是0還是1可以認為是隨機的，因此resize的過程，均勻的把之前的沖突的節(jié)點分散到新的bucket了。這一塊就是JDK1.8新增的優(yōu)化點。有一點注意區(qū)別，JDK1.7中rehash的時候，舊鏈表遷移新鏈表的時候，如果在新表的數(shù)組索引位置相同，則鏈表元素會倒置，但是從上圖可以看出，JDK1.8不會倒置。下面是JDK1.8的resize源碼，寫的很贊，如下:
final?Node[]?resize()?{
????Node[]?oldTab?=?table;
????int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;
????int?oldThr?=?threshold;
????int?newCap,?newThr?=?0;
????//?計算新的容量值和下一次要擴展的容量
????if?(oldCap?>?0)?{
????//?超過最大值就不再擴充了，就只好隨你碰撞去吧
????????if?(oldCap?>=?MAXIMUM_CAPACITY)?{
????????????threshold?=?Integer.MAX_VALUE;
????????????return?oldTab;
????????}
????????//?沒超過最大值，就擴充為原來的2倍
????????else?if?((newCap?=?oldCap?<1)?????????????????????oldCap?>=?DEFAULT_INITIAL_CAPACITY)
????????????newThr?=?oldThr?<1;?//?double?threshold
????}
????else?if?(oldThr?>?0)?//?initial?capacity?was?placed?in?threshold
????????newCap?=?oldThr;
????else?{???????????????//?zero?initial?threshold?signifies?using?defaults
????????newCap?=?DEFAULT_INITIAL_CAPACITY;
????????newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);
????}
????//?計算新的resize上限
????if?(newThr?==?0)?{
????????float?ft?=?(float)newCap?*?loadFactor;
????????newThr?=?(newCap?float)MAXIMUM_CAPACITY??
????????????????????(int)ft?:?Integer.MAX_VALUE);
????}
????threshold?=?newThr;
????@SuppressWarnings({"rawtypes","unchecked"})
????????Node[]?newTab?=?(Node[])new?Node[newCap];
????table?=?newTab;
????if?(oldTab?!=?null)?{
????????//?把每個bucket都移動到新的buckets中
????????for?(int?j?=?0;?j?????????????Node?e;
????????????//如果位置上沒有元素，直接為null
????????????if?((e?=?oldTab[j])?!=?null)?{
????????????????oldTab[j]?=?null;
????????????????//如果只有一個元素，新的hash計算后放入新的數(shù)組中
????????????????if?(e.next?==?null)
????????????????????newTab[e.hash?&?(newCap?-?1)]?=?e;
????????????????//如果是樹狀結(jié)構(gòu)，使用紅黑樹保存
????????????????else?if?(e?instanceof?TreeNode)
????????????????????((TreeNode)e).split(this,?newTab,?j,?oldCap);
????????????????//如果是鏈表形式
????????????????else?{?//?preserve?order
????????????????????Node?loHead?=?null,?loTail?=?null;
????????????????????Node?hiHead?=?null,?hiTail?=?null;
????????????????????Node?next;
????????????????????do?{
????????????????????????next?=?e.next;
????????????????????????//hash碰撞后高位為0，放入低Hash值的鏈表中
????????????????????????if?((e.hash?&?oldCap)?==?0)?{
????????????????????????????if?(loTail?==?null)
????????????????????????????????loHead?=?e;
????????????????????????????else
????????????????????????????????loTail.next?=?e;
????????????????????????????loTail?=?e;
????????????????????????}
????????????????????????//hash碰撞后高位為1，放入高Hash值的鏈表中
????????????????????????else?{
????????????????????????????if?(hiTail?==?null)
????????????????????????????????hiHead?=?e;
????????????????????????????else
????????????????????????????????hiTail.next?=?e;
????????????????????????????hiTail?=?e;
????????????????????????}
????????????????????}?while?((e?=?next)?!=?null);
????????????????????//?低hash值的鏈表放入數(shù)組的原始位置
????????????????????if?(loTail?!=?null)?{
????????????????????????loTail.next?=?null;
????????????????????????newTab[j]?=?loHead;
????????????????????}
????????????????????//?高hash值的鏈表放入數(shù)組的原始位置?+?原始容量
????????????????????if?(hiTail?!=?null)?{
????????????????????????hiTail.next?=?null;
????????????????????????newTab[j?+?oldCap]?=?hiHead;
????????????????????}
????????????????}
????????????}
????????}
????}
????return?newTab;
}