對HashMap的思考及手寫實現(xiàn)-創(chuàng)新互聯(lián)

作者：張豐哲
原文：https://www.jianshu.com/p/b638f19aeb64

HashMap是Java中常用的集合，而且HashMap的一些思想，對于我們平時解決業(yè)務(wù)上的一些問題，在思路上有幫助，基于此，本篇博客將分析HashMap底層設(shè)計思想，并手寫一個迷你版的HashMap！

成都創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站制作、成都做網(wǎng)站、外貿(mào)營銷網(wǎng)站建設(shè)、察哈爾右翼后網(wǎng)絡(luò)推廣、微信小程序定制開發(fā)、察哈爾右翼后網(wǎng)絡(luò)營銷、察哈爾右翼后企業(yè)策劃、察哈爾右翼后品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們大的嘉獎；成都創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供察哈爾右翼后建站搭建服務(wù)，24小時服務(wù)熱線：13518219792，官方網(wǎng)址：muchs.cn

對HashMap的思考

HashMap底層數(shù)據(jù)結(jié)構(gòu)

第一，如圖所示，HashMap有3個要素：hash函數(shù)+數(shù)組+單鏈表

第二，對于hash函數(shù)而言，需要考慮些什么？

要快，對于給定的Key，要能夠快速計算出在數(shù)組中的index。那么什么運算夠快呢？顯然是位運算！

要均勻分布，要較少碰撞。說白了，我們希望通過hash函數(shù)，讓數(shù)據(jù)均勻分布在數(shù)組中，不希望大量數(shù)據(jù)發(fā)生碰撞，導(dǎo)致鏈表過長。那么怎么辦到呢？也是利用位運算，通過對數(shù)據(jù)的二進制的位進行移動，讓hash函數(shù)得到的數(shù)據(jù)散列開來，從而減低了碰撞的概率。

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

通過寫一個迷你版的HashMap來深刻理解

定義接口

接口

定義一個接口，對外暴露快速存取的方法。

注意MyMap接口內(nèi)部定義了一個內(nèi)部接口Entry。

接口實現(xiàn)

MyHashMap定義

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

看MyHashMap的構(gòu)造

構(gòu)造方法

構(gòu)造方法有什么好說的呢？

仔細(xì)觀察下，你會發(fā)現(xiàn)，其實這里使用到了“門面模式”。這里的2個構(gòu)造方法其實指向的是同一個，但是對外卻暴露了2個“門面”！

Entry

Entry

HashMap的要素之一，單鏈表的體現(xiàn)就在這里！

看put如何實現(xiàn)

put

第一，要考慮是否擴容？

HashMap中的Entry的數(shù)量（數(shù)組以及單鏈表中的所有Entry）是否達到閥值？

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

第三，要根據(jù)Key計算出在Entry[]中的位置，定位后，如果Entry[]中的元素為null，那么可以放入其中，如果不為空，那么得遍歷單鏈表，要么更新value，要么形成一個新的Entry“擠壓”單鏈表！

hash函數(shù)

MyHashMap提供的hash函數(shù)

JDK的HashMap提供的hash函數(shù)

我這里參考了JDK的HashMap的hash函數(shù)的實現(xiàn)，這里也再次說明了：要想散列均勻，就得進行二進制的位運算！

resize和rehash

resize/rehash

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

resize/rehash的過程，就是數(shù)組變大，原來數(shù)組中的entry元素一個個的put到新數(shù)組的過程，需要注意的是一些狀態(tài)變量的改變。

get實現(xiàn)

get

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

Test測試

利用MyHashMap進行存取

運行結(jié)果

result

OK，一個迷你版的HashMap就寫好了，你學(xué)到了么？

網(wǎng)站欄目：對HashMap的思考及手寫實現(xiàn)-創(chuàng)新互聯(lián)
鏈接分享：http://muchs.cn/article36/dejcpg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、網(wǎng)站營銷、全網(wǎng)營銷推廣、自適應(yīng)網(wǎng)站、網(wǎng)站維護、用戶體驗

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)