文章單純記錄學(xué)習(xí)庭呜，答案不一定正確，大多從網(wǎng)上查閱犀忱，有錯誤望指正

一募谎、HashMap底層數(shù)據(jù)結(jié)構(gòu)以及擴容

HashMap的底層實現(xiàn)：JDK1.7是數(shù)組+鏈表；JDK1.8是數(shù)組+鏈表/紅黑樹

1. 擴容的條件：答：JDK1.7版：當(dāng)要添加新Entry對象時發(fā)現(xiàn)（1）size達(dá)到threshold（閾值）（2）table[index]!=null時阴汇，兩個條件同時滿足會擴容

JDK1.8版：當(dāng)要添加新Entry對象時發(fā)現(xiàn)（1）size達(dá)到threshold（閾值）（2）當(dāng)table[index]下的結(jié)點個數(shù)達(dá)到8個但是table.length又沒有達(dá)到64数冬。兩種情況滿足其一都會導(dǎo)致數(shù)組擴容

而且數(shù)組一旦擴容，不管哪個版本搀庶，都會導(dǎo)致所有映射關(guān)系重新調(diào)整存儲位置拐纱。

擴容：

2. put(key,value) -JDK1.7

（1）當(dāng)?shù)谝淮翁砑佑成潢P(guān)系時铜异，數(shù)組初始化為一個長度為16的HashMap$Entry的數(shù)組，這個HashMap$Entry類型是實現(xiàn)了java.util.Map.Entry接口

（2）特殊考慮：如果key為null秸架，index直接是[0]

（3）在計算index之前揍庄，會對key的hashCode()值，做一個hash(key)再次哈希的運算咕宿，這樣可以使得Entry對象更加散列的存儲到table中

（4）計算index = table.length-1 & hash;

（5）如果table[index]下面币绩，已經(jīng)有映射關(guān)系的key與我要添加的新的映射關(guān)系的key相同了，會用新的value替換舊的value府阀。

（6）如果沒有相同的缆镣，會把新的映射關(guān)系添加到鏈表的頭，原來table[index]下面的Entry對象連接到新的映射關(guān)系的next中试浙。

（7）添加之前先判斷if(size >= threshold? &&? table[index]!=null)如果該條件為true董瞻，會擴容

if(size >= threshold? &&? table[index]!=null){

①會擴容

②會重新計算key的hash

③會重新計算index

}

3.put(key,value) -JDK1.8

（1）當(dāng)?shù)谝淮翁砑佑成潢P(guān)系時，數(shù)組初始化為一個長度為16的HashMap$Node的數(shù)組田巴，這個HashMap$Node類型是實現(xiàn)了java.util. Map.Entry接口

（2）在計算index之前钠糊，會對key的hashCode()值，做一個hash(key)再次哈希的運算壹哺，這樣可以使得Entry對象更加散列的存儲到table中

> JDK1.8關(guān)于hash(key)方法的實現(xiàn)比JDK1.7要簡潔抄伍， key.hashCode() ^ key.Code()>>16;（異或其高16位）

（3）計算index = table.length-1 & hash;

（4）如果table[index]下面，已經(jīng)有映射關(guān)系的key與我要添加的新的映射關(guān)系的key相同了管宵，會用新的value替換舊的value截珍。

（5）如果沒有相同的，

①table[index]鏈表的長度沒有達(dá)到8個箩朴，會把新的映射關(guān)系添加到尾部

②table[index]鏈表的長度達(dá)到8個岗喉，但是table.length沒有達(dá)到64，會先對table進(jìn)行擴容炸庞，然后再添加

③table[index]鏈表的長度達(dá)到8個钱床，并且table.length達(dá)到64，會先把該分支進(jìn)行樹化埠居，結(jié)點的類型變?yōu)門reeNode查牌，然后把鏈表轉(zhuǎn)為一棵紅黑樹

④table[index]本來就已經(jīng)是紅黑樹了，那么直接連接到樹中滥壕，可能還會考慮考慮左旋右旋以保證樹的平衡問題

（6）添加完成后判斷if(size > threshold ){

①會擴容

②會重新計算key的hash

③會重新計算index

}

二僧免、HashMap的各種參數(shù)

