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])
}