Go 部落格

Go map 實戰

Andrew Gerrand
2013 年 2 月 6 日

引言

雜湊表是計算機科學中最有用的資料結構之一。存在許多具有不同特性的雜湊表實現，但總的來說，它們提供了快速的查詢、新增和刪除操作。Go 提供了一種內建的 map 型別，它實現了雜湊表。

宣告和初始化

Go map 型別看起來像這樣

map[KeyType]ValueType

其中 KeyType 可以是任何可比較的型別（稍後會詳細介紹），而 ValueType 可以是任何型別，包括另一個 map！

這個變數 m 是一個以 string 為鍵、int 為值的 map

var m map[string]int

map 型別是引用型別，類似於指標或切片，因此上面變數 m 的值是 nil；它不指向一個已初始化的 map。一個 nil map 在讀取時行為類似於一個空 map，但嘗試寫入 nil map 會導致執行時 panic；不要那樣做。要初始化一個 map，使用內建的 make 函式

m = make(map[string]int)

make 函式分配並初始化一個雜湊 map 資料結構，並返回一個指向它的 map 值。該資料結構的具體細節是執行時的實現細節，語言本身並未指定。在本文中，我們將重點介紹 map 的使用，而不是它們的實現。

使用 map

Go 提供了使用 map 的常用語法。這條語句將鍵 "route" 設定為值 66

m["route"] = 66

這條語句檢索儲存在鍵 "route" 下的值，並將其賦值給一個新變數 i

i := m["route"]

如果請求的鍵不存在，我們將獲得值型別的零值。在這種情況下，值型別是 int，所以零值是 0

j := m["root"]
// j == 0

內建的 len 函式返回 map 中的項數

n := len(m)

內建的 delete 函式從 map 中刪除一個條目

delete(m, "route")

delete 函式不返回任何內容，如果指定的鍵不存在，它什麼也不做。

兩值賦值用於測試鍵是否存在

i, ok := m["route"]

在此語句中，第一個值 (i) 被賦值為儲存在鍵 "route" 下的值。如果該鍵不存在，i 是值型別的零值 (0)。第二個值 (ok) 是一個 bool 型別，如果鍵存在於 map 中，則為 true，否則為 false。

要測試鍵是否存在而不檢索其值，請在第一個值的位置使用下劃線

_, ok := m["route"]

要遍歷 map 的內容，使用 range 關鍵字

for key, value := range m {
    fmt.Println("Key:", key, "Value:", value)
}

要使用一些資料初始化 map，使用 map 字面量

commits := map[string]int{
    "rsc": 3711,
    "r":   2138,
    "gri": 1908,
    "adg": 912,
}

可以使用相同的語法初始化一個空 map，這在功能上與使用 make 函式是相同的

m = map[string]int{}

利用零值

當鍵不存在時，map 檢索會產生一個零值，這可能很方便。

例如，一個布林值 map 可以用作集合狀資料結構（回想一下，布林型別的零值是 false）。此示例遍歷由 Node 組成的連結串列並列印它們的值。它使用一個 Node 指標 map 來檢測列表中的迴圈。

    type Node struct {
        Next  *Node
        Value interface{}
    }
    var first *Node

    visited := make(map[*Node]bool)
    for n := first; n != nil; n = n.Next {
        if visited[n] {
            fmt.Println("cycle detected")
            break
        }
        visited[n] = true
        fmt.Println(n.Value)
    }

表示式 visited[n] 如果 n 已被訪問，則為 true，如果 n 不存在，則為 false。無需使用兩值形式來測試 n 是否存在於 map 中；零值預設行為就幫我們做到了。

