導(dǎo)讀：本文分析的是源碼躺翻，所以至少讀者要熟悉他們的接口使用鳞芙，同時眷柔，對于并發(fā)，讀者至少要知道 CAS原朝、ReentrantLock驯嘱、UNSAFE操作這幾個基本知識，文中不會對這些知識進(jìn)行介紹喳坠。Java8 用到了紅黑樹鞠评，不過本文不會進(jìn)行展開，感興趣的讀者請自行查找相關(guān)資料壕鹉。
Hash 表
在講HashMap之前剃幌，我們先來了解下他們底層實現(xiàn)的一種數(shù)據(jù)結(jié)構(gòu)——Hash 表聋涨。
Hash表，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)负乡。也就是說牍白，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度抖棘。存放記錄的數(shù)組叫做哈希表茂腥。
在HashMap中，就是將所給的“鍵”通過哈希函數(shù)得到“索引”钉答，然后把內(nèi)容存在數(shù)組中础芍，這樣就形成了“鍵”和內(nèi)容的映射關(guān)系。
上圖可以發(fā)現(xiàn)数尿，“鍵”轉(zhuǎn)換為“索引”的過程就是哈希函數(shù)仑性，為了盡可能保證每一個“鍵”通過哈希函數(shù)的轉(zhuǎn)換對應(yīng)不同的“索引”，就需要對哈希函數(shù)進(jìn)行選擇了右蹦，使其得到的“索引”分布越均勻越好诊杆。
哈希函數(shù)的均勻性：
通過前輩的研究加上實踐表明，當(dāng)把哈希函數(shù)得到hashcode值對素數(shù)取模時何陆，這樣得到的索引是最為均勻的晨汹。但是，在HashMap源碼中贷盲，并不是取模素數(shù)的淘这，而是一種等效取模2的n次方的位運算，hash&(length-1)巩剖。hash%length==hash&(length-1)的前提是length是2的n次方铝穷；之所以使用位運算替代取模，是因為位運算的效率更高佳魔，所以也就要求數(shù)組的長度必須是2的n次方（索引的分布也是很均勻的）曙聂。
哈希函數(shù)的一致性：
哈希函數(shù)的一致性原則是：當(dāng)兩個對象的equals相等，那么他們的hashcode一定相等鞠鲜。
這就要求我們在重寫了equals方法時宁脊，必須重寫hashcode方法。如果不重寫hashcode贤姆，則會使用Object的hashcode方法榆苞，該方法是以我們創(chuàng)建的對象的地址作為參數(shù)求hash的。所以霞捡，如果不重寫hashcode坐漏，兩個equals相等的對象會導(dǎo)致hashcode不同（因為不同的對象），這個是不允許的，因為違背了hash函數(shù)的一致性原則仙畦。
哈希沖突：
當(dāng)兩個不同的元素，通過哈希函數(shù)得到了同一個hashcode音婶，則會產(chǎn)生哈希沖突慨畸。HashMap的處理方式是，JDK8之前衣式，每一個位置對應(yīng)一個鏈表寸士，鏈?zhǔn)降拇娣殴_突的元素；JDK8開始碴卧，當(dāng)哈希沖突達(dá)到一定程度（8個）弱卡，每一個位置從鏈表轉(zhuǎn)換成紅黑樹。因為紅黑樹的時間復(fù)雜度是O(log n)的住册，效率優(yōu)于鏈表婶博。
哈希表小結(jié)：
哈希表，均攤復(fù)雜度是O(1)荧飞，因為第一步通過數(shù)組索引找到數(shù)組位置是O(1)凡人，然后到鏈表中查找元素的均攤復(fù)雜度是O(size/length)，size為元素個數(shù)叹阔，length為數(shù)組長度挠轴。由于Hash表的容量是動態(tài)擴容的，也就是說隨著size和length成正比的耳幢，即size/length是一個常數(shù)岸晦，于是也是O(1)的復(fù)雜度，即總的來說睛藻，均攤復(fù)雜度是O(1)启上。但是哈希表是沒有順序性的，即無法對元素進(jìn)行排序修档。
Java7 HashMap
HashMap 是最簡單的碧绞，一來我們非常熟悉，二來就是它不支持并發(fā)操作吱窝，所以源碼也非常簡單讥邻。
首先，我們用下面的這張圖來介紹下HashMap的結(jié)構(gòu)院峡。
大方向上兴使，HashMap里面是一個數(shù)組，然后每個數(shù)組中的每個元素是一個單向鏈表照激。
上圖中发魄，每個綠色的實體是嵌套類Entry的實例，Entry包含四個屬性：key,value,hash值和用于單向鏈表的next。
capacity：當(dāng)前數(shù)組容量励幼，始終保持2^n汰寓，可以擴容，擴容后的大小為當(dāng)前的2倍苹粟，默認(rèn)為16有滑。
loadFactor：負(fù)載因子，默認(rèn)為 0.75嵌削。
threshold：擴容的閾值毛好，等于 capatity * loadFactor。
put 過程分析
1苛秕、數(shù)組初始化：在第一個元素插入 HashMap 的時候做一次數(shù)組的初始化肌访，就是先確定初始的數(shù)組大小，并計算數(shù)組的擴容閾值艇劫。這里將數(shù)組保持在 2 的 n 次方的做法吼驶，java7 和 java8 的HashMap 和 ConcurrentHashMap 都有相應(yīng)的要求。
注意：new HashMap時港准，并未做數(shù)組初始化操作旨剥，而是簡單為loadFactor ，threshold賦值浅缸；同時為了保證將數(shù)組保持在 2 的 n 次方轨帜，會對 capacity的值進(jìn)行處理，取大于capacity且最近的2 的 n 次方值作為數(shù)組大小衩椒。
2蚌父、計算具體數(shù)組的下標(biāo)：使用 key的 hash值對數(shù)組長度進(jìn)行取模（源碼中是 hash & (length -1)，當(dāng)length是2^n 時毛萌，此時（length - 1） 的二進(jìn)制全是1苟弛，?hash & (length -1) 相當(dāng)于取 hash值的低 n位，?結(jié)果和 hash mod length一樣的）阁将。
3膏秫、找到數(shù)組下標(biāo)后，先進(jìn)行 key 判重（== || equals）做盅，如果沒有重復(fù)缤削，則將新值放入鏈表的表頭，如果有重復(fù)吹榴，直接用新值覆蓋舊值亭敢。
4、數(shù)組擴容：如果當(dāng)前size >= threshold图筹，那么就會觸發(fā)擴容帅刀；擴容就是用一個新的大數(shù)組替換原來的小數(shù)組让腹，并將原來數(shù)組中的值遷移到新的數(shù)組中。
既然對 key的判重依據(jù)是hash值和equals方法扣溺，故必須對key進(jìn)行重寫hashcode和equals方法骇窍，因為如果不重寫，將直接用Object的hashcode和equals方法锥余，而其必須是同一個對象才能滿足key相同像鸡。
hashcode方法的一般規(guī)定：如果兩個對象能夠equals相等，那么他們的hashcode必須相等哈恰。
所以，重寫了equals必須重寫hashcode志群。
get 過程分析
相對于put 過程着绷，get 過程是非常簡單的。
1锌云、根據(jù)key 計算 hash 值荠医。
2、找到相應(yīng)的數(shù)組下標(biāo)：hash & (length - 1)桑涎。
3彬向、遍歷該數(shù)組位置處的鏈表，直到找到相等（== || equals）的 key攻冷。
java7 ConcurrentHashMap
ConcurrentHashMap和 HashMap 思路是差不多的娃胆，但是因為它支持并發(fā)操作，所以要復(fù)雜一些等曼。
整個ConcurrentHashMap 由一個個 Segment 組成里烦，Segment 代表“部分” 或 “一段”的意思，所以很多地方都會將其描述為分段鎖禁谦。
簡單的理解胁黑，ConcurrentHashMap 是一個 Segment數(shù)組，Segment 通過繼承 ReentrantLock來進(jìn)行加鎖州泊，所以每次需要加鎖的操作鎖住的是一個 Segment丧蘸，這樣只要保證每個 Segment是線程安全的，也就實現(xiàn)了全局的線程安全性遥皂。
concurrencyLevel：并行級別力喷、并發(fā)數(shù)、Segment 數(shù)渴肉。默認(rèn)是16冗懦，也就是說 ConcurrentHashMap 有16個 Segment，所以理論上仇祭，最多同時支持16個線程并發(fā)寫披蕉。這個值可以在初始化的時候設(shè)置為其他值，但是一旦初始化以后，它就不可以擴容了没讲。
再具體到每個 Segment內(nèi)部眯娱，其實每個 Segment 很像之前介紹的 HashMap，不過它要保證線程安全爬凑，所以處理起來要麻煩些徙缴。
初始化
initialCapacity：初始容量，這個值指的是整個 ConcurrentHashMap的初始容量嘁信，實際操作的時候需要平均分給每個 Segment于样。
loadFactor：負(fù)載因子，之前我們說了潘靖，Segment 數(shù)組不可以擴容穿剖，所以這個負(fù)載因子是給每個 Segment 內(nèi)部使用的。
new ConcurrentHashMap()無參進(jìn)行初始化以后：
1卦溢、Segment 數(shù)組長度為16糊余，不可以擴容。
2单寂、Sement[i]的默認(rèn)大小為2贬芥，負(fù)載因子為0.75，得出初始閾值為1.5宣决，也就插入第一個元素不會觸發(fā)擴容蘸劈，插入第二個進(jìn)行一次擴容。
3尊沸、初始化了 Segment[0]昵时，其他位置還是null。
put 過程分析
第一層皮很簡單椒丧，根據(jù) hash值找到 Segment壹甥，之后就是 Segment 內(nèi)部的 put 操作了。
Segment 內(nèi)部是由 數(shù)組+鏈表 組成的壶熏。
初始化 Segment：ensureSement
ConcurrentHashMap 初始化的時候初始化了第一個分段 Segment[0]句柠，對于其他分段來說，在插入第一個值的時候進(jìn)行初始化棒假。并且初始化其他的 Segment[k]時溯职，需要當(dāng)前 Segment[0]處的數(shù)組長度和負(fù)載因子，故 Segment[0]需要在ConcurrentHashMap初始化的時候進(jìn)行初始化帽哑。
擴容：rehash
重復(fù)一下谜酒，Segment 數(shù)組不能擴容，擴容的是 單個Segment內(nèi)部數(shù)組 HashEntry[]妻枕，擴容后僻族，容量為原來的2倍粘驰。
觸發(fā)擴容的時機：put 的時候，如果判斷該值的插入會導(dǎo)致該 Segment內(nèi)部的元素個數(shù)超過閾值述么，那么先進(jìn)行擴容蝌数，再插值。該方法不需要考慮并發(fā)度秘，因為 put 操作顶伞，是持有獨占鎖的。?
get 過程分析
相對于 put 來說剑梳，get 真的不要太簡單唆貌。
1、計算 hash值垢乙，找到 Segment數(shù)組中的下標(biāo)挠锥。
2、再次根據(jù) hash 找到每個 Segment內(nèi)部的 HashEntry[]數(shù)組的下標(biāo)侨赡。
3、遍歷該數(shù)組位置處的鏈表粱侣，直到找到相等（== || equals）的 key羊壹。
get 是不需要加鎖的：原因是get方法是將共享變量（table）定義為volatile，讓被修飾的變量對多個線程可見(即其中一個線程對變量進(jìn)行了修改齐婴，會同步到主內(nèi)存油猫，其他線程也能獲取到最新值)，允許一寫多讀的操作柠偶。
Java8 HashMap
Java8 對 HashMap 進(jìn)行了一些修改情妖，最大的是不同就是利用了紅黑樹，所以其由 數(shù)組+鏈表+紅黑樹 組成诱担。
根據(jù) Java7 HashMap 的介紹毡证，我們知道，查找的時候蔫仙，根據(jù) hash 值我們能夠快速定位到數(shù)組的具體下標(biāo)料睛，但是之后的話，需要順著鏈表一個個比較下去才能找到我們需要的摇邦，時間復(fù)雜度取決于鏈表的長度恤煞，為O(N)。
為了降低這部分的開銷施籍，在Java8 中居扒，當(dāng)鏈表中的元素超過8個以后，會將鏈表轉(zhuǎn)換為紅黑樹丑慎，在這些位置進(jìn)行查找的時候可以降低時間復(fù)雜度為O(logN)喜喂。
Java7 中使用 Entry來代表每個 HashMap 中的數(shù)據(jù)節(jié)點瓤摧，Java8 中使用 Node，基本沒有區(qū)別夜惭，都是 key姻灶，value，hash和 next 這四個屬性诈茧，不過产喉， Node 只能用于鏈表的情況，紅黑樹需要使用 TreeNode敢会。
put 過程分析
和Java7 稍微有點不一樣的是曾沈，Java7 是先擴容后插入新值的，Java8 先插入值再擴容的鸥昏；Java7 （HashMap/ConcurrentHashMap） 是將數(shù)據(jù)插入到鏈表的表頭塞俱，而 Java8 是將數(shù)據(jù)插入到鏈表的最后面。
get 過程分析
1吏垮、計算 key 的 hash 值障涯，根據(jù) hash 值找到對應(yīng)數(shù)組下標(biāo)：hash & (length - 1)。
2膳汪、判斷數(shù)組該位置第一個節(jié)點是否剛好是我們要找的（判key）唯蝶，如果不是，走第三步遗嗽。
3粘我、判斷該元素類型是否是 TreeNode，如果是痹换，用紅黑樹的方法取數(shù)據(jù)征字，如果不是，走第四步娇豫。
4匙姜、遍歷鏈表，直到找到相等（== || equals）的 key冯痢。
Java8 ConcurrentHashMap
對于 ConcurrentHashMap搁料，Java8 也引入了紅黑樹。
結(jié)構(gòu)上和 Java8 的 HashMap 基本上一樣系羞，不過它要保證安全性郭计，所以源碼上確實要復(fù)雜一些。注意：Java8 的?ConcurrentHashMap不再使用 Segment 分段鎖來保證并發(fā)寫椒振，而是使用 CAS 操作來保證線程安全的昭伸。
初始化
這個初始化方法，通過提供初始容量澎迎，計算 sizeCtl庐杨，sizeCtl = [(1.5 * initialCapacity + 1选调，然后向上取最近的2的 n 次方)]。
put 過程分析
1灵份、獲取 key 的 hash值仁堪，找到數(shù)組下標(biāo)。
2填渠、如果數(shù)組為空弦聂，進(jìn)行數(shù)組初始化。
3氛什、判斷該數(shù)組第一個節(jié)點是否有數(shù)據(jù)莺葫，如果沒有數(shù)據(jù)，則使用CAS操作將這個新值插入枪眉，如果有數(shù)據(jù)捺檬，則進(jìn)入第四步。
4贸铜、對頭結(jié)點進(jìn)行加鎖(synchronized)堡纬，如果頭結(jié)點的 hash 值>=0，說明是鏈表蒿秦，遍歷鏈表烤镐，如果找到相等的key，則進(jìn)行覆蓋渤早，如果沒有找到相等的key，則將新值放到鏈表的最后面瘫俊；如果 hash 值 <0鹊杖，說明是紅黑樹，調(diào)用紅黑樹的插值方法插入新節(jié)點扛芽。
5骂蓖、插值完成之后，判斷鏈表元素是否達(dá)到臨界值（8）川尖，那么就會進(jìn)行紅黑樹轉(zhuǎn)換登下。注意：當(dāng)數(shù)組長度小于64時，即使達(dá)到臨界值也不會進(jìn)行紅黑樹轉(zhuǎn)換叮喳，而是進(jìn)行數(shù)組擴容（Java8 HashMap沒有此限制被芳，直接判斷臨界值即可）。
初始化數(shù)組：initTable
初始化方法中的并發(fā)問題是通過對 sizeCtl 進(jìn)行一個CAS 操作來控制的馍悟。
get 過程分析
1畔濒、計算 hash值
2、根據(jù) hash 值找到數(shù)組對應(yīng)的位置：hash & (n- 1)
3.根據(jù)該位置處頭節(jié)點的性質(zhì)進(jìn)行查找：
? ? 1）如果該位置為 null锣咒，那么直接返回 null 就可以了
? ? 2）如果該位置處的節(jié)點剛好就是我們需要的侵状，返回該節(jié)點的值即可
? ? 3）如果該位置節(jié)點的 hash 值小于 0赞弥，說明正在擴容，或者是紅黑樹趣兄，后面調(diào)用 find 接口绽左，程序會根據(jù)上下文執(zhí)行具體的方法。
? ? 4）如果以上 3 條都不滿足艇潭，那就是鏈表拼窥，進(jìn)行遍歷比對即可
總結(jié)
HashMap 是允許 key 或 value 為null值的，并且將其保存在數(shù)組第一個元素 table[0]上暴区；而 ConcurrentHashMap 和 HashTable 是不允許 key? 或 value 為 null 的闯团。因為?ConcurrentHashMap 和?HashTable 支持多并發(fā)場景，當(dāng) map.get(key) 時仙粱，得到的為 null 的 value房交，你不知道是它的值自身為 null，還是不存在該 key 而返回的 null伐割。HashMap 可以通過 containsKey(key) 來判斷是否存在指定 key候味，因為它的設(shè)計初衷是單線程的；但是ConcurrentHashMap 和?HashTable 卻不能通過?containsKey(key) 來判斷是否存在指定 key隔心，因為其在?containsKey(key) 時可能存在操作該 key 的其他操作(比如刪除該key)白群，于是索性他們不存 null 值了。
LinkedHashMap 是默認(rèn)根據(jù)元素增加的先后順序進(jìn)行排序硬霍，而 TreeMap(底層二叉樹) 則默認(rèn)根據(jù)元素的 Key 進(jìn)行自然排序(即從小到大)帜慢，也可以指定排序的比較器。
LinkedHashMap 的構(gòu)造方法也支持?accessOrder 參數(shù)唯卖，如果為 true粱玲，則表示采用最近最少使用算法（LRU）進(jìn)行排序。大致原理為：
put(key, value)拜轨，首先在 HashMap 找到 Key 對應(yīng)的節(jié)點抽减，如果節(jié)點存在，更新節(jié)點的值橄碾，并把這個節(jié)點移動隊尾卵沉。如果不存在，需要構(gòu)造新的節(jié)點法牲，并且嘗試把節(jié)點塞到隊尾史汗，如果 LRU 空間不足(HashMap 由于可以擴容，故不存在這種情況)拒垃，則通過淘汰掉隊首的節(jié)點淹办，同時在 HashMap 中移除 Key。
get(key)恶复，通過 HashMap 找到 LRU 鏈表節(jié)點怜森，因為根據(jù)LRU 原理速挑，這個節(jié)點是最新訪問的，所以要把節(jié)點插入到隊尾副硅，然后返回緩存的值姥宝。
HashTable：線程安全的，但是由于采用的是synchronized來保證線程安全恐疲，效率非常低腊满，因為當(dāng)一個線程訪問HashTable的同步方法時，其他線程訪問會進(jìn)入阻塞或輪詢的狀態(tài)培己。
二叉樹：二叉樹規(guī)定了在每個節(jié)點下最多只能擁有兩個子節(jié)點碳蛋，一左一右。
二叉查找樹：二叉查找樹的左子樹中任意節(jié)點的值都小于右子樹中任意節(jié)點的值省咨。
平衡二叉樹：又稱為AVL樹肃弟，它要求左右子樹的高度差的絕對值不能大于1，紅黑樹就是一種平衡二叉樹零蓉。
彩蛋
HashSet 的工作原理：
HashSet 的底層還是 HashMap:
對于 HashSet 而言笤受，它是基于 HashMap 實現(xiàn)的，HashSet 底層使用 HashMap 來保存所有元素敌蜂，因此 HashSet 的實現(xiàn)比較簡單箩兽，相關(guān) HashSet 的操作，基本上都是直接調(diào)用底層 HashMap 的相關(guān)方法來完成章喉，我們應(yīng)該為保存到 HashSet 中的對象覆蓋 hashCode() 和 equals()汗贫。
add 方法：
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
可知肋乍，HashSet 中的 value 都是 PRESENT棺弊，其是 Object 對象。當(dāng)元素 e 在 map 中不存在時昆箕，?map.put(e, PRESENT) 方法返回 null撞反，即 add 返回 true妥色；如果元素 e 在 map 中已經(jīng)存在搪花，map.put(e, PRESENT) 方法返回不為 null遏片，即 add 返回 false。從而保證了 set 中元素的不可重復(fù)性撮竿。