閾值 = size（數(shù)組大小）* loadFactory（加載因子）

初始化大小size為16捏浊，加載因子為0.75,JDK1.8鏈表長度為8，數(shù)組長度大于等于64撞叨，進(jìn)行樹化

（1）1. HashMap的負(fù)載因子是多少金踪，為什么浊洞？

a) 0.75；

b) 因為定的太大胡岔，比如為1法希，就意味著數(shù)組的空位都需要填滿，如果一直等到數(shù)組填滿才擴容靶瘸，雖然達(dá)到了最大的數(shù)組空間利用率苫亦，但會產(chǎn)生大量的哈希碰撞，同時產(chǎn)生更多的鏈表怨咪，顯然不符合我們的要求屋剑；

c) 但如果設(shè)置的太小，比如0.3诗眨，這樣一來保證了數(shù)組空間很充足唉匾，減少了哈希碰撞，這種情況下查詢效率很高匠楚，但是消耗浪費了大量的空間巍膘。

d) 所以我們需要在時間和空間上做一個折中，選擇最合適的負(fù)載因子以保證最優(yōu)化芋簿，0.75峡懈。

2. HashMap的數(shù)組長度是2的指數(shù)次冪，為什么与斤。

i. 通過tableSizeFor()方法讓最高位1的后面全變?yōu)?肪康，在讓結(jié)果n+1，即得到了2的整數(shù)次冪幽告。

ii. 因為添加元素時索引的下標(biāo)可以通過取模運算獲得梅鹦，但是取模的效率低于乘法，所以要避免頻繁的取模運算冗锁。有因為在我們HashMap中他要通過取模去定位我們的索引齐唆，并且hashmap是在不斷的擴容的，數(shù)組一旦達(dá)到容量閾值時就需要進(jìn)行擴容冻河，那么擴容就意味著要進(jìn)行數(shù)組元素的移動箍邮，每一次移動都要重新計算索引，這個過程中牽扯大量的元素移動叨叙，就需要頻繁的取模運算锭弊，就會大大影響效率。

iii. 那么如果我們直接使用與運算擂错，這個效率就遠(yuǎn)高與取模運算味滞。利用與運算的就需要規(guī)定好數(shù)組的長度n，將n-1就會得到最高位為0，后面全1的二進(jìn)制數(shù)剑鞍，與任何數(shù)相與得到的范圍在0~n-1昨凡。

iv. 結(jié)論：首先使用與運算來加快計算的效率，而要使用與運算蚁署，就需要數(shù)組長度n-1與hash值保證其在數(shù)組范圍內(nèi)便脊，只有當(dāng)數(shù)組的長度為2的指數(shù)次冪時，其計算出來的值才能和取模算法的值相等光戈，并且保證能取到數(shù)組中的每一位哪痰，減少哈希碰撞，不浪費大量數(shù)組資源久妆。

3. 為什么鏈表長度大于8時轉(zhuǎn)成紅黑樹晌杰？

涉及泊松分布，以下是通過泊松分布計算出來的鏈表中元素個數(shù)和概率的對照表镇饺，鏈表中元素個數(shù)為8的概率非常小乎莉。

另外，紅黑樹平均查找長度是log(n),長度為8時奸笤，平均查找長度為3惋啃，如果繼續(xù)使用鏈表，平均查找長度為8/2=4监右，才有轉(zhuǎn)換為樹的必要边灭。

三、并發(fā)下HashMap安全嗎健盒？為什么绒瘦？

線程不安全，因為在多線程下扣癣，transfer方法將原table的值賦值給新的table惰帽，而transfer使用的是頭插法，也就是鏈表的順序會翻轉(zhuǎn)父虑，從而可能形成循環(huán)鏈表该酗。

解決方法 ： https://blog.csdn.net/javageektech/article/details/103724851

第一種方法，使用Hashtable線程安全類士嚎；

第二種方法呜魄，使用Collections.synchronizedMap方法，對方法進(jìn)行加同步鎖莱衩；

第三種方法爵嗅，使用并發(fā)包中的ConcurrentHashMap類；

前兩種方法都是通過給加全表鎖來保證安全笨蚁，在競爭激烈的多線程環(huán)境下性能非常差睹晒，所以不推薦使用趟庄！

