HashMap對于每一個開發(fā)者來說再熟悉不過了，本文就來講講它究竟是如何實(shí)現(xiàn)的。最開始我并不打算直接對著源碼來說這些疚察，從生活中具體事情來說原理，可以讓人印象更深刻仇奶，也更容易理解貌嫡！
生活小例子
發(fā)現(xiàn)問題
生活中你是一個熱愛看書的人，所以私底下藏有很多書籍猜嘱，像《白夜行》衅枫、《三體》等嫁艇，剛開始你都是把書隨意放在桌子上朗伶，每天看看書喝喝茶，日子過的非常愜意步咪。隨著時(shí)間增長论皆，你的書也越來越多。慢慢的問題出現(xiàn)了猾漫，由于書都是無規(guī)則的放在桌子上点晴，少的時(shí)候還好，這書多了以后悯周，想快速找到需要的那本書越來越困難粒督，可能翻個幾分鐘都找不到，有木有禽翼？
解決問題
這樣下去不是辦法蚣抗，機(jī)智的你靈光一閃毛嫉，想到一個辦法。這樣無規(guī)則的擺放增加了我找書的難度，為了快速找到我需要的書籍织咧，我可以把桌子分為N個區(qū)域，每個區(qū)域用A机隙、B智玻、C這樣的字母來標(biāo)記，然后把書名第一個字的首字母按這個區(qū)域標(biāo)記來規(guī)則的擺放（如：安徒生童話=》A夺脾，白夜行=》B）之拨，當(dāng)我要找書的時(shí)候，可以直接根據(jù)名字就能快速的定位到書在哪個區(qū)域咧叭，找到區(qū)域后再找到想要的那本書蚀乔，速度大大提升了，你心里美滋滋的佳簸，效果圖如下
書本《安徒生童話》的首字母為A乙墙，因此這本書被你放到了A標(biāo)記的區(qū)域颖变，而《白夜行》和《白鹿原》的首字母都是B，所以它們兩個都應(yīng)該放到B區(qū)域中听想，就這樣你把所有的書籍都按這個規(guī)則整理好了腥刹。相比之前，現(xiàn)在想找一本書簡直快的多了汉买，比如我想要看《三體》衔峰，直接找到書桌上S標(biāo)記的區(qū)域，然后在這區(qū)域疊起來的一摞書中找就是了蛙粘！這個時(shí)候你太佩服自己了垫卤。
問題升級
這樣的設(shè)計(jì)讓你舒舒服服的過了很久，可是時(shí)間久了你又遇到一個問題了：B區(qū)域的書太多了出牧。我找一本首字母為B開頭的書還是需要費(fèi)很大力氣呀穴肘，這個時(shí)候你又陷入了沉思，能不能對這里稍微再改進(jìn)呢舔痕？
最終方案
有一天评抚，你在X寶無意中發(fā)現(xiàn)一個東西
咦，這個東西不錯呀伯复，把某個區(qū)域過多的書用這個代替慨代，在這個書架中你可以再設(shè)定自己的一套規(guī)則（比如書名不超過5個字的可以放右側(cè)，超過了的就放左側(cè)）啸如，方便更快速的找書侍匙，完美！當(dāng)然你不會每個區(qū)域都買個小書架叮雳，這樣成本太高了想暗，所以你決定每當(dāng)某個區(qū)域的書本多于N的時(shí)候（N由你自己決定），你就放一個小書架到這個區(qū)域里面债鸡，最終方案如下
經(jīng)過上面的文字江滨，你知道HashMap的原理了嗎？
HashMap 結(jié)構(gòu)圖
jdk1.7結(jié)構(gòu)圖
如果仔細(xì)讀了上面的小故事厌均，我想HashMap的原理大概已經(jīng)知道了唬滑，現(xiàn)在我們來看下HashMap1.7的結(jié)構(gòu)圖
看到這個圖是不是和上文中的書桌與書本極其相識？這里的table[]數(shù)組表示書桌棺弊，數(shù)組的每一個元素代表書桌的標(biāo)記字母的區(qū)域晶密，而entry節(jié)點(diǎn)表示書本。HashMap不斷的存取數(shù)據(jù)（put方法）其實(shí)就是不斷的向書桌增加書本模她。在HashMap里面有個概念叫Hash沖突稻艰，就是類似不同書本的首字母可能會相同，在書桌上我們采用一本本的疊加起來解決問題侈净，相當(dāng)于上圖當(dāng)中的鏈表尊勿。
jdk1.8結(jié)構(gòu)圖
在上面的故事中已經(jīng)提到了僧凤，當(dāng)書桌某個區(qū)域中的書越來越多的時(shí)候，我們在里面加了個小書架元扔，因此在HashMap1.8中同樣為了優(yōu)化區(qū)域中搜索而引入了紅黑樹躯保，來看下HashMap1.8的結(jié)構(gòu)圖
在HashMap1.8中引入了紅黑樹，能在鏈表長度過多的時(shí)候澎语，增加查詢速度途事。這就跟上面書桌區(qū)域中引入一個書架是一個道理，由于書太多擅羞，一本本的查詢還是會花比較多的時(shí)間尸变，針對區(qū)域進(jìn)行優(yōu)化，可以更快速的找到想要的書减俏。
好了召烂，說了這么多，是時(shí)候進(jìn)入主題了垄懂。
HashMap 源碼解析
關(guān)鍵變量
在HashMap源碼中有幾個關(guān)鍵變量骑晶，我們必須知道，通過這些變量我們可以更容易理解它的底層原理草慧，注意這里的源碼是基于1.8版本的
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_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.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4；默認(rèn)起始容量匙头，就是table數(shù)組的默認(rèn)長度（2的4次方）漫谷，相當(dāng)于書桌上的區(qū)域數(shù)量，必須為2的N次方（為什么蹂析？后面解釋）舔示。
static final int MAXIMUM_CAPACITY = 1 << 30；最大容量电抚，table數(shù)組的長度不能超過這個（2的30次方）惕稻，即使超過也不會再改變。
static final float DEFAULT_LOAD_FACTOR = 0.75f蝙叛；加載因子俺祠，這個干嘛的呢？我們知道table是一個數(shù)組借帘，初始化的時(shí)候都必須指定一個長度蜘渣，隨著HashMap不斷的put東西進(jìn)去，這個數(shù)組需要擴(kuò)容也就是增加長度肺然。這個時(shí)候就是根據(jù)這個加載因子來擴(kuò)容的蔫缸，初始化的時(shí)候?yàn)?6，當(dāng)數(shù)組中的元素?cái)?shù)量達(dá)到16*0.75=12的時(shí)候际起，table長度會變成原來的兩倍拾碌。
static final int TREEIFY_THRESHOLD = 8吐葱；鏈表轉(zhuǎn)紅黑樹閾值，當(dāng)鏈表數(shù)量超過這個數(shù)的時(shí)候校翔，它會將鏈表轉(zhuǎn)為紅黑樹（這里并不打算講紅黑樹的特性唇撬，具體百度，嚴(yán)格來說還有一個因素會影響是否轉(zhuǎn)化成紅黑樹MIN_TREEIFY_CAPACITY展融，具體往下看）窖认。
static final int UNTREEIFY_THRESHOLD = 6；紅黑樹轉(zhuǎn)鏈表閾值告希，當(dāng)紅黑樹數(shù)量小于這個數(shù)的時(shí)候扑浸，它會將紅黑樹轉(zhuǎn)變?yōu)殒湵怼?/p>
static final int MIN_TREEIFY_CAPACITY = 64；這個也是鏈表轉(zhuǎn)為紅黑樹的一個條件燕偶，前面提到的一個條件是鏈表中的個數(shù)要大于8喝噪。而這里則是table數(shù)組的長度需要超過64，也就是說只有兩個條件達(dá)到才會由鏈表轉(zhuǎn)化為紅黑樹指么。
關(guān)鍵類與方法
hash()方法
hash方法對應(yīng)將書本名稱換算成字母的一個方法酝惧，如hash("安徒生童話") = A，貼上源碼
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
該方法能將一個key轉(zhuǎn)換成int型的值伯诬。需要注意的是不同的key經(jīng)過hash方法得到的值有可能是相同的晚唇，這就是所謂的hash沖突，前面也提到了盗似，解決hash沖突主要采用的是拉鏈?zhǔn)降逆湵斫Y(jié)構(gòu)哩陕。從代碼上我們也可以知道，當(dāng)key為null的時(shí)候赫舒，統(tǒng)一規(guī)定hash返回為0悍及，也就是說key為null的鍵值對會被放在table[0]這個區(qū)域里面（類似書桌第一塊區(qū)域）。
Node類
Node是HashMap中的一個內(nèi)部類接癌，充當(dāng)書桌上的書這一角色心赶，組成鏈表的關(guān)鍵，先來看源碼
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
用通俗的話來說明上面的具體參數(shù)缺猛，hash指書名經(jīng)過規(guī)則換算成A字母缨叫，key值書本名稱，value指具體的書枯夜，next蓋在當(dāng)前書上書籍弯汰，形成拉鏈?zhǔn)降慕Y(jié)構(gòu)。
put(K key, V value)方法
看了源碼的話我們會發(fā)現(xiàn)湖雹，在HashMap中的put方法實(shí)際上是調(diào)用了另外一個方法putVal咏闪。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
因此我們接下來看putVal這個方法，每行都補(bǔ)充了相關(guān)注釋
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//將table賦值給tab摔吏，如果table為空或者長度為0鸽嫂，則調(diào)用resize()初始化纵装，再把長度賦值給n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//這里(n - 1) & hash相當(dāng)于hash%(n-1)，判斷tab[i]這個區(qū)域是否已經(jīng)有值据某，如果沒有橡娄，則新建一個節(jié)點(diǎn)，并且賦值給p癣籽，把節(jié)點(diǎn)放到這個區(qū)域
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果tab[i]里面已經(jīng)存在值了
else {
Node<K,V> e; K k;
//如果p這個節(jié)點(diǎn)的傳進(jìn)來的是一樣的挽唉，則把p賦值給e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果p為樹類型節(jié)點(diǎn)，則調(diào)用樹的putTreeVal方法筷狼，此方法就是一個紅黑樹添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//遍歷區(qū)域中所有節(jié)點(diǎn)
else {
for (int binCount = 0; ; ++binCount) {
//將p的子節(jié)點(diǎn)賦值給e瓶籽，如果區(qū)域中沒有相同key的節(jié)點(diǎn)則直接插入到區(qū)域中（可能是鏈表可能是紅黑樹，具體查看treeifyBin方法）埂材，退出循環(huán)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果區(qū)域中有相同key的節(jié)點(diǎn)直接退出循環(huán)塑顺，
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//以上都沒有，則e賦值給p繼續(xù)循環(huán)
p = e;
}
}
//e不為空俏险，說明之前區(qū)域中存在key與現(xiàn)在新的key相同严拒，這時(shí)候?qū)⑿轮蹈采w原來的舊值，并且返回舊值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
另外再附上一張put方法完整流程圖（點(diǎn)擊可看大圖）
get(Object key)方法
同樣竖独，從源碼中可以看到主要是調(diào)用了getNode這個方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
下面貼上getNode的源碼裤唠，里面也添加了相關(guān)注釋
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//判斷table是否為空并且長度不為0，根據(jù)hash得到應(yīng)該存放的區(qū)域预鬓，區(qū)域頭節(jié)點(diǎn)也不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//是否與頭結(jié)點(diǎn)的key相同巧骚，相同則直接返回該節(jié)點(diǎn)
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//頭結(jié)點(diǎn)不匹配則進(jìn)入遍歷
if ((e = first.next) != null) {
//如果是樹節(jié)點(diǎn)，遍歷紅黑樹格二，找到節(jié)點(diǎn)立即返回該節(jié)點(diǎn)，具體紅黑樹的遍歷查詢需要查看getTreeNode方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//否則遍歷鏈表竣蹦，找到節(jié)點(diǎn)立即返回該節(jié)點(diǎn)
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//沒有找到對應(yīng)的key顶猜，說明不存在，返回null;
return null;
}
總結(jié)
源碼分析并不難痘括，需要一顆平靜的心长窄，切勿浮躁。每個人的理解都不一樣纲菌，選擇自己的方式挠日，效果會更明顯。另外就是不能被一些專業(yè)的術(shù)語所嚇到翰舌，很多所謂的術(shù)語其實(shí)很簡單嚣潜。
