Java 8中HashMap的底層原理解析
引言
HashMap
是Java中常用的集合類,用于存儲(chǔ)鍵值對(duì)。其底層實(shí)現(xiàn)經(jīng)過多次優(yōu)化,包括哈希算法、數(shù)組擴(kuò)容、鏈表轉(zhuǎn)紅黑樹等。本文將深入研究HashMap
的底層原理,并詳細(xì)探討如何解決哈希碰撞的技術(shù)。
1. 哈希算法
HashMap
的核心是哈希算法,它通過將鍵的哈希碼映射到數(shù)組索引,實(shí)現(xiàn)快速的數(shù)據(jù)查找和插入。在JDK 1.8中,哈希算法經(jīng)過了一些優(yōu)化,以提高均勻性和減少碰撞的可能性。
2. 數(shù)組與鏈表結(jié)構(gòu)
HashMap
的底層數(shù)據(jù)結(jié)構(gòu)是一個(gè)數(shù)組,每個(gè)數(shù)組元素是一個(gè)鏈表(或紅黑樹)。當(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è)鏈表上的元素哈希值相同。
紅黑樹:當(dāng)鏈表長度超過一定閾值(默認(rèn)為8)時(shí),鏈表會(huì)轉(zhuǎn)換為紅黑樹,可以減少查找時(shí)間。因?yàn)榧t黑樹的時(shí)間復(fù)雜度為O(logn),而鏈表為O(n)。
擴(kuò)容rehash:當(dāng)HashMap中的元素?cái)?shù)量太多,超過數(shù)組大小*加載因子時(shí),會(huì)發(fā)生擴(kuò)容。擴(kuò)容后,需要對(duì)原數(shù)組中的所有元素重新計(jì)算哈希值,然后放到新的擴(kuò)容后的數(shù)組中,這樣可以增加鏈表長度,減少哈希沖突。
優(yōu)化哈希算法:JDK 1.8中優(yōu)化了哈希算法,通過hashCode()的高16位異或低16位實(shí)現(xiàn)的:(h = k.hashCode()) ^ (h >>> 16),提高了哈希碰撞分布性。
所以Java 8中HashMap主要通過鏈地址法+紅黑樹+擴(kuò)容rehash+優(yōu)化哈希算法來解決哈希沖突。這些方法相結(jié)合可以有效地解決哈希沖突問題,提高HashMap的性能。
5. 數(shù)組擴(kuò)容機(jī)制
當(dāng)HashMap
中的元素?cái)?shù)量超過容量乘以加載因子時(shí),數(shù)組會(huì)被擴(kuò)容。在JDK 1.8中,默認(rèn)加載因子是0.75。擴(kuò)容涉及到重新計(jì)算哈希碼、重新分配數(shù)組,并將現(xiàn)有元素重新放置到新的數(shù)組中。這確保了HashMap
的性能和空間的平衡。
6. 紅黑樹的引入
為了應(yīng)對(duì)鏈表過長的情況,JDK 1.8引入了紅黑樹。當(dāng)鏈表長度達(dá)到8時(shí),鏈表將被轉(zhuǎn)換為紅黑樹,以提高查找效率。紅黑樹的引入使得在最壞情況下,查找時(shí)間復(fù)雜度從O(n)降低到O(log n)。
為什么當(dāng)鏈表長度達(dá)到8時(shí),鏈表將被轉(zhuǎn)換為紅黑樹,又為什么紅黑樹轉(zhuǎn)鏈表的閾值為6?
首先和hashcode碰撞次數(shù)的泊松分布有關(guān),主要是為了實(shí)現(xiàn)時(shí)間和空間的平衡,在負(fù)載因子為0.75默認(rèn)情況下,單個(gè)hash槽內(nèi)元素個(gè)數(shù)為8的概率小于百萬分之一,將7作為一個(gè)分水嶺,等于7時(shí)不做轉(zhuǎn)換,大于等于8才轉(zhuǎn)紅黑樹,小于等于6才轉(zhuǎn)鏈表,鏈表中元素個(gè)數(shù)為8時(shí)的概率已經(jīng)非常小,再多的就更少了,所以原作者在選擇鏈表元素個(gè)數(shù)時(shí)選擇了8,是根據(jù)概率統(tǒng)計(jì)而選擇的,紅黑樹中的TreeNode,是鏈表中的Node所占空間的2倍,雖然紅黑樹的查找效率為o(logN),要優(yōu)于鏈表的o(N),但是當(dāng)鏈表長度比較小的時(shí)候,即使全部遍歷,時(shí)間復(fù)雜度也不會(huì)太高,所以,要尋找一種時(shí)間和空間的平衡,即在鏈表長度達(dá)到一個(gè)閾值,之后再轉(zhuǎn)換為紅黑樹,之所以是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í)候說明由于元素,本身和hash函數(shù)的原因,此次操作的hash碰撞的可能性非常大了,后序可能還會(huì)繼續(xù)發(fā)生hash碰撞,所以,這個(gè)時(shí)候,就應(yīng)該將鏈表轉(zhuǎn)換為紅黑樹了,也就是為什么鏈表轉(zhuǎn)紅黑樹的閾值是8;
最后,紅黑樹轉(zhuǎn)鏈表的閾值為6,主要是因?yàn)椋喝绻矊⒃撻撝翟O(shè)置于8,那么當(dāng)hash碰撞在8時(shí),會(huì)反生鏈表和紅黑樹的不停相互激蕩轉(zhuǎn)換,白白浪費(fèi)資源。
7. 在Java 8中的實(shí)現(xiàn)細(xì)節(jié)
在JDK 1.8中,HashMap
的實(shí)現(xiàn)經(jīng)過了優(yōu)化,包括更好的哈希算法、紅黑樹的引入、鏈表長度的控制等。這些變化使得HashMap
在面對(duì)各種情況時(shí)都能提供高效的性能。
8. 性能優(yōu)化與注意事項(xiàng)
在使用HashMap
時(shí),需要注意一些性能優(yōu)化的問題,例如合理選擇初始容量和加載因子、避免頻繁擴(kuò)容等。對(duì)于特定的應(yīng)用場景,可以通過調(diào)整這些參數(shù)來達(dá)到更好的性能。
結(jié)論
HashMap
作為Java中常用的數(shù)據(jù)結(jié)構(gòu)之一,在JDK 1.8中經(jīng)過了一系列的優(yōu)化和改進(jìn)。深入理解其底層原理,包括哈希算法、數(shù)組與鏈表結(jié)構(gòu)、紅黑樹的引入等,以及如何解決哈希碰撞的技術(shù),有助于更好地使用和理解HashMap
的性能特性。在實(shí)際應(yīng)用中,根據(jù)具體場景選擇適當(dāng)?shù)膮?shù),可以更好地發(fā)揮HashMap
的優(yōu)勢,提高程序的性能和效率。
到此這篇關(guān)于Java 8中HashMap的底層原理的文章就介紹到這了,更多相關(guān)Java 8 HashMap原理內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
java實(shí)現(xiàn)單鏈表中是否有環(huán)的方法詳解
本篇文章介紹了,用java實(shí)現(xiàn)單鏈表中是否有環(huán)的方法詳解。需要的朋友參考下2013-05-05詳解如何通過Java實(shí)現(xiàn)壓縮PDF文檔
PDF文檔是我們?nèi)粘^k公中使用最頻繁的文檔格式。但因?yàn)榇蠖鄶?shù)PDF文檔都包含很多頁面圖像或大量圖片,這就導(dǎo)致PDF文檔過大,處理起來較為麻煩。本文將介紹如何通過Java應(yīng)用程序壓縮PDF文檔,需要的可以了解一下2022-12-12java集合框架 arrayblockingqueue應(yīng)用分析
ArrayBlockingQueue是一個(gè)由數(shù)組支持的有界阻塞隊(duì)列。此隊(duì)列按 FIFO(先進(jìn)先出)原則對(duì)元素進(jìn)行排序。隊(duì)列的頭部 是在隊(duì)列中存在時(shí)間最長的元素2012-11-11深入分析@Resource和@Autowired注解區(qū)別
這篇文章主要為大家介紹了深入分析@Resource和@Autowired注解區(qū)別,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-04-04springboot實(shí)現(xiàn)rabbitmq消息確認(rèn)的示例代碼
RabbitMQ的消息確認(rèn)有兩種, 一種是消息發(fā)送確認(rèn),第二種是消費(fèi)接收確認(rèn),本文主要介紹了springboot實(shí)現(xiàn)rabbitmq消息確認(rèn)的示例代碼,具有一定的參考價(jià)值,感興趣的可以了解一下2023-09-09SpringBoot 接口開發(fā)教程(httpclient客戶端)
這篇文章主要介紹了SpringBoot 接口開發(fā)教程(httpclient客戶端),具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-03-03Java數(shù)組優(yōu)點(diǎn)和缺點(diǎn)_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
本文給大家簡單介紹下java數(shù)組的優(yōu)點(diǎn)和缺點(diǎn)知識(shí),需要的的朋友參考下吧2017-04-04