，因為hashMap 是數(shù)組 + 鏈表的數(shù)據(jù)結(jié)構(gòu)册招，如果我們把數(shù)組進(jìn)行分割多段岔激，對每一段分別設(shè)計一把同步鎖，這樣在多線程訪問不同段的數(shù)據(jù)時是掰，就不會存在鎖競爭了，這樣是不是可以有效的提高性能辱匿？

四键痛、ConcurrentHashMap底層實現(xiàn)及其安全機制

好文：https://blog.csdn.net/javageektech/article/details/103724851

Jdk1.7實現(xiàn)方式：ConcurrentHashMap類所采用的正是分段鎖的思想，將HashMap 進(jìn)行切割匾七，把HashMap 中的哈希數(shù)組切分成小數(shù)組絮短，每個小數(shù)組有n 個HashEntry 組成，其中小數(shù)組繼承自ReentrantLock（可重入鎖）昨忆，這個小數(shù)組名叫Segment丁频。

Jdk1.8實現(xiàn)方式：JDK1.8中 ConcurrentHashMap 類取消了Segment 分段鎖，采用CAS+synchronized來保證并發(fā)安全邑贴，數(shù)據(jù)結(jié)構(gòu)跟 jdk1.8 中 HashMap 結(jié)構(gòu)類似席里，都是數(shù)組 + 鏈表（當(dāng)鏈表長度大于 8 時，鏈表結(jié)構(gòu)轉(zhuǎn)為紅黑二叉樹）結(jié)構(gòu)拢驾。

ConcurrentHashMap 中synchronized 只鎖定當(dāng)前鏈表或紅黑二叉樹的首節(jié)點奖磁，只要節(jié)點 hash 不沖突，就不會產(chǎn)生并發(fā)繁疤，相比 JDK1.7 的 ConcurrentHashMap 效率又提升了 N 倍咖为！

一、Jdk1.7源碼分析：

1稠腊、 HashEntry和HashMap中的 Entry非常類似躁染，唯一的區(qū)別就是其中的核心數(shù)據(jù)如value ，以及next都使用了volatile關(guān)鍵字修飾架忌，保證了多線程環(huán)境下數(shù)據(jù)獲取時的可見性吞彤！

2、 Segment 這個靜態(tài)內(nèi)部類繼承了ReentrantLock類鳖昌，ReentrantLock是一個可重入鎖备畦。

3、 理論上 ConcurrentHashMap 支持 concurrentLevel（通過 Segment 數(shù)組長度計算得來许昨，默認(rèn)為16） 個線程并發(fā)操作懂盐，每當(dāng)一個線程獨占一把鎖訪問 Segment 時，不會影響到其他的 Segment 操作糕档，效率大大提升莉恼！

4拌喉、 Put方法的流程：

第一步，嘗試獲取對象鎖俐银，如果獲取到返回 true尿背，否則執(zhí)行scanAndLockForPut方法，這個方法也是嘗試獲取對象鎖捶惜；

第二步田藐，獲取到鎖之后，類似 hashMap 的 put 方法吱七，通過 key 計算所在 HashEntry 數(shù)組的下標(biāo)汽久；

第三步，獲取到數(shù)組下標(biāo)之后遍歷鏈表內(nèi)容踊餐，通過 key 和 hash 值判斷是否 key 已存在景醇，如果已經(jīng)存在，通過標(biāo)識符判斷是否覆蓋吝岭，默認(rèn)覆蓋三痰；

第四步，如果不存在窜管，采用頭插法插入到 HashEntry 對象中散劫；

第五步，最后操作完整之后微峰，釋放對象鎖舷丹；

上述提到的scanAndLockForPut方法，操作也是分以下幾步：

? 當(dāng)前線程嘗試去獲得鎖蜓肆，查找 key 是否已經(jīng)存在颜凯，如果不存在，就創(chuàng)建一個 HashEntry 對象仗扬；

? 如果重試次數(shù)大于最大次數(shù)症概，就調(diào)用lock()方法獲取對象鎖，如果依然沒有獲取到早芭，當(dāng)前線程就阻塞彼城，直到獲取之后退出循環(huán)；