另一個有用的零值例子是 slice map。向 nil slice 追加元素只會分配一個新的 slice，因此向 slice map 追加一個值只需一行程式碼；無需檢查鍵是否存在。在下面的示例中，slice people 填充了 Person 值。每個 Person 都有一個 Name 和一個 Likes slice。該示例建立一個 map，將每個 like 與喜歡它的人的 slice 關聯起來。

    type Person struct {
        Name  string
        Likes []string
    }
    var people []*Person

    likes := make(map[string][]*Person)
    for _, p := range people {
        for _, l := range p.Likes {
            likes[l] = append(likes[l], p)
        }
    }

列印喜歡乳酪的人列表

    for _, p := range likes["cheese"] {
        fmt.Println(p.Name, "likes cheese.")
    }

列印喜歡培根的人數

    fmt.Println(len(likes["bacon"]), "people like bacon.")

注意，由於 range 和 len 都將 nil slice 視為零長度 slice，所以即使沒有人喜歡乳酪或培根（儘管這種可能性很小），最後這兩個示例也會正常工作。

鍵型別

如前所述，map 鍵可以是任何可比較的型別。語言規範精確定義了這一點，但簡而言之，可比較型別包括布林型、數值型、字串型、指標型、channel 型別和介面型別，以及僅包含這些型別的 struct 或 array。列表中明顯缺少的是 slice、map 和 function；這些型別不能使用 == 進行比較，也不能用作 map 鍵。

顯然，字串、int 和其他基本型別可以用作 map 鍵，但可能出乎意料的是 struct 鍵。Struct 可以用於按多個維度對資料進行鍵控。例如，這個 map 的 map 可以用來按國家統計網頁訪問量

hits := make(map[string]map[string]int)

這是一個 string 到 (string 到 int 的 map) 的 map。外部 map 的每個鍵都是網頁路徑，其對應的值是它自己的內部 map。每個內部 map 的鍵是一個兩字母的國家程式碼。這個表示式檢索澳大利亞使用者載入文件頁面的次數

n := hits["/doc/"]["au"]

不幸的是，當新增資料時，這種方法會變得笨拙，因為對於任何給定的外部鍵，您都必須檢查內部 map 是否存在，並在需要時建立它

func add(m map[string]map[string]int, path, country string) {
    mm, ok := m[path]
    if !ok {
        mm = make(map[string]int)
        m[path] = mm
    }
    mm[country]++
}
add(hits, "/doc/", "au")

另一方面，使用帶有 struct 鍵的單個 map 的設計消除了所有這些複雜性

type Key struct {
    Path, Country string
}
hits := make(map[Key]int)

當越南使用者訪問主頁時，遞增（並可能建立）相應的計數器只需一行程式碼

hits[Key{"/", "vn"}]++

同樣直觀地可以看到有多少瑞士人閱讀了規範

n := hits[Key{"/ref/spec", "ch"}]

併發

map 不是併發安全的：同時讀寫 map 時會發生什麼行為並未定義。如果您需要從併發執行的 goroutine 中讀寫 map，則必須透過某種同步機制協調訪問。保護 map 的一種常見方法是使用 sync.RWMutex。

此語句聲明瞭一個 counter 變數，它是一個包含一個 map 和一個嵌入式 sync.RWMutex 的匿名 struct。

var counter = struct{
    sync.RWMutex
    m map[string]int
}{m: make(map[string]int)}

要從計數器讀取，獲取讀鎖

counter.RLock()
n := counter.m["some_key"]
counter.RUnlock()
fmt.Println("some_key:", n)

要向計數器寫入，獲取寫鎖

counter.Lock()
counter.m["some_key"]++
counter.Unlock()

迭代順序

當使用 range 迴圈迭代 map 時，迭代順序是未指定的，並且不能保證從一次迭代到下一次迭代保持一致。如果您需要穩定的迭代順序，必須維護一個單獨的資料結構來指定該順序。此示例使用一個單獨的有序鍵 slice 來按鍵順序列印 map[int]string

import "sort"

var m map[int]string
var keys []int
for k := range m {
    keys = append(keys, k)
}
sort.Ints(keys)
for _, k := range keys {
    fmt.Println("Key:", k, "Value:", m[k])
}