首先我們來通過下面的圖看看JDK1.7時代的HashMap是如何通過數(shù)組+鏈表的形式進(jìn)行值儲存的。

由圖中的描述可以清楚地看出來，當(dāng)數(shù)組第一次被定義并且第一次被賦值的時候，這個時候的操作很簡單，就是將這個值賦值到我們的table數(shù)組上面去。這個操作完成以后，然后我們進(jìn)行二次put:

如圖左下角描述所示的情況，當(dāng)數(shù)組table下標(biāo)出現(xiàn)了相等的情況的時候，此時此刻還是將肝鐵俠2的值賦值給tablle[i]的，這里講述的是JDK1.7版本下HashMap中插入的頭插法，而JDK1.8版本中是用的尾插法。插入以后，我們要讓數(shù)組指向鏈表的頭部，那么鏈表的頭部也就是頭節(jié)點是不是就是table[i]的位置呀。

如上，最終插入完成以后的模型就是這樣的：

那我們此時此刻是不是就可以大膽地猜測，在HashMap中，使用map.get(“name”)獲取到它的value的時候，是不是就是通過int hash = “name”.hashcode，然后獲取到對應(yīng)table下的數(shù)組下標(biāo)int i = hash % table.length獲取到table[i]的具體位置的鏈表，然后再通過hash去對應(yīng)table[i]上的鏈表中找到對應(yīng)的值呢？

有了這個思維，我們再去看HashMap的源碼就會輕松許多許多。下一期為大家?guī)鞨ashMap的手動實現(xiàn)。

再順帶兩個基本的關(guān)于HashMap的問題：

HashMap底層是怎么實現(xiàn)的呢？

在JDK1.7中是通過數(shù)組+鏈表實現(xiàn)的。JDK1.8中是通過數(shù)組+鏈表+樹(紅黑樹)組成的。

為什么要用鏈表呢？

①HashMap數(shù)組元素為鏈表的時候，插入直接使用頭插，插入復(fù)雜度O(1)，即操作的數(shù)量為常數(shù)，與輸入的數(shù)據(jù)的規(guī)模無關(guān)，效率是非?？斓?；當(dāng)鏈表較短時候，查找數(shù)據(jù)時對性能并沒有什么影響，但是如果鏈表一長，查找起來就很影響性能了。

②在Java8中，如果鏈表長度到達(dá)了8個，就會轉(zhuǎn)化為紅黑樹，提高了查找的性能，但每次插入新的數(shù)據(jù)，都得維護紅黑樹的結(jié)構(gòu)，復(fù)雜度為O(log n)。其實算是對查找和插入元素時性能的一個權(quán)衡，畢竟存入的效果就是用來查詢的。

這個問題的答案不唯一，可以自行了解一下。

以上就是JAVA進(jìn)階之HashMap底層實現(xiàn)解析的詳細(xì)內(nèi)容，更多關(guān)于HashMap底層實現(xiàn)的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論