首頁技術(shù)文章正文

說一下HashMap的實現(xiàn)原理?【java面試必問】

更新時間:2022-07-14 來源:黑馬程序員 瀏覽量:

IT培訓(xùn)班

HashMap概述:HashMap是基于哈希表的Map接口的非同步實現(xiàn)。此實現(xiàn)提供所有可選的映射操作,并允許使用null值和null鍵。此類不保證映射的順序,特別是它不保證該順序恒久不變。


HashMap的數(shù)據(jù)結(jié)構(gòu):在java編程語言中,最基本的結(jié)構(gòu)就是兩種,一個是數(shù)組,另外一個是模擬指針(引用),所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個基本結(jié)構(gòu)來構(gòu)造的,HashMap也不例外。HashMap實際上是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu),即數(shù)組和鏈表的結(jié)合體。


當(dāng)我們往Hashmap中put元素時,首先根據(jù)key的hashcode重新計算hash值,根絕hash值得到這個元素在數(shù)組中的位置(下標(biāo)),如果該數(shù)組在該位置上已經(jīng)存放了其他元素,那么在這個位置上的元素將以鏈表的形式存放,新加入的放在鏈頭,最先加入的放入鏈尾.如果數(shù)組中該位置沒有元素,就直接將該元素放到數(shù)組的該位置上。


需要注意Jdk 1.8中對HashMap的實現(xiàn)做了優(yōu)化,當(dāng)鏈表中的節(jié)點數(shù)據(jù)超過八個之后,該鏈表會轉(zhuǎn)為紅黑樹來提高查詢效率,從原來的O(n)到O(logn)。




猜你喜歡:

HashMap,HashTable,ConcurrentHashMap有什么不同?

如何理解并實現(xiàn)HashMap?【Java培訓(xùn)】

java基本功——HashMap 視頻教程下載

黑馬程序員java后端開發(fā)開發(fā)培訓(xùn)

分享到:
在線咨詢 我要報名
和我們在線交談!