HashMap是一個用於儲存Key-Value的集合，根據Key而直接查詢記憶體儲存位置的資料結構。其實際意義為將Key通過計算(映射函數)，映射到表中的特定位置，得到記憶體位址，並直接由記憶體位址取值，可以使查找速度較快。而這個映射含數為雜湊函數，映射後的表稱為雜湊表。
其優點為:
- 資料量大時，維持相同的運算速度
2. 若已知資料數量，可以直接設定所需的記憶體容量，避免記憶體重新配置
3. 若已知資料型態，可以根據該資料型態尋找最佳雜湊函數
缺點為:
- 資料量較少時，雜湊計算成本較一般Array高
2. 效能與雜湊函數相關，較差的函數容易造成雜湊碰撞，較佳的函數計算成本通常較高
概念
先建立一個陣列，用於擺放Key對應之Value。以聯絡人為例:
我們目前建立第一筆資料，Marc的電話為12345
步驟為:
1. 經過雜湊函數，Marc對應的Index為2
2. 將電話號碼12345放置array[2]的位置
Hash_function(“Marc”) = 2
接著再建立兩筆資料，Pedrosa: 45678、Dani: 56789
1. 經過雜湊函數，Pedrosa對應的Index為0
2. 將電話號碼45678放置array[0]的位置
3. 經過雜湊函數，Dani對應的Index為3
4. 將電話號碼56789放置array[3]的位置
Hash_function(“Pedrosa”) = 0
Hash_function(“Dani”) = 3
而需要取得Pedrosa的手機號碼，只要
1. 經過雜湊函數，Pedrosa對應的Index為0
2. 從Array[0]的索引位置上，取得Pedrosa的電話為45678
以上就完成了最基礎的HashMap。
雜湊
雜湊函數就是將 ”較廣值域映射至較窄值域” 的函數。實際上就是Encode，將複雜的數字、字串或其他符號經過轉換後對應到有限的範圍內。不過雜湊函數需要有一定的特性:
Key1 == Key2 >> hash_function(Key1) == hash_function(Key2)
當Key相同時，映射後的結果必須一致，否則Key對應之Value會不相同。其中最重要的是雜湊函數，根據不同的情況可以使用不同的映射函數。
選擇雜湊函數
由於雜湊函數會直接影響計算的速度及記憶體占用，因此選擇雜湊函數是相當重要。好的函數會有以下特性:
1. 相同的Key會對應至相同的雜湊值
2. 計算花費時間少
3. 任意輸入資料所得之雜湊值須接近均勻分布，減少雜湊碰撞問題
雜湊碰撞
雜湊碰撞就是不同輸入的Key卻計算出相同雜湊值，造成多個Key對應到相同索引上。但這種狀況也可以處理，分別為separate chaining與open addressing。
separate chaining
separate chaining就是讓不同Key對應到相同索引的狀況發生時，將所有的Value皆儲存下來的做法。可以用幾種作法:
1. Linked List鏈結串列: 以Linked List儲存Value，可以自由將碰撞的所有元素儲存下來。
2. 動態陣列: 當碰撞發生時，再該位址配置動態陣列儲存元素。
open addressing
open addressing則不給碰撞的元素額外的配置空間，而是在原始陣列內尋找未被配置的空間，再把衝突的元素儲存。依據不同探測方式會得到不同的HashMap，有幾種常見的方式:
1. Linear probing: 從碰撞的索引開始，依序找下一個空的位置後儲存。
2. Quadratic probing: 從碰撞的索引開始，以平方為間隔尋找空的位置儲存，如X +1 ， X +4 ，X +9，X+16...
3. Double hashing: 從碰撞的索引開始，以固定大小K為間隔，尋找空的位置儲存碰撞之Value，如: X+K，X+2K，X+3K。而這個間隔是以另外一個函數計算而來，因此又稱為”雙雜湊”。
X為發生碰撞的索引
這些方法的差異為CPU效能，以及HashMap資料群聚效應的敏感程度。以Linear probing為舉例，Linear probing擁有較少的計算過程，但會受到雜湊函數影響，當映射值較為集中時，依次搜尋所造成的時間就會較久，且容易造成群聚效應，資料集中而非平均分布。
動態調整雜湊表
若資料的數量已知，可以直接配置與資料成正比的陣列大小，因此就不用擔心雜湊表空間不夠，而造成需要重新配置儲存空間(reallocate)的狀況。
但在未知資料數量的狀態下，則需要動態調整雜湊表。但其新增空間方式與一般動態陣列不同，舊的雜湊表對應至新的雜湊表需要將所有Key都重新計算過，更新為新的雜湊值(rehash)。
因為需要將所有Key都重新計算過，因此需要盡可能減少動態調整的次數，而其有一個評估指標: load factor
n ：已放入雜湊表內的資料總數。
k：雜湊表配置的儲存空間（bucket 總數）。
Load factor代表目前雜湊表的”使用率”，若三筆資料放入四個bucket內，則load factor為75%。
當Load factor太大時會容易發生碰撞，造成效能影響，但太小時空間使用率過低，太多冗餘。因此load factor的控制相當重要，一般而言，load factor約75%時就可以重新配置雜湊表。但此數值還是要根據應用狀況調整。
重配置雜湊表與動態陣列的動態調整大小雷同，達到某個門檻值，就會將底層陣列大小翻倍。為了避免開銷過高，通常元素減少時，不會主動調整大小。
