HashMap是Java中常用的集合，而且HashMap的一些思想，對(duì)于我們平時(shí)解決業(yè)務(wù)上的一些問(wèn)題，在思路上有幫助，基于此，本文將分析HashMap底層設(shè)計(jì)思想，并手寫一個(gè)迷你版的HashMap!
對(duì)HashMap的思考
HashMap底層數(shù)據(jù)結(jié)構(gòu)
第一，如圖所示，HashMap有3個(gè)要素：hash函數(shù)+數(shù)組+單鏈表第二，對(duì)于hash函數(shù)而言，需要考慮些什么?
要快，對(duì)于給定的Key，要能夠快速計(jì)算出在數(shù)組中的index。那么什么運(yùn)算夠快呢?顯然是位運(yùn)算!
要均勻分布，要較少碰撞。說(shuō)白了，我們希望通過(guò)hash函數(shù)，讓數(shù)據(jù)均勻分布在數(shù)組中，不希望大量數(shù)據(jù)發(fā)生碰撞，導(dǎo)致鏈表過(guò)長(zhǎng)。那么怎么辦到呢?也是利用位運(yùn)算，通過(guò)對(duì)數(shù)據(jù)的二進(jìn)制的位進(jìn)行移動(dòng)，讓hash函數(shù)得到的數(shù)據(jù)散列開(kāi)來(lái)，從而減低了碰撞的概率。
如果發(fā)生了碰撞怎么辦?上面的圖其實(shí)已經(jīng)說(shuō)明了JDK的HashMap是如何處理hash沖突的，就是通過(guò)單鏈表解決的。那么除了這個(gè)方法，還有其他思路么?比如說(shuō)，如果發(fā)生沖突，那么記下這個(gè)沖突的位置為index，然后在加上固定步長(zhǎng)，即index+step，找到這個(gè)位置，看一下是否仍然沖突，如果繼續(xù)沖突，那么按照這個(gè)思路，繼續(xù)加上固定步長(zhǎng)。其實(shí)這就是所謂的線性探測(cè)來(lái)解決Hash沖突的方法!
通過(guò)寫一個(gè)迷你版的HashMap來(lái)深刻理解
定義接口
接口
- 定義一個(gè)接口，對(duì)外暴露快速存取的方法。
- 注意MyMap接口內(nèi)部定義了一個(gè)內(nèi)部接口Entry。
接口實(shí)現(xiàn)
HashMap的要素之一，就是數(shù)組，自然在這里，我們要定義數(shù)組，數(shù)組的初始化大小，還要考慮擴(kuò)容的閥值。
看MyHashMap的構(gòu)造
構(gòu)造方法有什么好說(shuō)的呢?
仔細(xì)觀察下，你會(huì)發(fā)現(xiàn)，其實(shí)這里使用到了"門面模式"。這里的2個(gè)構(gòu)造方法其實(shí)指向的是同一個(gè)，但是對(duì)外卻暴露了2個(gè)"門面"!
Entry
HashMap的要素之一，單鏈表的體現(xiàn)就在這里!
看put如何實(shí)現(xiàn)
第一，要考慮是否擴(kuò)容?HashMap中的Entry的數(shù)量(數(shù)組以及單鏈表中的所有Entry)是否達(dá)到閥值?
第二，如果擴(kuò)容，意味著新生成一個(gè)Entry[]，不僅如此還得重新散列。
第三，要根據(jù)Key計(jì)算出在Entry[]中的位置，定位后，如果Entry[]中的元素為null，那么可以放入其中，如果不為空，那么得遍歷單鏈表，要么更新value，要么形成一個(gè)新的Entry"擠壓"單鏈表!
hash函數(shù)
MyHashMap提供的hash函數(shù)
JDK的HashMap提供的hash函數(shù)
我這里參考了JDK的HashMap的hash函數(shù)的實(shí)現(xiàn)，這里也再次說(shuō)明了：要想散列均勻，就得進(jìn)行二進(jìn)制的位運(yùn)算!
resize和rehash
這里可以看出，對(duì)于HashMap而言，如果頻繁進(jìn)行resize/rehash操作，是會(huì)影響性能的。
resize/rehash的過(guò)程，就是數(shù)組變大，原來(lái)數(shù)組中的entry元素一個(gè)個(gè)的put到新數(shù)組的過(guò)程，需要注意的是一些狀態(tài)變量的改變。
get實(shí)現(xiàn)
get
get很簡(jiǎn)單，只需要注意在遍歷單鏈表的過(guò)程中使用==orequals來(lái)判斷下即可。
Test測(cè)試
利用MyHashMap進(jìn)行存取
運(yùn)行結(jié)果
OK，一個(gè)迷你版的HashMap就寫好了，你學(xué)到了么?
以上就是北大青鳥長(zhǎng)沙麓谷校區(qū)java培訓(xùn)機(jī)構(gòu)的小編針對(duì)“編程基礎(chǔ)入門，Java實(shí)現(xiàn)hashmap”的內(nèi)容進(jìn)行的回答，希望對(duì)大家有所幫助，如有疑問(wèn)，請(qǐng)?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為你服務(wù)。
