1. 前言

• hashMap是JDK中的哈希表的容器的實現(xiàn)，它通過使用CPU計算替代遍歷尋址來提高數(shù)據(jù)搜索的速度答姥。
• 這種結(jié)構(gòu)的時間復(fù)雜度通常是O(1)铣除，也就是說它不會隨著數(shù)據(jù)量的增加而降低他的遍歷速度，當(dāng)然這是指在沒有發(fā)生hash沖突的情況下鹦付。

2. 數(shù)據(jù)結(jié)構(gòu)

• 哈希表的實現(xiàn)有很多種尚粘，有純數(shù)組的實現(xiàn)，也有數(shù)組加鏈表的實現(xiàn)敲长，還有數(shù)組加上額外內(nèi)存區(qū)域的實現(xiàn)郎嫁，這些實現(xiàn)都各有各的好處，而JDK選擇了其中較為簡單的一種實現(xiàn)祈噪，即數(shù)組加鏈表的實現(xiàn)方式泽铛。
• 更加精確點來說，在JDK1.8之前的版本是數(shù)組加鏈表辑鲤，而JDK1.9之后的版本是數(shù)組加紅黑樹的結(jié)構(gòu)

1.8的數(shù)據(jù)結(jié)構(gòu)

• JDK1.8添加的紅黑樹結(jié)構(gòu)的實現(xiàn)盔腔，主要是為了降低哈希沖突的帶來的影響。

3. 搜索數(shù)據(jù)

• 接下來說一下Hashmap如何搜索數(shù)據(jù)月褥，哈希表這種數(shù)據(jù)結(jié)構(gòu)最重要的便是它的哈希算法弛随，哈希算法通過哈希key值，來為數(shù)據(jù)做索引宁赤，將數(shù)據(jù)導(dǎo)航到指定的存儲位置舀透，并且不管怎么計算，數(shù)值都應(yīng)該是一樣的才能夠命中緩存决左。

3.1 哈希算法

3.1.1 哈希值的獲取

• HashMap使用的哈希值直接使用實例對象的hashcode()方法獲取的哈希值愕够。
• 這個hashcode()方法的實現(xiàn)可以直接使用JDK默認(rèn)的實現(xiàn)，我們也可以通過重寫實現(xiàn)佛猛，其中JDK默認(rèn)的實現(xiàn)有部分邏輯是直接獲取的內(nèi)存地址惑芭，也有其他的實現(xiàn)，具體要看JDK的源碼怎么編寫继找。

3.1.2 與運算替代求余運算

• HashMap在獲取完實例對象的哈希值之后强衡，不管是1.7還是1.8都會通過與（容量-1）的操作來定位數(shù)據(jù)的存儲位置。
• 這是因為HashMap為了提高哈希速度，它拋棄了求余的方式漩勤，選擇使用效率更高的與操作。
• 但是這種與操作有個限制便是需要容量是2的n次冪才行缩搅，所以一般我們創(chuàng)建HashMap的時候雖然指定了HashMap的容量越败，但是HashMap會自動向上取到2的n次冪。

3.1.3 高位擾亂低位

• 接下來需要說一下1.8的哈希算法的特殊處理硼瓣，1.8在獲取到Hash值之后究飞，首先會將前面一半的位數(shù)和后面一半的位數(shù)進行異或操作，添加數(shù)據(jù)的擾亂程度堂鲤，之后再讓讓高位的數(shù)據(jù)和低位的數(shù)據(jù)一同參與到運算中亿傅，使哈希更加平均。

3.2 添加數(shù)據(jù)

• 接下來說一下HashMap如何添加數(shù)據(jù)瘟栖，哈希表的結(jié)構(gòu)為一個數(shù)組加鏈表葵擎，且一開始的時候是一個空數(shù)組，在第一次添加數(shù)據(jù)的時候會進行resize()操作半哟，而這一次resize操作主要是為了初始化數(shù)組酬滤，數(shù)組的大小為初始容量向上取整到2的大小。

3.2.1 添加數(shù)據(jù)

• 當(dāng)?shù)谝粋€數(shù)據(jù)添加的時候寓涨，數(shù)據(jù)首先通過哈希算法找到槽位盯串，也就是數(shù)組上的對應(yīng)一個節(jié)點，然后鏈表節(jié)點的形式放到槽位上戒良，其他數(shù)據(jù)也是一樣放置到對應(yīng)的槽點上体捏。

3.2.2 哈希沖突