? 在這個過程中退个，key 可能被別的線程給插入募壕，所以在第 5 步中，如果 HashEntry 存儲內(nèi)容發(fā)生變化语盈，重置重試次數(shù)舱馅；

通過scanAndLockForPut()方法，當(dāng)前線程就可以在即使獲取不到segment鎖的情況下刀荒，完成需要添加節(jié)點的實例化工作代嗤，當(dāng)獲取鎖后棘钞，就可以直接將該節(jié)點插入鏈表即可。

這個方法還實現(xiàn)了類似于自旋鎖的功能干毅，循環(huán)式的判斷對象鎖是否能夠被成功獲取宜猜，直到獲取到鎖才會退出循環(huán)，防止執(zhí)行 put 操作的線程頻繁阻塞硝逢，這些優(yōu)化都提升了 put 操作的性能姨拥。

5、 remove方法：

1) 先獲取對象鎖趴捅；

2) 計算 key 的 hash 值在 HashEntry[]中的角標(biāo)垫毙；

3) 根據(jù) index 角標(biāo)獲取 HashEntry 對象；

4) 循環(huán)遍歷 HashEntry 對象拱绑，HashEntry 為單向鏈表結(jié)構(gòu)；

5) 通過 key 和 hash 判斷 key 是否存在丽蝎，如果存在猎拨，就移除元素，并將需要移除的元素節(jié)點的下一個屠阻，向上移红省；

6) 最后就是釋放對象鎖，以便其他線程使用国觉；

二吧恃、 jdk1.8源碼分析

1、 JDK1.8 中的 ConcurrentHashMap 對節(jié)點Node類中的共享變量麻诀，和 JDK1.7 一樣痕寓，使用volatile關(guān)鍵字，保證多線程操作時蝇闭，變量的可見行呻率！

2、 Put方法流程：

? 首先會判斷 key呻引、value 是否為空礼仗，如果為空就拋異常！

? 接著會判斷容器數(shù)組是否為空逻悠，如果為空就初始化數(shù)組元践；

? 進(jìn)一步判斷，要插入的元素f童谒，在當(dāng)前數(shù)組下標(biāo)是否第一次插入单旁，如果是就通過 CAS 方式插入；

? 在接著判斷f.hash == -1是否成立惠啄，如果成立慎恒，說明當(dāng)前f是ForwardingNode節(jié)點任内，表示有其它線程正在擴容，則一起進(jìn)行擴容操作融柬；

? 獲得該位置下的鎖死嗦，把新的Node節(jié)點按鏈表或紅黑樹的方式插入到合適的位置；

? 節(jié)點插入完成之后粒氧，接著判斷鏈表長度是否超過8越除，如果超過8個，就將鏈表轉(zhuǎn)化為紅黑樹結(jié)構(gòu)外盯；

? 最后摘盆，插入完成之后，進(jìn)行擴容判斷饱苟；

3孩擂、 initTable 初始化數(shù)組，當(dāng)?shù)谝淮尾迦霑r箱熬，內(nèi)部容器數(shù)組為空类垦，該方法進(jìn)行初始化

其中sizeCtl 是一個對象屬性，使用了 volatile 關(guān)鍵字修飾保證并發(fā)的可見性城须，默認(rèn)為 0蚤认，當(dāng)?shù)谝淮螆?zhí)行 put 操作時，通過Unsafe.compareAndSwapInt()方法糕伐，俗稱CAS砰琢，將 修改為 -1，有且只有一個線程能夠修改成功良瞧，接著執(zhí)行 table 初始化任務(wù)陪汽。

如果別的線程發(fā)現(xiàn)sizeCtl<0，意味著有另外的線程執(zhí)行 CAS 操作成功莺褒，當(dāng)前線程通過執(zhí)行Thread.yield()讓出 CPU 時間片等待 table 初始化完成掩缓。

4、 helpTransfer 幫組擴容遵岩，當(dāng)f.hash =-1時你辣，說明當(dāng)前f是一個forwardingNode節(jié)點，意味著其他線程正在擴容尘执，則一起進(jìn)行擴容操作舍哄。

這個過程，操作步驟如下：

