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

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é)合體。

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

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

猜你喜歡：

HashMap，HashTable，ConcurrentHashMap有什么不同？

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

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

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