前言

在上一篇文章中，我們介紹了兩個線性的資料結構：數組和切片。在本文中，我們會介紹另一種在計算機科學裡常用的資料結構-哈希表(Hash Table)。

哈希表是一種儲存鍵/值對(keuy/value)的資料結構，在哈希表裡，我們會利用一些方法將將鍵映射到物件身上，鍵值之間的連繫關系就是哈希。哈希表有不同的實現方式，但是它們都擁有快速查找、新壞和刪除的特性。Go語言提供了一個內建的map型態。

哈希表

哈希函數

哈希表的關鍵在於哈希函數的選擇。我們會希望找到一個哈希函數，透過此函數將不同鍵映射到唯一的索引上，

但是這種映射是一種壓縮轉換，也就是輸出的Hash值範圍通常遠小於輸入範圍，不同的蛉入可能會Hash到同一個輸出。因此哈希表在實際使用時，理想狀態是不可能達到的。

兩個不同的輸入值，經過哈希函數計算出同樣的哈希值的現象稱為碰撞。

常見的哈希函數

• 直接定址法：直接以鍵值k或者k加上某個常數c作為哈希值。
• 數字分析法：提取鍵值中取值比較均勻的數字作為哈希值。
• 除留餘數法：將鍵字除以某個不大於哈希表長度m，所得餘數即為哈希值
• 分段疊加法：按照哈希表地址位數，將關鍵字分成位數相等的幾部分，然後將這幾部分相加，總和捨棄最高位後的結果即為哈希值。
• 平分取中法：當鍵值各個部分分佈都不均勻時，可以求出它的平方值，然後按照需求取中間的幾位作為哈希值。
• 偽隨機數法：採用一個偽隨機數當作哈希函數

碰撞解決

衡量一個哈希函數的重要指標就是發生碰撞的機率，還有發生碰撞後的解決方案。常見的碰撞解決方案如下：

• 開放定址法：
  當哈希函數發生時，就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到並將之記錄下來。
• 鏈結地址法：
  將哈希表的每個單元都視為鏈表的頭結點，當衝突發生時就把該鍵值增加在以哈希值為頭結點的鏈表尾部。
• 再哈希法
  衝突發生時，用其他哈希函數再計算另一個哈希函數地址，重覆計算到衝突不再產生為止。
• 建立公共溢出區：
  將哈希表分為基本表和溢出表，發生衝突的鍵值都放入溢出表裡。

Map的使用

宣告與初始化

Go語言裡，宣告map物件的語法如下：

var m map [<KeyType>]ValueType

其中key必須為可以哈希的資料型態，value可以是任何的資料型態，包括map。
Map類似切片，屬於一種reference type，當m宣告後未賦值時，默認值為nil。

將map物件初始化需要用到map函數

//宣告一個m為map型態
var m map [int]int
//將m初始化
m=make(map[int]int)

如何使用

使用map需要注意的地方

• map是無序的，每次print出來的map都不一樣，它必須通過key獲取value，而不是index。
• map是無序的，和slice一樣，也是一種引用類型。
• map可以使用內建的len函數，它會返回所擁有的key數量。
• map並非thread-safe，在多個go-routine存取時必須使用mutex lock機制。
• map的初始化可以通過key:val的方式，同時map內置會判斷是否存在key。

使用delete可以刪除map的元素:

// 初始化一個map物件
support := map[string]float32{"C":3.0, "Go":1.12, "Python":3.7, "Java":10 }
// 查調map有兩個返回，value和ok，當key不存在於map裡時，ok為false，反之ok為true。
version, ok := rating["Java"]
if ok {
    fmt.Println("We are supporting the Java %d",version)
} else {
    fmt.Println("We are not supporting Java yet")
}

delete(rating, "C") //從map裡頭刪除C的鍵值對

另外map是引用類型，多個變數操作同一個map物件時要小心

m := make(map[string]string)
m["Hello"] = "Bonjour"
m1 := m
m1["Hello"] = "Salut"

fmt.Println(m["Hello"]) //輸出: Salut