• 但是數(shù)據(jù)量無窮無盡，槽位卻是限定的糯崎，那么總會有兩個不同數(shù)據(jù)會哈希到同一個數(shù)值几缭，此時兩個數(shù)據(jù)要使用同一個槽位的方式便叫做哈希沖突。
• 解決哈希沖突的方式有很多拇颅，像是如果發(fā)現(xiàn)沖突就往后挪動一位槽為進行存儲奏司，或者劃定一塊特定的區(qū)域來存儲這些沖突數(shù)據(jù)。這些方案實現(xiàn)上都有其優(yōu)缺點樟插。
• 而HashMap采用的是最簡單的方式韵洋，即直接使用鏈表的方式將沖突的數(shù)據(jù)進行串聯(lián)，形成一條鏈表黄锤，這樣當(dāng)搜索該槽位上的數(shù)據(jù)的時候搪缨，就會遍歷槽位上的鏈表，將數(shù)據(jù)搜索出來鸵熟；
• 顯然這樣解決了哈希沖突副编，但是卻會出現(xiàn)另一個問題，該槽位上的哈希沖突過多流强，對導(dǎo)致鏈表過長痹届，導(dǎo)致搜索速度變慢呻待；
• 對于這種情況，hashMap提供了resize方案來解決這個問題，同時在1.8的時候引入紅黑樹來解決問題。

3.2.3 鏈表與紅黑樹

• 先說一下1.8如果引入紅黑樹解決鏈表過長的問題贝乎。
• 鏈表之所以會導(dǎo)致搜索速度變慢，主要是因為其數(shù)據(jù)結(jié)構(gòu)決定了他的遍歷速度只能是O(n)迫淹，所以通過引入紅黑樹的結(jié)構(gòu)，時間復(fù)雜度便能夠降低為O(log^n)为严，隨著鏈表的數(shù)據(jù)量和紅黑樹的數(shù)據(jù)量增大敛熬，兩者的遍歷速度將不斷拉大。
• JDK1.8中使用的是鏈表加紅黑樹第股，而不是紅黑樹替代鏈表的方案应民，主要是因為紅黑樹的維護成本相對與鏈表是較高的，而生活中大多數(shù)的場景下炸茧，單個槽位上的沖突數(shù)并不會很多瑞妇，紅黑樹的高效查詢特性并不能凸顯出來，因此一開始發(fā)生沖突的時候梭冠，仍然使用鏈表來處理哈希沖突問題辕狰。
• 而當(dāng)槽位上的沖突數(shù)增加達到8的時候，HashMap便啟用鏈表轉(zhuǎn)換成紅黑樹的樹化邏輯控漠。不過這有一個前提蔓倍，便是HashMap的槽位數(shù)量大于64，否則HashMap傾向于通過resize來增加槽位盐捷，緩解哈希沖突問題偶翅。
• 而當(dāng)槽位上的沖突樹減少達到6的時候，HashMap便啟用紅黑樹轉(zhuǎn)換成鏈表的鏈表化邏輯碉渡，為什么樹化和鏈表化的閾值不同主要是為了防止頻繁put和remove同一個值而導(dǎo)致頻繁的轉(zhuǎn)換聚谁，使HashMap的性能消耗在一些不必要的邏輯上，這相當(dāng)于一個緩沖帶的作用滞诺。

3.2.4 resize

• 接下來說resize方案形导，我們知道HashMap會根據(jù)初始容量創(chuàng)建一定的槽位，而槽位的數(shù)量會影響到哈希沖突的概率习霹，而resize便是通過增加槽位來降低哈希沖突的概率朵耕；
• 當(dāng)槽位鏈表上的沖突數(shù)達到8而數(shù)組容量還沒達到64，或HashMap上存儲的數(shù)據(jù)達到當(dāng)前的閾值0.75倍容量時淋叶，就會觸發(fā)resize操作阎曹；
• HashMap的resize方案是首先創(chuàng)建兩倍容量的數(shù)組，為什么是兩倍是因為哈希算法已經(jīng)限定了只能是2的n次冪個槽位，不再贅述处嫌。
• 之后遍歷每個槽位上的鏈表栅贴，以尾插法的方式將鏈表插入到數(shù)組上，其中轉(zhuǎn)移的過程中直接將key與resize之后的容量锰霜，如果是0則槽位位置不變筹误，如果是1則槽位的值添加resize一半容量的數(shù)值。
• 需要特別說明的是癣缅，1.7使用的resize方案中，是用頭插法的方式插入到新的數(shù)組中哄酝，并且在線程沖突的情況下會發(fā)生鏈表死循環(huán)的情況友存。
• 不過hashMap本身就是線程不安全的容器，不管1.8還是1.7都是不允許在線程不安全的環(huán)境下使用的陶衅。