? 第 1 步誊锭，對 table表悬、node 節(jié)點、node 節(jié)點的 nextTable（新table）進(jìn)行數(shù)據(jù)校驗丧靡；

? 第 2 步蟆沫，根據(jù)數(shù)組的 length 得到一個標(biāo)識符號籽暇；

? 第 3 步，進(jìn)一步校驗 nextTab饭庞、tab戒悠、sizeCtl 值，如果 nextTab 沒有被并發(fā)修改并且 tab 也沒有被并發(fā)修改舟山，同時 sizeCtl < 0绸狐，說明還在擴容；

? 第 4 步累盗，對 sizeCtl 參數(shù)值進(jìn)行分析判斷寒矿，如果不滿足任何一個判斷，將sizeCtl + 1, 增加了一個線程幫助其擴容;

5若债、 addCount擴容判斷

這個過程符相，操作步驟如下：

? 第 1 步，利用 CAS 將方法更新 baseCount 的值

? 第 2 步蠢琳，檢查是否需要擴容主巍，默認(rèn) check = 1，需要檢查挪凑；

? 第 3 步，如果滿足擴容條件逛艰，判斷當(dāng)前是否正在擴容躏碳，如果是正在擴容就一起擴容；

? 第 4 步散怖，如果不在擴容菇绵，將 sizeCtl 更新為負(fù)數(shù)，并進(jìn)行擴容處理镇眷；

總結(jié)：

為解決HashMap在多線程環(huán)境下操作不安全的問題咬最，java為我們提供了ConcurrentHashMap類，保證了多線程下hashMap操作安全欠动。

在jdk1.7中永乌，ConcurrentHashMap采用了分段鎖策略，將一個HashMap切割成Segment數(shù)組具伍，而Segment存儲n個HashEntry,類似HashMap翅雏，不同的是Segment繼承自ReetrantLock(可重入鎖)，在操作的時候給Segment賦予一個對象鎖人芽，從而保證了多線程環(huán)境下并發(fā)操作安全望几。

但是jdk1.7中，hashMap容易因為沖突鏈表長度過長萤厅，導(dǎo)致查詢效率低橄抹。

在jdk1.8中靴迫，ConcurrentHashMap采用了jdk1.8中HashMap類似的存儲結(jié)構(gòu)（數(shù)組+鏈表/紅黑樹），但ConcurrentHashMap并沒有采用分段鎖的策略楼誓，而是在元素的節(jié)點上采用CAS+synchronized操作來保證并發(fā)的安全性玉锌。

五、?TreeMap和HashMap的區(qū)別

1慌随、 HashMap中元素是無序的芬沉；TreeMap中所有元素都是有某一固定順序的

2、 HashMap繼承AbstractMap類阁猜，是基于hash表實現(xiàn)的丸逸；而TreeMap繼承SortedMap類，是基于紅黑樹實現(xiàn)的剃袍。

3黄刚、 兩者都是線程不安全的

4、 HashMap適用于Map插入民效、刪除憔维、定位元素；TreeMap適用于自然順序或自定義順序遍歷鍵畏邢。

六业扒、HashMap與Hashtable的區(qū)別

1皿曲、hashtable是線程安全的,即hashtable的方法都提供了同步機制秀睛，底層加了synchronized關(guān)鍵字；hashmap不是線程安全的,即不提供同步機制?

2辽剧、hashtable不允許插入空值,hashmap允許!

3臂寝、HashMap繼承了AbstractMap章鲤，HashTable繼承Dictionary抽象類，兩者均實現(xiàn)Map接口咆贬。

4败徊、HashMap的初始容量為16，Hashtable初始容量為11掏缎，兩者的填充因子默認(rèn)都是0.75皱蹦。

5、HashMap擴容時是當(dāng)前容量翻倍即:capacity*2御毅，Hashtable擴容時是容量翻倍+1即:capacity*2+1根欧。

6、HashMap和Hashtable的底層實現(xiàn)都是數(shù)組+鏈表結(jié)構(gòu)實現(xiàn)端蛆。

7凤粗、兩者計算hash的方法不同：

Hashtable計算hash是直接使用key的hashcode對table數(shù)組的長度直接進(jìn)行取模：