Java中的HashMap相信大家都不陌生，也是大家編程時最常用的數據結構之一，各種面試題更是恨不得掘地三尺的去問HashMap、HashTable、ConcurrentHashMap，無論面試題多麽刁鑽的問，只要我們真正的掌握了它的設計思想，便可以不變應萬變，hold住所有的面試題了。
本文主要包含以下內容，力求深入淺出一步一步徹底明白HashMap的設計思想：
- 數組的優勢
- 數組是特殊的鍵值對
- Hash函數
- Hash沖突
- 此時再看HashMap源碼
文章幹貨內容較多，建議大家“收藏”後持續閱讀！
關注“java架構設計”，閱讀更多技術幹貨文章！
數組的優勢
整型數組
上圖是一個含有8個元素的整型數組，數組下標從0到7，
如果我們要獲取第四個元素的值，直接a[3]就可以了，時間複雜度爲O(1)，
如果我們要將第四個元素的值替換爲36，直接a[3]=36就可以了，時間複雜度也是O(1),
也就是說基于下標的隨機訪問和賦值數組元素的時間複雜度都是O(1)，無論這個數組是多大（在內存充足的條件下），這是數組的優勢之一。
數組不夠，我們還需要鍵值對
通過上面的簡單描述，我們可以知道數組可以通過“下標”來獲取數組中的指定元素，但是這個下標只能是正整數，且從0開始。
但是如果我們想通過一個浮點數、一個字符串、一個對象來獲取對應的元素呢？也就是所謂的鍵值對，是不是數組就滿足不了了？
我們可以把數組看做是一種特殊的鍵值對，key就是數組的下標，value就是下標對應的元素：
鍵值對
所以我們要求KV數據結構裏面的key是一個對象，而不僅僅只能是數組中的一個下標。因此我們需要創造出一種數據結構，他至少需要具有以下的特性：
- O(1)複雜度的訪問任何一個key對應的值
- 這個key可以支持整型、浮點、字符串、對象等任何類型的數據
第一個特性要求我們需要一個像數組下標一樣的整型數字來快速訪問數組。
第二個特性要求我們的下標不限制只能是整型。
顯然我們需要對key做一些特殊處理，這個時候Hash函數就上場了。
Hash函數
哈希函數的作用就是通過哈希算法把任意類型的key轉換成固定類型、固定長度的散列值，也就是我們所期望的數組下標（整型）。
因此哈希函數需要具有如下的特征：
- 相同的內容經過哈希算法計算後輸出結果一致；
- 不同的內容經過哈希算法計算後輸出不同的結果，但也可能會出現相同的輸出值（即哈希碰撞）；
因此，一個優秀的哈希算法是不同的內容經過哈希計算後輸出的結果具有分布均勻的特點，也就是低碰撞率。
同時，計算速度必須要快！
比較出名的哈希算法有time33算法、Murmurhash算法，這些算法都在追求更好的均勻分布和更快的計算速度。
Java8中java.lang.String類的hashCode方法實現：
java.lang.String#hashCode()
現在來寫一個簡單的測試類來測試Java中的String類實現的hashCode：
輸出：
s1.hashCode=92599395
s2.hashCode=92599395
s3.hashCode=92599396可以看出來s1和s2是相同的字符串，輸出了相同的hash值，s3和s1、s2不同，輸出的hash值也不同，但是也很接近。
說明java采用的hash算法分散性不好，如果用Murmurhash算法，差異就會很大，即哈希算法的劇烈度大，感興趣的同學可以用Guava中Murmurhash方法試驗一下。
通過Hash算法，我們可以計算出任何一種數據類型的哈希值且爲整型，這樣就滿足了數組的下標必須爲整數的要求了。
但是又來了一個問題，通過上面的實驗我們拿到的hashCode值很大，無法作爲數組的下標，否則我們的數組占用的內存就太大了！
所以就采用了根據hashCode取余的方式，比如Java中的HashMap默認size是16，那麽92599395%16=3，那麽實際上abcde這個字符串就存儲在HashMap數組中下標爲3的地方。
Hash沖突
上面已經講過Hash算法無法做到完全均勻分布，也就是說可能會有那麽兩個不一樣的字符串經過hash計算後得到相同的值，此時兩個不同的字符串都得對應同一個數組下標上，這就造成了所謂的Hash沖突。
因此，爲了解決Hash沖突問題，我們需要下標對應的元素不再僅僅是當前對應的字符串了，而應該是當前的字符串再加上它的next節點的對象地址，這樣的一個對象應該如下：
當根據key去找值時候，先計算出key的hash值再取余得到數組的下標，然後根據下標獲取到元素，再判斷該元素的key是否和當前的key相等(如何判斷相等？equals方法！)，如果不相等，繼續取next節點，繼續判斷。
說到這裏大家如果對HashMap熟悉的話，是不是發現這其實就是HashMap的簡單版，一個數組+鏈表的實現：
再看HashMap源碼
如果你已經看到這裏，那麽我相信你一定已經了解了HashMap的結構了，那麽請回去看HashMap的源碼吧，你會發現原來是這麽簡單！這個時候你已經達到了“看山不是山”的境界了！面試官問你任何關于HashMap的問題相信你都能回答了。
搞清楚了HashMap之後，HashTable和HashMap的區別？ConcurrentHashMap是線程安全的基于分段鎖的HashMap？爲了優化鏈表的性能，當鏈表的數超過8之後就變成平衡樹了等等。。。
後面做的事情要麽是爲了線程安全要麽就是爲了性能。