全國咨詢/投訴熱線:400-618-4000

了解HashMap底層設計思想,教你手寫一個迷你版的HashMap!【java培訓】

更新時間:2020年04月09日14時58分 來源:傳智播客

HashMap是Java中常用的集合,而且HashMap的一些思想,對于我們平時解決業務上的一些問題,在思路上有幫助,基于此,本文將分析HashMap底層設計思想,并手寫一個迷你版的HashMap!

對HashMap的思考

HashMap的思考01


HashMap底層數據結構第一,如圖所示,HashMap有3個要素:hash函數+數組+單鏈表。

第二,對于hash函數而言,需要考慮些什么?

要快,對于給定的Key,要能夠快速計算出在數組中的index。那么什么運算夠快呢?顯然是位運算!要均勻分布,要較少碰撞。說白了,我們希望通過hash函數,讓數據均勻分布在數組中,不希望大量數據發生碰撞,導致鏈表過長。那么怎么辦到呢?也是利用位運算,通過對數據的二進制的位進行移動,讓hash函數得到的數據散列開來,從而減低了碰撞的概率。

如果發生了碰撞怎么辦?上面的圖其實已經說明了JDK的HashMap是如何處理hash沖突的,就是通過單鏈表解決的。那么除了這個方法,還有其他思路么?比如說,如果發生沖突,那么記下這個沖突的位置為 index,然后在加上固定步長,即index+step,找到這個位置,看一下是否仍然沖突,如果繼續沖突,那么按照這個思路,繼續加上固定步長。其實這就是所謂的線性探測來解決Hash沖突的方法!

通過寫一個迷你版的HashMap來深刻理解定義接口

定義接口

HashMap的思考02

接口

定義一個接口,對外暴露快速存取的方法。注意MyMap接口內部定義了一個內部接口Entry。

接口實現

HashMap的思考03

HashMap的要素之一,就是數組,自然在這里,我們要定義數組,數組的初始化大小,還要考慮擴容的閥值。

看MyHashMap的構造

HashMap的思考04


構造方法有什么好說的呢?

仔細觀察下,你會發現,其實這里使用到了“門面模式”。這里的2個構造方法其實指向的是同一個,但是對外卻暴露了2個“門面”!

Entry

HashMap的思考05

HashMap的要素之一,單鏈表的體現就在這里!

看put如何實現

HashMap的思考06

第一,要考慮是否擴容?

HashMap中的Entry的數量(數組以及單鏈表中的所有Entry)是否達到閥值?

第二,如果擴容,意味著新生成一個Entry[],不僅如此還得重新散列。

第三,要根據Key計算出在Entry[]中的位置,定位后,如果Entry[]中的元素為null,那么可以放入其中,如

果不為空,那么得遍歷單鏈表,要么更新value,要么形成一個新的Entry“擠壓”單鏈表!

hash函數

HashMap的思考07

MyHashMap提供的hash函數

HashMap的思考08


JDK的HashMap提供的hash函數

我這里參考了JDK的HashMap的hash函數的實現,這里也再次說明了:要想散列均勻,就得進行二進制的位運算!

resize和rehash

HashMap的思考09

這里可以看出,對于HashMap而言,如果頻繁進行resize/rehash操作,是會影響性能的。

resize/rehash的過程,就是數組變大,原來數組中的entry元素一個個的put到新數組的過程,需要注意的是一些狀態變量的改變。

get實現

HashMap的思考10.png

get

get很簡單,只需要注意在遍歷單鏈表的過程中使用== or equals來判斷下即可。

Test測試

HashMap的思考11

利用MyHashMap進行存取

運行結果

HashMap的思考12

OK,一個迷你版的HashMap就寫好了,你學到了么?

猜你喜歡:
java中級程序員學習線路圖

如何使用solr完成vip等級排名?

17058期足彩专家复式 贵州省11选5前三走势 大庆麻将下载 股票当日跌停还会涨 15选5中奖新闻 安徽快3下载安卓版 平煤股份股票 娱网棋牌大厅下载地址谁知道的 366娱乐城网上百家乐 网络捕鱼游戏的诀窍 姚记娱乐APP官网版下载