Go: 通過例子學習 Map 的設計 — Part I
本文是三篇系列文章中的第一篇。每篇文章都將涵蓋 map 的不同部分。我建議你按順序閱讀。
Go 提供的內置類型 map 是使用哈希表 [1] 實現的。在本文中，我們將探討這個哈希表的不同部分的具體實現：桶（存儲鍵值對的數據結構），哈希（鍵值對的索引），負載因子（判斷 map 是否應該擴容的指標）。
桶
Go 將鍵值對存儲在桶的列表中，每個桶容納 8 個鍵值對，當 map 的容量耗盡，哈希桶的數量將會翻倍。下面是持有 4 個桶的 map 的粗略示圖：
map with a list of buckets
在下一篇文章中，我們將看到這些鍵值對是如何在桶裏存儲的。如果 map 再一次擴容，桶的數量將會翻倍，依次增加到 8，16，等等。
當一個鍵值對存入 map，它將根據鍵計算出的哈希值，被分配到一個桶裏。
哈希
當一個鍵值對被存放到 map 中，Go 會根據它的鍵生成哈希值。
讓我們以鍵值對 "foo" = 1 的插入作爲例子。生成的哈希值可能是 15491954468309821754。該值將應用於位操作，掩碼對應於桶的數量減 1。在我們的 4 個桶的例子中，掩碼是 3，位操作如下：
value dispatched in the buckets
哈希值不僅用於值在桶中的分配，還參與其他的操作。每個桶都將其哈希值的首字節存儲在一個內部數組中，這使得 Go 可以對鍵進行索引，並跟蹤桶中的空槽。讓我們看一下二進制表示下，哈希的例子：
top hash table in bucket
多虧了桶內部被稱爲 top hash 的表，Go 可以在數據訪問期間使用它們與請求鍵的哈希值進行比較。
根據我們在程序中對 map 的使用，Go 需要對 map 進行擴容，以便管理更多的鍵值對。
Map 擴容
在存儲鍵值對時，桶會將它存儲在 8 個可用的插槽中。如果這些插槽全部不可用，Go 會創建一個溢出桶，並與當前桶連接。
overflow bucket
這個 overflow 屬性表明了桶的內部結構。然而，增加溢出桶會降低 map 的性能。作爲彌補，Go 將會分配新的桶（當前桶的數量的兩倍），保存一箇舊桶和新桶之間的連接，逐步將舊桶遷移到新桶中。實際上，在這次新的分配之後，每個參與過寫操作的桶，如果操作還未完成，都將被遷移。被遷移的桶中的所有鍵值對都將被重新分配到新桶中，這意味着，先前同一個桶中存儲在一起的鍵值對，現在可能被分配到不同的桶中。
Go 使用負載因子來判斷何時開始分配新桶並遷移舊桶。
負載因子
Go 在 map 中使用 6.5 作爲負載因子。你可以在代碼中看到與負載因子相關的研究：
// Picking loadFactor: too large and we have lots of overflow
// buckets, too small and we waste a lot of space. I wrote
// a simple program to check some stats for different loads:
// (64-bit, 8 byte keys and values)
// loadFactor %overflow bytes/entry hitprobe missprobe
// 4.00 2.13 20.77 3.00 4.00
// 4.50 4.05 17.30 3.25 4.50
// 5.00 6.85 14.77 3.50 5.00
// 5.50 10.55 12.94 3.75 5.50
// 6.00 15.27 11.67 4.00 6.00
// 6.50 20.90 10.79 4.25 6.50
// 7.00 27.14 10.15 4.50 7.00
// 7.50 34.03 9.73 4.75 7.50
// 8.00 41.10 9.40 5.00 8.00
//
// %overflow = percentage of buckets which have an overflow bucket
// bytes/entry = overhead bytes used per key/value pair
// hitprobe = # of entries to check when looking up a present key
// missprobe = # of entries to check when looking up an absent key如果桶中鍵值對的平均容量超過 6.5，map 將會擴容。考慮到基於鍵的哈希值的分配並不均勻，正如我們在以上研究中看到的，使用 8 作爲負載因子會導致大量的溢出桶。
這個系列的下一篇文章，將會講解 map 的內部實現。
via: https://medium.com/@blanchon.vincent/go-map-design-by-example-part-i-3f78a064a352
作者：blanchon.vincent[2] 譯者：DoubleLuck[3] 校對：polaris1119[4]
本文由 GCTT[5] 原創編譯，Go 中文網 [6] 榮譽推出，發佈在 Go 語言中文網公衆號，轉載請聯繫我們授權。
參考資料
[1]
哈希表: https://en.wikipedia.org/wiki/Hash_table
[2]
blanchon.vincent: https://medium.com/@blanchon.vincent
[3]
DoubleLuck: https://github.com/DoubleLuck
[4]
polaris1119: https://github.com/polaris1119
[5]
GCTT: https://github.com/studygolang/GCTT
[6]
Go 中文網: https://studygolang.com/
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/YwsemMCuPmeqeWBTIe3PWQ