1. 前言
- hashMap是JDK中的哈希表的容器的實(shí)現(xiàn)，它通過(guò)使用CPU計(jì)算替代遍歷尋址來(lái)提高數(shù)據(jù)搜索的速度。
- 這種結(jié)構(gòu)的時(shí)間復(fù)雜度通常是O(1)，也就是說(shuō)它不會(huì)隨著數(shù)據(jù)量的增加而降低他的遍歷速度，當(dāng)然這是指在沒(méi)有發(fā)生hash沖突的情況下。
2. 數(shù)據(jù)結(jié)構(gòu)
- 哈希表的實(shí)現(xiàn)有很多種，有純數(shù)組的實(shí)現(xiàn)，也有數(shù)組加鏈表的實(shí)現(xiàn)，還有數(shù)組加上額外內(nèi)存區(qū)域的實(shí)現(xiàn)，這些實(shí)現(xiàn)都各有各的好處，而JDK選擇了其中較為簡(jiǎn)單的一種實(shí)現(xiàn)，即數(shù)組加鏈表的實(shí)現(xiàn)方式。
- 更加精確點(diǎn)來(lái)說(shuō)，在JDK1.8之前的版本是數(shù)組加鏈表，而JDK1.9之后的版本是數(shù)組加紅黑樹的結(jié)構(gòu)
1.8的數(shù)據(jù)結(jié)構(gòu)
- JDK1.8添加的紅黑樹結(jié)構(gòu)的實(shí)現(xiàn)，主要是為了降低哈希沖突的帶來(lái)的影響。
3. 搜索數(shù)據(jù)
- 接下來(lái)說(shuō)一下Hashmap如何搜索數(shù)據(jù)，哈希表這種數(shù)據(jù)結(jié)構(gòu)最重要的便是它的哈希算法，哈希算法通過(guò)哈希key值，來(lái)為數(shù)據(jù)做索引，將數(shù)據(jù)導(dǎo)航到指定的存儲(chǔ)位置，并且不管怎么計(jì)算，數(shù)值都應(yīng)該是一樣的才能夠命中緩存。
3.1 哈希算法
3.1.1 哈希值的獲取
- HashMap使用的哈希值直接使用實(shí)例對(duì)象的hashcode()方法獲取的哈希值。
- 這個(gè)hashcode()方法的實(shí)現(xiàn)可以直接使用JDK默認(rèn)的實(shí)現(xiàn)，我們也可以通過(guò)重寫實(shí)現(xiàn)，其中JDK默認(rèn)的實(shí)現(xiàn)有部分邏輯是直接獲取的內(nèi)存地址，也有其他的實(shí)現(xiàn)，具體要看JDK的源碼怎么編寫。
3.1.2 與運(yùn)算替代求余運(yùn)算
- HashMap在獲取完實(shí)例對(duì)象的哈希值之后，不管是1.7還是1.8都會(huì)通過(guò)與（容量-1）的操作來(lái)定位數(shù)據(jù)的存儲(chǔ)位置。
- 這是因?yàn)镠ashMap為了提高哈希速度，它拋棄了求余的方式，選擇使用效率更高的與操作。
- 但是這種與操作有個(gè)限制便是需要容量是2的n次冪才行，所以一般我們創(chuàng)建HashMap的時(shí)候雖然指定了HashMap的容量，但是HashMap會(huì)自動(dòng)向上取到2的n次冪。
3.1.3 高位擾亂低位
- 接下來(lái)需要說(shuō)一下1.8的哈希算法的特殊處理，1.8在獲取到Hash值之后，首先會(huì)將前面一半的位數(shù)和后面一半的位數(shù)進(jìn)行異或操作，添加數(shù)據(jù)的擾亂程度，之后再讓讓高位的數(shù)據(jù)和低位的數(shù)據(jù)一同參與到運(yùn)算中，使哈希更加平均。
3.2 添加數(shù)據(jù)
- 接下來(lái)說(shuō)一下HashMap如何添加數(shù)據(jù)，哈希表的結(jié)構(gòu)為一個(gè)數(shù)組加鏈表，且一開始的時(shí)候是一個(gè)空數(shù)組，在第一次添加數(shù)據(jù)的時(shí)候會(huì)進(jìn)行resize()操作，而這一次resize操作主要是為了初始化數(shù)組，數(shù)組的大小為初始容量向上取整到2的大小。
3.2.1 添加數(shù)據(jù)
- 當(dāng)?shù)谝粋€(gè)數(shù)據(jù)添加的時(shí)候，數(shù)據(jù)首先通過(guò)哈希算法找到槽位，也就是數(shù)組上的對(duì)應(yīng)一個(gè)節(jié)點(diǎn)，然后鏈表節(jié)點(diǎn)的形式放到槽位上，其他數(shù)據(jù)也是一樣放置到對(duì)應(yīng)的槽點(diǎn)上。
3.2.2 哈希沖突
- 但是數(shù)據(jù)量無(wú)窮無(wú)盡，槽位卻是限定的，那么總會(huì)有兩個(gè)不同數(shù)據(jù)會(huì)哈希到同一個(gè)數(shù)值，此時(shí)兩個(gè)數(shù)據(jù)要使用同一個(gè)槽位的方式便叫做哈希沖突。
- 解決哈希沖突的方式有很多，像是如果發(fā)現(xiàn)沖突就往后挪動(dòng)一位槽為進(jìn)行存儲(chǔ)，或者劃定一塊特定的區(qū)域來(lái)存儲(chǔ)這些沖突數(shù)據(jù)。這些方案實(shí)現(xiàn)上都有其優(yōu)缺點(diǎn)。
- 而HashMap采用的是最簡(jiǎn)單的方式，即直接使用鏈表的方式將沖突的數(shù)據(jù)進(jìn)行串聯(lián)，形成一條鏈表，這樣當(dāng)搜索該槽位上的數(shù)據(jù)的時(shí)候，就會(huì)遍歷槽位上的鏈表，將數(shù)據(jù)搜索出來(lái)；
- 顯然這樣解決了哈希沖突，但是卻會(huì)出現(xiàn)另一個(gè)問(wèn)題，該槽位上的哈希沖突過(guò)多，對(duì)導(dǎo)致鏈表過(guò)長(zhǎng)，導(dǎo)致搜索速度變慢；
- 對(duì)于這種情況，hashMap提供了resize方案來(lái)解決這個(gè)問(wèn)題，同時(shí)在1.8的時(shí)候引入紅黑樹來(lái)解決問(wèn)題。
3.2.3 鏈表與紅黑樹
- 先說(shuō)一下1.8如果引入紅黑樹解決鏈表過(guò)長(zhǎng)的問(wèn)題。
- 鏈表之所以會(huì)導(dǎo)致搜索速度變慢，主要是因?yàn)槠鋽?shù)據(jù)結(jié)構(gòu)決定了他的遍歷速度只能是O(n)，所以通過(guò)引入紅黑樹的結(jié)構(gòu)，時(shí)間復(fù)雜度便能夠降低為O(log^n)，隨著鏈表的數(shù)據(jù)量和紅黑樹的數(shù)據(jù)量增大，兩者的遍歷速度將不斷拉大。
- JDK1.8中使用的是鏈表加紅黑樹，而不是紅黑樹替代鏈表的方案，主要是因?yàn)榧t黑樹的維護(hù)成本相對(duì)與鏈表是較高的，而生活中大多數(shù)的場(chǎng)景下，單個(gè)槽位上的沖突數(shù)并不會(huì)很多，紅黑樹的高效查詢特性并不能凸顯出來(lái)，因此一開始發(fā)生沖突的時(shí)候，仍然使用鏈表來(lái)處理哈希沖突問(wèn)題。
- 而當(dāng)槽位上的沖突數(shù)增加達(dá)到8的時(shí)候，HashMap便啟用鏈表轉(zhuǎn)換成紅黑樹的樹化邏輯。不過(guò)這有一個(gè)前提，便是HashMap的槽位數(shù)量大于64，否則HashMap傾向于通過(guò)resize來(lái)增加槽位，緩解哈希沖突問(wèn)題。
- 而當(dāng)槽位上的沖突樹減少達(dá)到6的時(shí)候，HashMap便啟用紅黑樹轉(zhuǎn)換成鏈表的鏈表化邏輯，為什么樹化和鏈表化的閾值不同主要是為了防止頻繁put和remove同一個(gè)值而導(dǎo)致頻繁的轉(zhuǎn)換，使HashMap的性能消耗在一些不必要的邏輯上，這相當(dāng)于一個(gè)緩沖帶的作用。
3.2.4 resize
- 接下來(lái)說(shuō)resize方案，我們知道HashMap會(huì)根據(jù)初始容量創(chuàng)建一定的槽位，而槽位的數(shù)量會(huì)影響到哈希沖突的概率，而resize便是通過(guò)增加槽位來(lái)降低哈希沖突的概率；
- 當(dāng)槽位鏈表上的沖突數(shù)達(dá)到8而數(shù)組容量還沒(méi)達(dá)到64，或HashMap上存儲(chǔ)的數(shù)據(jù)達(dá)到當(dāng)前的閾值0.75倍容量時(shí)，就會(huì)觸發(fā)resize操作；
- HashMap的resize方案是首先創(chuàng)建兩倍容量的數(shù)組，為什么是兩倍是因?yàn)楣Ｋ惴ㄒ呀?jīng)限定了只能是2的n次冪個(gè)槽位，不再贅述。
- 之后遍歷每個(gè)槽位上的鏈表，以尾插法的方式將鏈表插入到數(shù)組上，其中轉(zhuǎn)移的過(guò)程中直接將key與resize之后的容量，如果是0則槽位位置不變，如果是1則槽位的值添加resize一半容量的數(shù)值。
- 需要特別說(shuō)明的是，1.7使用的resize方案中，是用頭插法的方式插入到新的數(shù)組中，并且在線程沖突的情況下會(huì)發(fā)生鏈表死循環(huán)的情況。
- 不過(guò)hashMap本身就是線程不安全的容器，不管1.8還是1.7都是不允許在線程不安全的環(huán)境下使用的。
