在了解golang的map之前，我們需要了解哈希這個概念。
哈希表，又稱散列表(Hash table)，是根據鍵(key)而直接訪問在內存儲存位置的數據結構。也就是說，它通過計算出一個鍵值的函數，將所需查詢的數據映射到表中的一個位置讓人訪問，這加快了查找速度。這個映射函數稱為散列函數，存放記錄的數組稱作散列表。
1、特點
一個優秀的哈希函數應該包含以下特性：
- 均勻性：一個好的哈希函數應該在其輸出范圍內盡可能均勻地映射，也就是說，應以大致相同的概率生成輸出范圍內的每個哈希值。
- 高效率：哈希效率要高，即使很長的輸入參數也能快速計算出哈希值。
- 單向性：哈希過程必須是確定性的，這意味著對于給定的輸入值，它必須始終生成相同的哈希值。
- 雪崩效應：微小的輸入值變化也會讓輸出值發生巨大的變化。
- 不可逆：從哈希函數的輸出值不可反向推導出原始的數據。
2、哈希沖突
由于哈希算法被計算的數據是無限的，而計算后的結果范圍有限，因此總會存在不同的數據經過計算后得到的值相同，這就是哈希沖突。
3、解決哈希沖突的方法
解決哈希沖突的方法一般有：開放定址法、鏈地址法（拉鏈法）、再哈希法、建立公共溢出區等方法。
而我們這里主要介紹開放地址法和拉鏈法。
3.1、拉鏈法
鏈接地址法的思路是將哈希值相同的元素構成一個同義詞的單鏈表，并將單鏈表的頭指針存放在哈希表的第i個單元中，查找、插入和刪除主要在同義詞鏈表中進行。鏈表法適用于經常進行插入和刪除的情況。
3.2、開放地址法
從發生沖突的那個單元起，按照一定的次序，從哈希表中找到一個空閑的單元。然后把發生沖突的元素存入到該單元的一種方法。開放定址法需要的表長度要大于等于所需要存放的元素。
在開放尋址法中解決沖突的方法有：線性探測法、平方探測法、雙散列函數探測法。
開放定址法的缺點在于刪除元素的時候不能真的刪除，否則會引起查找錯誤，只能做一個特殊標記。只到有下個元素插入才能真正刪除該元素。
3.2.1、線性探測法
線性探查法是開放定址法中最簡單的沖突處理方法，它從發生沖突的單元起，依次判斷下一個單元是否為空，當達到最后一個單元時，再從表首依次判斷。直到碰到空閑的單元或者探查完全部單元為止。
設Hash(key)表示關鍵字key的哈希值，表示哈希表的槽位數（哈希表的大?。?/p>
線性探測法可以表示為：
- 如果Hash(x)%M已經有數據，則嘗試(Hash(x)+1)%M
- 如果(Hash(x)+1)%M有數據，則嘗試(Hash(x)+2)%M
- 如果(Hash(x)+2)%M有數據，則嘗試(Hash(x)+3)%M
- …
同樣以哈希函數H(key)=key MOD 7（除數取余法）對一組元素[50,700,76,85,92,73,101]進行映射。
其中，empty代表槽位為空，occupied代表槽位已被占（后續映射到該槽，則需要線性向下繼續探測)，而lazy delete則代表將槽位里面的數據清除，并不釋放存儲空間。
3.2.2、平方探測法
平方探查法即是發生沖突時，用發生沖突的單元d[i], 加上 1²、 2²等。即d[i] + 1²，d[i] + 2², d[i] + 3²…直到找到空閑單元。 在實際操作中，平方探查法不能探查到全部剩余的單元。不過在實際應用中，能探查到一半單元也就可以了。若探查到一半單元仍找不到一個空閑單元，表明此散列表太滿，應該重新建立。
3.2.3、雙散列函數探測法
這種方法使用兩個散列函數hl和h2。
其中hl和前面的h一樣，以關鍵字為自變量，產生一個0至m-l之間的數作為散列地址；
h2也以關鍵字為自變量，產生一個l至m-1之間的、并和m互素的數(即m不能被該數整除)作為探查序列的地址增量(即步長)，探查序列的步長值是固定值l.
對于平方探查法，探查序列的步長值是探查次數i的兩倍減l；
對于雙散列函數探查法，其探查序列的步長值是同一關鍵字的另一散列函數的值。
4、小結
哈希桶：所有哈希值組成哈希空間
裝載因子：表示哈希表中元素的填滿程度。
計算方式：裝載因子=填入哈希表中的元素個數/哈希表的長度。
裝載因子越大，填入的元素越多，空間利用率越高，發生哈希沖突的幾率變大。
裝載因子越小，填入的元素越少，空間利用率越低，但空間浪費多，而且會提高擴容操作的次數。
開放地址法
只用數組一種數據結構就可完成存儲，繼承了數組的優點，對CPU緩存友好，易于序列化操作。
但是它對內存的利用率不如鏈地址法，且發生沖突時代價更高。當數據量明確、裝載因子小，適合采用開放尋址法。
鏈地址法
1、處理沖突簡單，且無堆積現象
2、由于拉鏈法中各鏈表上的節點空間在需要時創建，不必像開放地址法事先申請好足夠的內存，因此對內存使用率較高，適合造表前無法確定表長的情況
3、對裝載因子的容忍度較高，適合存儲大對象、大數據量的哈希表
4、刪除結點的操作易于實現，只要簡單地刪去鏈表上相應的結點即可。
