Java集合類的源碼是深入學(xué)習(xí)Java非常好的素材，源碼里很多優(yōu)雅的寫法和思路，會讓人嘆為觀止。HashMap的源碼尤為經(jīng)典，是非常值得去深入研究的，jdk1.8中HashMap發(fā)生了比較大的變化，這方面的東西也是各個公司高頻的考點。網(wǎng)上也有很多應(yīng)對面試的標準答案，我之前也寫過類似的面試技巧（面試必備：Hashtable、HashMap、ConcurrentHashMap的原理與區(qū)別），應(yīng)付一般的面試應(yīng)該是夠了，但個人覺得這還是遠遠不夠，畢竟我們不能只茍且于得到offer，更應(yīng)去勇敢的追求詩和遠方（源碼）。
jdk版本目前更新的相對頻繁，好多小伙伴說jdk1.7才剛真正弄明白，1.8就出現(xiàn)了，1.8還用都沒開始用，更高的jdk版本就又發(fā)布了。很多小伙伴大聲疾呼：臣妾真的學(xué)不動啦！這也許就是技術(shù)的最大魅力吧，活到老學(xué)到老，沒有人能說精通所有技術(shù)。不管jdk版本如何更新，目前jdk1.7和1.8還是各個公司的主力版本。不管是否學(xué)得動，難道各位小伙伴忘記了《倚天屠龍記》里九陽真經(jīng)里的口訣：他強由他強，清風(fēng)拂山崗；他橫由他橫，明月照大江。他自狠來他自惡，我自一口真氣足。（原諒我插入廣告緬懷金庸大師，年少時期讀的最多的書就是金庸大師的，遍布俠骨柔情大義?。?。這里的“真氣”就是先掌握好jdk1.7和1.8，其它學(xué)不動的版本以后再說。
一、初窺HashMap
HashMap是應(yīng)用更廣泛的哈希表實現(xiàn)，而且大部分情況下，都能在常數(shù)時間性能的情況下進行put和get操作。要掌握HashMap，主要從如下幾點來把握：
jdk1.7中底層是由數(shù)組（也有叫做“位桶”的）+鏈表實現(xiàn)；jdk1.8中底層是由數(shù)組+鏈表/紅黑樹實現(xiàn)
可以存儲null鍵和null值，線程不安全
初始size為16，擴容：newsize = oldsize*2，size一定為2的n次冪
擴容針對整個Map，每次擴容時，原來數(shù)組中的元素依次重新計算存放位置，并重新插入
插入元素后才判斷該不該擴容，有可能無效擴容（插入后如果擴容，如果沒有再次插入，就會產(chǎn)生無效擴容）
當(dāng)Map中元素總數(shù)超過Entry數(shù)組的75%，觸發(fā)擴容操作，為了減少鏈表長度，元素分配更均勻
為什么說HashMap是線程不安全的？在接近臨界點時，若此時兩個或者多個線程進行put操作，都會進行resize（擴容）和reHash（為key重新計算所在位置），而reHash在并發(fā)的情況下可能會形成鏈表環(huán)。
二、jdk1.7中HashMap的實現(xiàn)
HashMap底層維護的是數(shù)組+鏈表，我們可以通過一小段源碼來看看：
/**
* The default initial capacity - MUST be a power of two.
*/staticfinalintDEFAULT_INITIAL_CAPACITY =1<<4;// aka 16/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/staticfinalintMAXIMUM_CAPACITY =1<<30;/**
* The load factor used when none specified in constructor.
*/staticfinalfloatDEFAULT_LOAD_FACTOR =0.75f;/**
* An empty table instance to share when the table is not inflated.
*/staticfinalEntry[] EMPTY_TABLE = {};/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/transient Entry[] table = (Entry[]) EMPTY_TABLE;
通過以上代碼可以看出初始容量（16）、負載因子以及對數(shù)組的說明。數(shù)組中的每一個元素其實就是Entry<K,V>[] table，Map中的key和value就是以Entry的形式存儲的。關(guān)于Entry的具體定義參看如下源碼：
staticclass Entry implements Map.Entry {finalKkey; V value; Entry next;inthash;? Entry(inth, K k, V v, Entry n) { value = v; next = n;key= k; hash = h; }publicfinalK getKey() {returnkey; }publicfinalV getValue() {returnvalue; }publicfinalV setValue(V newValue) { V oldValue = value; value = newValue;returnoldValue; }publicfinalbooleanequals(Objecto) {if(!(oinstanceofMap.Entry))returnfalse; Map.Entry e = (Map.Entry)o;Objectk1 = getKey();Objectk2 = e.getKey();if(k1 == k2 || (k1 !=null&& k1.equals(k2))) {Objectv1 = getValue();Objectv2 = e.getValue();if(v1 == v2 || (v1 !=null&& v1.equals(v2)))returntrue; }returnfalse; }publicfinalinthashCode() {returnObjects.hashCode(getKey()) ^ Objects.hashCode(getValue()); }publicfinalStringtoString() {returngetKey() +"="+ getValue(); }/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/voidrecordAccess(HashMap m) { }/**
* This method is invoked whenever the entry is
* removed from the table.
*/voidrecordRemoval(HashMap m) { }}
當(dāng)向 HashMap 中 put 一對鍵值時，它會根據(jù) key的 hashCode 值計算出一個位置， 該位置就是此對象準備往數(shù)組中存放的位置。 該計算過程參看如下代碼：
transientinthashSeed =0;finalinthash(Objectk) {inth = hashSeed;if(0!= h && kinstanceofString) {returnsun.misc.Hashing.stringHash32((String) k); }? h ^= k.hashCode();// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>>20) ^ (h >>>12);returnh ^ (h >>>7) ^ (h >>>4); }/**
* Returns index for hash code h.
*/staticintindexFor(inth,intlength) {// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";returnh & (length-1); }
通過hash計算出來的值將會使用indexFor方法找到它應(yīng)該所在的table下標。當(dāng)兩個key通過hashCode計算相同時，則發(fā)生了hash沖突(碰撞)，HashMap解決hash沖突的方式是用鏈表。當(dāng)發(fā)生hash沖突時，則將存放在數(shù)組中的Entry設(shè)置為新值的next（這里要注意的是，比如A和B都hash后都映射到下標i中，之前已經(jīng)有A了，當(dāng)map.put(B)時，將B放到下標i中，A則為B的next，所以新值存放在數(shù)組中，舊值在新值的鏈表上）。即將新值作為此鏈表的頭節(jié)點，為什么要這樣操作？據(jù)說后插入的Entry被查找的可能性更大（因為get查詢的時候會遍歷整個鏈表），此處有待考究，如果有哪位大神知道，請留言告知。
如果該位置沒有對象存在，就將此對象直接放進數(shù)組當(dāng)中；如果該位置已經(jīng)有對象存在了，則順著此存在的對象的鏈開始尋找(為了判斷是否是否值相同，map不允許<key,value>鍵值對重復(fù))， 如果此鏈上有對象的話，再去使用 equals方法進行比較，如果對此鏈上的每個對象的 equals 方法比較都為 false，則將該對象放到數(shù)組當(dāng)中，然后將數(shù)組中該位置以前存在的那個對象鏈接到此對象的后面。
圖中，左邊部分即代表哈希表，也稱為哈希數(shù)組（默認數(shù)組大小是16，每對key-value鍵值對其實是存在map的內(nèi)部類entry里的），數(shù)組的每個元素都是一個單鏈表的頭節(jié)點，跟著的藍色鏈表是用來解決沖突的，如果不同的key映射到了數(shù)組的同一位置處，就將其放入單鏈表中。
前面說過HashMap的key是允許為null的，當(dāng)出現(xiàn)這種情況時，會放到table[0]中。
privateVputForNullKey(Vvalue){for(Entry e = table[0]; e !=null; e = e.next) {if(e.key ==null) { V oldValue = e.value; e.value=value; e.recordAccess(this);returnoldValue; } } modCount++; addEntry(0,null,value,0);returnnull;}
當(dāng)size>=threshold（ threshold等于“容量*負載因子”）時，會發(fā)生擴容。
id addEntry(inthash, Kkey, V value,intbucketIndex) {if((size>= threshold) && (null!= table[bucketIndex])) { resize(2* table.length); hash = (null!=key) ? hash(key) :0; bucketIndex = indexFor(hash, table.length); }? createEntry(hash,key, value, bucketIndex);}
jdk1.7中resize，只有當(dāng) size>=threshold并且 table中的那個槽中已經(jīng)有Entry時，才會發(fā)生resize。即有可能雖然size>=threshold，但是必須等到每個槽都至少有一個Entry時，才會擴容,可以通過上面的代碼看到每次resize都會擴大一倍容量（2 * table.length）。
三、jdk1.8中HashMap的實現(xiàn)
在jdk1.8中HashMap的內(nèi)部結(jié)構(gòu)可以看作是數(shù)組(Node[] table)和鏈表的復(fù)合結(jié)構(gòu)，數(shù)組被分為一個個桶（bucket），通過哈希值決定了鍵值對在這個數(shù)組中的尋址（哈希值相同的鍵值對，則以鏈表形式存儲。有一點需要注意，如果鏈表大小超過閾值（TREEIFY_THRESHOLD,8），圖中的鏈表就會被改造為樹形（紅黑樹）結(jié)構(gòu)。
transientNode<K,V>[] table;
Entry的名字變成了Node，原因是和紅黑樹的實現(xiàn)TreeNode相關(guān)聯(lián)。
在分析jdk1.7中HashMap的hash沖突時，不知大家是否有個疑問就是萬一發(fā)生碰撞的節(jié)點非常多怎么版？如果說成百上千個節(jié)點在hash時發(fā)生碰撞，存儲一個鏈表中，那么如果要查找其中一個節(jié)點，那就不可避免的花費O(N)的查找時間，這將是多么大的性能損失。這個問題終于在JDK1.8中得到了解決，在最壞的情況下，鏈表查找的時間復(fù)雜度為O(n),而紅黑樹一直是O(logn),這樣會提高HashMap的效率。
jdk1.7中HashMap采用的是位桶+鏈表的方式，即我們常說的散列鏈表的方式，而jdk1.8中采用的是位桶+鏈表/紅黑樹的方式，也是非線程安全的。當(dāng)某個位桶的鏈表的長度達到某個閥值的時候，這個鏈表就將轉(zhuǎn)換成紅黑樹。
jdk1.8中，當(dāng)同一個hash值的節(jié)點數(shù)不小于8時，將不再以單鏈表的形式存儲了，會被調(diào)整成一顆紅黑樹（上圖中null節(jié)點沒畫）。這就是jdk1.7與jdk1.8中HashMap實現(xiàn)的最大區(qū)別。
通過分析put方法的源碼，可以讓這種區(qū)別更直觀：
staticfinalintTREEIFY_THRESHOLD =8;publicV put(Kkey, V value) {returnputVal(hash(key),key, value,false,true); }finalV putVal(inthash, Kkey, V value,booleanonlyIfAbsent,booleanevict) { Node[] tab; Node p;intn, i;//如果當(dāng)前map中無數(shù)據(jù)，執(zhí)行resize方法。并且返回nif((tab = table) ==null|| (n = tab.length) ==0) n = (tab = resize()).length;//如果要插入的鍵值對要存放的這個位置剛好沒有元素，那么把他封裝成Node對象，放在這個位置上即可if((p = tab[i = (n -1) & hash]) ==null) tab[i] = newNode(hash,key, value,null);//否則的話，說明這上面有元素else{ Node e; K k;//如果這個元素的key與要插入的一樣，那么就替換一下。if(p.hash == hash && ((k = p.key) ==key|| (key!=null&&key.equals(k)))) e = p;//1.如果當(dāng)前節(jié)點是TreeNode類型的數(shù)據(jù)，執(zhí)行putTreeVal方法elseif(pinstanceofTreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash,key, value);else{//還是遍歷這條鏈子上的數(shù)據(jù)，跟jdk7沒什么區(qū)別for(intbinCount =0; ; ++binCount) {if((e = p.next) ==null) { p.next = newNode(hash,key, value,null);//2.完成了操作后多做了一件事情，判斷，并且可能執(zhí)行treeifyBin方法if(binCount >= TREEIFY_THRESHOLD -1)// -1 for 1sttreeifyBin(tab, hash);break; }if(e.hash == hash && ((k = e.key) ==key|| (key!=null&&key.equals(k))))break; p = e; } }if(e !=null) {// existing mapping for keyV oldValue = e.value;if(!onlyIfAbsent || oldValue ==null)//true || --e.value = value;//3.afterNodeAccess(e);returnoldValue; } } ++modCount;//判斷閾值，決定是否擴容if(++size> threshold) resize();//4.afterNodeInsertion(evict);returnnull; }以上代碼中的特別之處如下：12if(binCount >= TREEIFY_THRESHOLD -1)// -1 for 1sttreeifyBin(tab, hash);
treeifyBin()就是將鏈表轉(zhuǎn)換成紅黑樹。
putVal方法處理的邏輯比較多，包括初始化、擴容、樹化，近乎在這個方法中都能體現(xiàn)，針對源碼簡單講解下幾個關(guān)鍵點：
如果Node<K,V>[] table是null，resize方法會負責(zé)初始化，即如下代碼：
if((tab= table) == null || (n =tab.length) ==0) n = (tab= resize()).length;
resize方法兼顧兩個職責(zé)，創(chuàng)建初始存儲表格，或者在容量不滿足需求的時候，進行擴容（resize）。
在放置新的鍵值對的過程中，如果發(fā)生下面條件，就會發(fā)生擴容。
if(++size > threshold)resize();
具體鍵值對在哈希表中的位置（數(shù)組index）取決于下面的位運算：
i= (n -1) & hash
仔細觀察哈希值的源頭，會發(fā)現(xiàn)它并不是key本身的hashCode，而是來自于HashMap內(nèi)部的另一個hash方法。為什么這里需要將高位數(shù)據(jù)移位到低位進行異或運算呢？這是因為有些數(shù)據(jù)計算出的哈希值差異主要在高位，而HashMap里的哈希尋址是忽略容量以上的高位的，那么這種處理就可以有效避免類似情況下的哈希碰撞。
在jdk1.8中取消了indefFor()方法，直接用(tab.length-1)&hash，所以看到這個，代表的就是數(shù)組的下角標。
staticfinalinthash(Objectkey) {inth;return(key==null) ?0: (h =key.hashCode()) ^ (h >>>16);}
為什么HashMap為什么要樹化？
之前在極客時間的專欄里看到過一個解釋。本質(zhì)上這是個安全問題。因為在元素放置過程中，如果一個對象哈希沖突，都被放置到同一個桶里，則會形成一個鏈表，我們知道鏈表查詢是線性的，會嚴重影響存取的性能。而在現(xiàn)實世界，構(gòu)造哈希沖突的數(shù)據(jù)并不是非常復(fù)雜的事情，惡意代碼就可以利用這些數(shù)據(jù)大量與服務(wù)器端交互，導(dǎo)致服務(wù)器端CPU大量占用，這就構(gòu)成了哈希碰撞拒絕服務(wù)攻擊，國內(nèi)一線互聯(lián)網(wǎng)公司就發(fā)生過類似攻擊事件。
四、分析Hashtable、HashMap、TreeMap的區(qū)別
HashMap是繼承自AbstractMap類，而HashTable是繼承自Dictionary類。不過它們都實現(xiàn)了同時實現(xiàn)了map、Cloneable（可復(fù)制）、Serializable（可序列化）這三個接口。存儲的內(nèi)容是基于key-value的鍵值對映射，不能由重復(fù)的key，而且一個key只能映射一個value。
Hashtable的key、value都不能為null；HashMap的key、value可以為null，不過只能有一個key為null，但可以有多個null的value；TreeMap鍵、值都不能為null。
Hashtable、HashMap具有無序特性。TreeMap是利用紅黑樹實現(xiàn)的（樹中的每個節(jié)點的值都會大于或等于它的左子樹中的所有節(jié)點的值，并且小于或等于它的右子樹中的所有節(jié)點的值），實現(xiàn)了SortMap接口，能夠?qū)Ρ４娴挠涗浉鶕?jù)鍵進行排序。所以一般需求排序的情況下首選TreeMap，默認按鍵的升序排序（深度優(yōu)先搜索），也可以自定義實現(xiàn)Comparator接口實現(xiàn)排序方式。
一般情況下我們選用HashMap，因為HashMap的鍵值對在取出時是隨機的，其依據(jù)鍵的hashCode和鍵的equals方法存取數(shù)據(jù)，具有很快的訪問速度，所以在Map中插入、刪除及索引元素時其是效率最高的實現(xiàn)。而TreeMap的鍵值對在取出時是排過序的，所以效率會低點。
TreeMap是基于紅黑樹的一種提供順序訪問的Map，與HashMap不同的是它的get、put、remove之類操作都是o(log(n))的時間復(fù)雜度，具體順序可以由指定的Comparator來決定，或者根據(jù)鍵的自然順序來判斷。
對HashMap做下總結(jié)：
HashMap基于哈希散列表實現(xiàn) ，可以實現(xiàn)對數(shù)據(jù)的讀寫。將鍵值對傳遞給put方法時，它調(diào)用鍵對象的hashCode()方法來計算hashCode，然后找到相應(yīng)的bucket位置（即數(shù)組）來儲存值對象。當(dāng)獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。HashMap使用鏈表來解決hash沖突問題，當(dāng)發(fā)生沖突了，對象將會儲存在鏈表的頭節(jié)點中。HashMap在每個鏈表節(jié)點中儲存鍵值對對象，當(dāng)兩個不同的鍵對象的hashCode相同時，它們會儲存在同一個bucket位置的鏈表中，如果鏈表大小超過閾值（TREEIFY_THRESHOLD,8），鏈表就會被改造為樹形結(jié)構(gòu)。
歡迎工作一到五年的Java工程師朋友們加入Java架構(gòu)開發(fā)： 854393687
群內(nèi)提供免費的Java架構(gòu)學(xué)習(xí)資料（里面有高可用、高并發(fā)、高性能及分布式、Jvm性能調(diào)優(yōu)、Spring源碼，MyBatis，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多個知識點的架構(gòu)資料）合理利用自己每一分每一秒的時間來學(xué)習(xí)提升自己，不要再用"沒有時間“來掩飾自己思想上的懶惰！趁年輕，使勁拼，給未來的自己一個交代！
