更新時間:2020-04-09 來源:黑馬程序員 瀏覽量:
HashMap是Java中常用的集合,而且HashMap的一些思想,對于我們平時解決業(yè)務(wù)上的一些問題,在思路上有幫助,基于此,本篇博客將分析HashMap底層設(shè)計(jì)思想,并手寫一個迷你版的HashMap!
對HashMap的思考
HashMap底層數(shù)據(jù)結(jié)構(gòu)第一,如圖所示,HashMap有3個要素:hash函數(shù)+數(shù)組+單鏈表。
第二,對于hash函數(shù)而言,需要考慮些什么?
要快,對于給定的Key,要能夠快速計(jì)算出在數(shù)組中的index。那么什么運(yùn)算夠快呢?顯然是位運(yùn)算!要均勻分布,要較少碰撞。說白了,我們希望通過hash函數(shù),讓數(shù)據(jù)均勻分布在數(shù)組中,不希望大量數(shù)據(jù)發(fā)生碰撞,導(dǎo)致鏈表過長。那么怎么辦到呢?也是利用位運(yùn)算,通過對數(shù)據(jù)的二進(jìn)制的位進(jìn)行移動,讓hash函數(shù)得到的數(shù)據(jù)散列開來,從而減低了碰撞的概率。
如果發(fā)生了碰撞怎么辦?上面的圖其實(shí)已經(jīng)說明了JDK的HashMap是如何處理hash沖突的,就是通過單鏈表解決的。那么除了這個方法,還有其他思路么?比如說,如果發(fā)生沖突,那么記下這個沖突的位置為 index,然后在加上固定步長,即index+step,找到這個位置,看一下是否仍然沖突,如果繼續(xù)沖突,那么按照這個思路,繼續(xù)加上固定步長。其實(shí)這就是所謂的線性探測來解決Hash沖突的方法!
通過寫一個迷你版的HashMap來深刻理解定義接口
定義接口
接口
定義一個接口,對外暴露快速存取的方法。注意MyMap接口內(nèi)部定義了一個內(nèi)部接口Entry。
接口實(shí)現(xiàn)
HashMap的要素之一,就是數(shù)組,自然在這里,我們要定義數(shù)組,數(shù)組的初始化大小,還要考慮擴(kuò)容的閥值。
看MyHashMap的構(gòu)造
構(gòu)造方法有什么好說的呢?
仔細(xì)觀察下,你會發(fā)現(xiàn),其實(shí)這里使用到了“門面模式”。這里的2個構(gòu)造方法其實(shí)指向的是同一個,但是對外卻暴露了2個“門面”!
Entry
HashMap的要素之一,單鏈表的體現(xiàn)就在這里!
看put如何實(shí)現(xiàn)
第一,要考慮是否擴(kuò)容?
HashMap中的Entry的數(shù)量(數(shù)組以及單鏈表中的所有Entry)是否達(dá)到閥值?
第二,如果擴(kuò)容,意味著新生成一個Entry[],不僅如此還得重新散列。
第三,要根據(jù)Key計(jì)算出在Entry[]中的位置,定位后,如果Entry[]中的元素為null,那么可以放入其中,如
果不為空,那么得遍歷單鏈表,要么更新value,要么形成一個新的Entry“擠壓”單鏈表!
hash函數(shù)
MyHashMap提供的hash函數(shù)
JDK的HashMap提供的hash函數(shù)
我這里參考了JDK的HashMap的hash函數(shù)的實(shí)現(xiàn),這里也再次說明了:要想散列均勻,就得進(jìn)行二進(jìn)制的位運(yùn)算!
resize和rehash
這里可以看出,對于HashMap而言,如果頻繁進(jìn)行resize/rehash操作,是會影響性能的。
resize/rehash的過程,就是數(shù)組變大,原來數(shù)組中的entry元素一個個的put到新數(shù)組的過程,需要注意的是一些狀態(tài)變量的改變。
get實(shí)現(xiàn)
get
get很簡單,只需要注意在遍歷單鏈表的過程中使用== or equals來判斷下即可。
Test測試
利用MyHashMap進(jìn)行存取
運(yùn)行結(jié)果
OK,一個迷你版的HashMap就寫好了,你學(xué)到了么?
猜你喜歡:
java中級程序員學(xué)習(xí)線路圖
SpringBoot整合Redis來實(shí)現(xiàn)緩存技術(shù)[java培訓(xùn)]
2020-04-07如何使用solr完成vip等級排名?[java培訓(xùn)]
2020-04-07Netty快速入門教程[java培訓(xùn)]
2020-04-07疫情期間黑馬程序員如何抓學(xué)生的學(xué)習(xí)質(zhì)量?
2020-04-03如何使用Neo4j構(gòu)建人物關(guān)系圖?[Javaee培訓(xùn)]
2020-04-03黑馬程序員疫情期間如何保證項(xiàng)目實(shí)戰(zhàn)課程效果?
2020-04-03