作者：張豐哲
來源： jianshu.com/p/b638f19aeb64
HashMap是Java中常用的集合，而且HashMap的一些思想，對于我們平時解決業務上的一些問題，在思路上有幫助，基于此，本篇博客將分析HashMap底層設計思想，并手寫一個迷你版的HashMap！
對HashMap的思考
第一，如圖所示，HashMap有3個要素：hash函式+陣列+單鏈表
第二，對于hash函式而言，需要考慮些什么？
要快，對于給定的Key，要能夠快速計算出在陣列中的index，那么什么運算夠快呢？顯然是位運算！
要均勻分布，要較少碰撞，說白了，我們希望通過hash函式，讓資料均勻分布在陣列中，不希望大量資料發生碰撞，導致鏈表過長，那么怎么辦到呢？也是利用位運算，通過對資料的二進制的位進行移動，讓hash函式得到的資料散列開來，從而減低了碰撞的概率，
如果發生了碰撞怎么辦？上面的圖其實已經說明了JDK的HashMap是如何處理hash沖突的，就是通過單鏈表解決的，那么除了這個方法，還有其他思路么？
比如說，如果發生沖突，那么記下這個沖突的位置為index，然后在加上固定步長，即index+step，找到這個位置，看一下是否仍然沖突，如果繼續沖突，那么按照這個思路，繼續加上固定步長，其實這就是所謂的線性探測來解決Hash沖突的方法！
通過寫一個迷你版的HashMap來深刻理解
定義介面
定義一個介面，對外暴露快速存取的方法，
注意MyMap介面內部定義了一個內部介面Entry，
介面實作
HashMap的要素之一，就是陣列，自然在這里，我們要定義陣列，陣列的初始化大小，還要考慮擴容的閥值，
看MyHashMap的構造
構造方法有什么好說的呢？
仔細觀察下，你會發現，其實這里使用到了“門面模式”，這里的2個構造方法其實指向的是同一個，但是對外卻暴露了2個“門面”！
Entry
HashMap的要素之一，單鏈表的體現就在這里！
看put如何實作
第一，要考慮是否擴容？
HashMap中的Entry的數量（陣列以及單鏈表中的所有Entry）是否達到閥值？
第二，如果擴容，意味著新生成一個Entry[]，不僅如此還得重新散列，
第三，要根據Key計算出在Entry[]中的位置，定位后，如果Entry[]中的元素為null，那么可以放入其中，如果不為空，那么得遍歷單鏈表，要么更新value，要么形成一個新的Entry“擠壓”單鏈表！
hash函式
我這里參考了JDK的HashMap的hash函式的實作，這里也再次說明了：要想散列均勻，就得進行二進制的位運算！
resize和rehash
這里可以看出，對于HashMap而言，如果頻繁進行resize/rehash操作，是會影響性能的，
resize/rehash的程序，就是陣列變大，原來陣列中的entry元素一個個的put到新陣列的程序，需要注意的是一些狀態變數的改變，
get實作
get很簡單，只需要注意在遍歷單鏈表的程序中使用== or equals來判斷下即可，
Test測驗
運行結果
OK，一個迷你版的HashMap就寫好了，你學到了么？
近期熱文推薦：
1.1,000+ 道 Java面試題及答案整理(2021最新版)
2.別在再滿屏的 if/ else 了，試試策略模式，真香！！
3.臥槽！Java 中的 xx ≠ null 是什么新語法？
4.Spring Boot 2.5 重磅發布，黑暗模式太炸了！
5.《Java開發手冊（嵩山版）》最新發布，速速下載！
覺得不錯，別忘了隨手點贊+轉發哦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/298545.html
標籤：Java