HashMap是我們使用非常多的Collection，它是基于哈希表的 Map 接口的實現，以key-value的形式存在。在HashMap中，key-value總是會當做一個整體來處理，系統會根據hash算法來來計算key-value的存儲位置，我們總是可以通過key快速地存、取value。在學習HashMap之前先來了解幾個概念。

Hash的定義：

Hash，一般翻譯做“散列”，也有直接音譯為“哈?！钡摹Ｋ菍⒁粋€任意長度的二進制值通過一個映射關系轉換成一個固定長度的二進制值，任意長度的二進制值和固定長度的二進制值存在一一對應關系（就是key–value的關系）。

Hash表（取數據的時間復雜度為1）：

又叫散列表，通過一個 key 映射到表中的一個位置，來找到與這個key對應的唯一映射的Value，加快查詢的速度，這個映射函數叫做Hash函數，存放記錄的數組叫做散列表。

構造Hash函數：

由于HashMap的內部實現是使用了除留余數法因此只講解除留余數法（感興趣可以查看這篇博客）。

除留余數法（最常用的構造散列函數方法）：

f(key) = key mod p (p≤m)，m為散列表長。根據經驗，若散列表表長為m，通常p為小于或等于表長（最好接近m）的最最大質數，可以更好的減小沖突。 若表的長度為16(最接近16的素數為15，key為傳入的值通過特定的算法獲取到的值，value為要存取的值，index 為在Hash表中的坐標) key = 1，value=23，index=1%15= 1； key=17，value=22，index=17%15=2 ;

在Hash表中的儲存狀態：

Hash表處理沖突：

1.沖突產生的原因：

不同的key用同樣的Hash算法,可能會得到相同的Hash值

若存在一下三個數 a,b,c (其中 a 和 c 的通過 Hash 函數的到了 Hash 值都為3, c 的得到 Hash 值為2 )：

那么他們在Hash表中的儲存狀態為：

拉鏈法（HashMap中使用的這種方法來進行沖突的處理）

拉鏈法的數據結構 我們都知道，數組存儲區間是連續的，占用內存嚴重，故空間復雜的很大。但數組的二分查找時間復雜度小，為O(1)；數組的特點是：尋址容易，插入和刪除困難；而鏈表存儲區間離散，占用內存比較寬松，故空間復雜度很小，但時間復雜度很大，達O（N）。鏈表的特點是：尋址困難，插入和刪除容易。拉鏈法利用了它們的優點，有數組和鏈表構成，既滿足了數據的查找方便，同時不占用太多的內容空間，使用也十分方便。

拉鏈法解決沖突的做法： 將具有相同Hash值的結點鏈接在同一個單鏈表中。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。 【例】設有 m ＝ 5 ， H(K) ＝ K mod 5 ，關鍵字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外鏈地址法所建立的哈希表如下圖所示：

拉鏈法的優點：

拉鏈法的缺點：