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就寫好了，你學到了麼？