# 數據結構 in Golang：Hash Tables（哈希表） ### 場景 - 水果店的價格表： - 蘋果 Apple：3元 - 香蕉 Banana：4元 - 桃子 Peach：2元 - 梨 Pear：3元 - 找到一種水果的價格： - 可以使用 binary search，通過名稱來查找，耗 ...
數據結構 in Golang：Hash Tables（哈希表）
場景
- 水果店的價格表：
- 蘋果 Apple：3元
- 香蕉 Banana：4元
- 桃子 Peach：2元
- 梨 Pear：3元
- 找到一種水果的價格：
- 可以使用 binary search，通過名稱來查找，耗時：O(logn)
- 如何只耗時 O(1) 來找到價格呢？
Hash 函數
- Hash 函數：通過一個字元串 -> 一個數值
- 例如：
- "Apple" -> 1
- "Banana" -> 2
- "Peach" -> 7
- "Pear" -> 8
- 將字元串映射為數值
Hash 函數的要求
- 一致性
- 將不同的字元串映射為不同的數值
Hash 函數有什麼用？
方便 快捷的得到自己想要的值...
Hash Table
- Hash 函數 + 數組 = Hash Table
- 數組直接映射到記憶體
- Hash Table 具有額外的邏輯，它使用 Hash 函數智能的找到存放元素的位置
- 在 Go 語言中叫 Map
package main
func main() {
dict := make(map[string]int)
dict1 := map[string]int{"Apple": 3, "Orange": 4}
}
- 其它語言中：Dictionary、Map、Hash Map......
使用場景
- 電話簿
- DNS 解析
- 緩存
衝突
- 衝突就是：兩個 Key 被安排到了同一個位置
- 也就是說：K1 != K2，但 H(K1) == H(K2)
解決衝突
- 開放地址法、再 Hash 法、建立公共溢出區 ...
- 鏈地址法：鏈表
註意：
- Hash 函數應儘可能的將 Key 平均的映射
- 如果鏈表過長，會讓 Hash Table 變得很慢
選擇 Hash 函數
| Hash Table 平均 | Hash Table 最壞 | 數組 | 鏈表 | |
|---|---|---|---|---|
| 查找 | O(1) | O(n) | O(1) | O(n) |
避免衝突
- 裝載因數（load factor）要低
- 一個好的 Hash 函數
裝載因數（load factor）
- 調整大小，Resize
- 例如：load factor 為 75% 的時候，就可以調整大小，通常是原來大小的兩倍
- 註意：調整大小也會花費很多時間
選擇好的 Hash 函數
- 好的 Hash 函數會將值儘可能的平均分佈在數組中
- 不好的 Hash 函數經常會把值聚集，並產生很多衝突
- 通常不需要自己編寫 Hash 函數，可以瞭解 SHA 函數
本文來自博客園，作者：尋月隱君，轉載請註明原文鏈接：https://www.cnblogs.com/QiaoPengjun/p/17464792.html
