引言

HashMap是Java中常用的集合類，用于存儲鍵值對。其底層實現(xiàn)經(jīng)過多次優(yōu)化，包括哈希算法、數(shù)組擴容、鏈表轉(zhuǎn)紅黑樹等。本文將深入研究HashMap的底層原理，并詳細(xì)探討如何解決哈希碰撞的技術(shù)。

1. 哈希算法

HashMap的核心是哈希算法，它通過將鍵的哈希碼映射到數(shù)組索引，實現(xiàn)快速的數(shù)據(jù)查找和插入。在JDK 1.8中，哈希算法經(jīng)過了一些優(yōu)化，以提高均勻性和減少碰撞的可能性。

2. 數(shù)組與鏈表結(jié)構(gòu)

HashMap的底層數(shù)據(jù)結(jié)構(gòu)是一個數(shù)組，每個數(shù)組元素是一個鏈表（或紅黑樹）。當(dāng)多個鍵映射到相同的索引位置時，它們將被存儲在同一個鏈表中。為了解決哈希碰撞，鏈表中存儲的是一個個鍵值對。

3. 鍵值對的存儲

在HashMap中，鍵值對以Node對象的形式存儲。每個Node包含鍵、值、哈希碼以及指向下一個Node的引用。當(dāng)產(chǎn)生哈希沖突時，新的Node將被添加到鏈表的末尾。

4. 解決哈希碰撞的方法

鏈地址法:當(dāng)發(fā)生哈希沖突時,將沖突的元素以鏈表的形式鏈接在一起,同一個鏈表上的元素哈希值相同。

紅黑樹:當(dāng)鏈表長度超過一定閾值(默認(rèn)為8)時,鏈表會轉(zhuǎn)換為紅黑樹,可以減少查找時間。因為紅黑樹的時間復(fù)雜度為O(logn),而鏈表為O(n)。

擴容rehash:當(dāng)HashMap中的元素數(shù)量太多,超過數(shù)組大小*加載因子時,會發(fā)生擴容。擴容后,需要對原數(shù)組中的所有元素重新計算哈希值,然后放到新的擴容后的數(shù)組中,這樣可以增加鏈表長度,減少哈希沖突。

優(yōu)化哈希算法:JDK 1.8中優(yōu)化了哈希算法,通過hashCode()的高16位異或低16位實現(xiàn)的:(h = k.hashCode()) ^ (h >>> 16),提高了哈希碰撞分布性。

所以Java 8中HashMap主要通過鏈地址法+紅黑樹+擴容rehash+優(yōu)化哈希算法來解決哈希沖突。這些方法相結(jié)合可以有效地解決哈希沖突問題,提高HashMap的性能。

5. 數(shù)組擴容機制

當(dāng)HashMap中的元素數(shù)量超過容量乘以加載因子時，數(shù)組會被擴容。在JDK 1.8中，默認(rèn)加載因子是0.75。擴容涉及到重新計算哈希碼、重新分配數(shù)組，并將現(xiàn)有元素重新放置到新的數(shù)組中。這確保了HashMap的性能和空間的平衡。

6. 紅黑樹的引入

為了應(yīng)對鏈表過長的情況，JDK 1.8引入了紅黑樹。當(dāng)鏈表長度達到8時，鏈表將被轉(zhuǎn)換為紅黑樹，以提高查找效率。紅黑樹的引入使得在最壞情況下，查找時間復(fù)雜度從O(n)降低到O(log n)。

為什么當(dāng)鏈表長度達到8時，鏈表將被轉(zhuǎn)換為紅黑樹，又為什么紅黑樹轉(zhuǎn)鏈表的閾值為6？
首先和hashcode碰撞次數(shù)的泊松分布有關(guān),主要是為了實現(xiàn)時間和空間的平衡，在負(fù)載因子為0.75默認(rèn)情況下，單個hash槽內(nèi)元素個數(shù)為8的概率小于百萬分之一，將7作為一個分水嶺，等于7時不做轉(zhuǎn)換，大于等于8才轉(zhuǎn)紅黑樹，小于等于6才轉(zhuǎn)鏈表，鏈表中元素個數(shù)為8時的概率已經(jīng)非常小，再多的就更少了，所以原作者在選擇鏈表元素個數(shù)時選擇了8，是根據(jù)概率統(tǒng)計而選擇的，紅黑樹中的TreeNode，是鏈表中的Node所占空間的2倍，雖然紅黑樹的查找效率為o(logN)，要優(yōu)于鏈表的o(N)，但是當(dāng)鏈表長度比較小的時候，即使全部遍歷，時間復(fù)雜度也不會太高，所以，要尋找一種時間和空間的平衡，即在鏈表長度達到一個閾值，之后再轉(zhuǎn)換為紅黑樹，之所以是8，是因為Java的源碼貢獻者，在進行大量實驗發(fā)現(xiàn)，hash碰撞發(fā)生8次的概率，已經(jīng)降低到了0.00000006，幾乎為不可能事件，如果真的碰撞發(fā)生了8次，那么這個時候說明由于元素，本身和hash函數(shù)的原因，此次操作的hash碰撞的可能性非常大了，后序可能還會繼續(xù)發(fā)生hash碰撞，所以，這個時候，就應(yīng)該將鏈表轉(zhuǎn)換為紅黑樹了，也就是為什么鏈表轉(zhuǎn)紅黑樹的閾值是8；
最后，紅黑樹轉(zhuǎn)鏈表的閾值為6，主要是因為：如果也將該閾值設(shè)置于8，那么當(dāng)hash碰撞在8時，會反生鏈表和紅黑樹的不停相互激蕩轉(zhuǎn)換，白白浪費資源。

7. 在Java 8中的實現(xiàn)細(xì)節(jié)

在JDK 1.8中，HashMap的實現(xiàn)經(jīng)過了優(yōu)化，包括更好的哈希算法、紅黑樹的引入、鏈表長度的控制等。這些變化使得HashMap在面對各種情況時都能提供高效的性能。

8. 性能優(yōu)化與注意事項

在使用HashMap時，需要注意一些性能優(yōu)化的問題，例如合理選擇初始容量和加載因子、避免頻繁擴容等。對于特定的應(yīng)用場景，可以通過調(diào)整這些參數(shù)來達到更好的性能。

結(jié)論

HashMap作為Java中常用的數(shù)據(jù)結(jié)構(gòu)之一，在JDK 1.8中經(jīng)過了一系列的優(yōu)化和改進。深入理解其底層原理，包括哈希算法、數(shù)組與鏈表結(jié)構(gòu)、紅黑樹的引入等，以及如何解決哈希碰撞的技術(shù)，有助于更好地使用和理解HashMap的性能特性。在實際應(yīng)用中，根據(jù)具體場景選擇適當(dāng)?shù)膮?shù)，可以更好地發(fā)揮HashMap的優(yōu)勢，提高程序的性能和效率。

到此這篇關(guān)于Java 8中HashMap的底層原理的文章就介紹到這了,更多相關(guān)Java 8 HashMap原理內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論