引言

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

1. 哈希算法

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

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

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

3. 鍵值對(duì)的存儲(chǔ)

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

4. 解決哈希碰撞的方法

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

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

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

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

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

5. 數(shù)組擴(kuò)容機(jī)制

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

6. 紅黑樹(shù)的引入

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

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

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

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

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

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

結(jié)論

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

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

最新評(píng)論