資料結構 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
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/554548.html
標籤：其他
上一篇：C++面試八股文：C++中，函式的引數應該傳值還是傳參考？
下一篇：返回列表