Go映射(map)实战

本文翻译自《Go maps in action》。

Andrew Gerrand

2013/02/06

介绍

哈希表是计算机科学中最有用的数据结构之一。许多哈希表的实现具有不同的属性,但通常它们都提供快速查找、添加和删除这些功能。Go提供了实现哈希表的内置的map类型。

定义和初始化

Go的map类型如下所示:

map[KeyType]ValueType

其中KeyType可以是任何可比较的类型(稍后将详细介绍),ValueType可以是任何类型,包括另一个map!

此变量m是字符串键到int值的映射:

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是一个布尔值,如果键存在于map中则为真,否则为假。

要在不检索值的情况下测试键是否存在,可以使用下划线来省略第一个返回值:

_, 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)。此示例遍历链接列表的Nodes并打印它们的值。它使用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)
    }

如果n已被访问,表达式visited[n]为true,如果n不存在则为false。无需使用二值形式来测试map中是否存在n;默认返回零值已经够用了。

另一个有用的零值实例是map的切片值。append到一个nil切片会分配一个新的切片,所以把一个值append到一个map的切片值无需检查键是否存在。在以下示例中,切片people填充了Person值。每个Person都有一个Name字段和一个Likes切片字段。该示例创建了一个map,将每个爱好(作为likes的键)与喜欢它的那些人(作为likes的值)相关联。

    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.")

请注意,由于rangelen都将nil切片视为零长度切片,因此即使没有人喜欢奶酪或培根(尽管不太可能),最后两个示例仍然能正常工作。

键的类型

如前所述,map的键可以是任何可比较的类型。Go语言规范对此进行了精确定义,但简而言之,可比较类型是布尔类型、数字类型、字符串类型、指针类型、通道类型和接口类型,以及仅包含这些类型的结构体或数组。值得注意的是,没有切片、map和函数,这些类型不能使用==进行比较,因此不能用作map的键。

显然,字符串、整数和其他基本类型应该可以用作map的键,但可能出乎意料的是结构体作为map的键。结构体可以从多个维度作为键。例如,以下map可用于按国家/地区统计网页点击率:

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

这个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")

我们可以使用带有结构体键的单个map的设计来消除所有的复杂性:

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

当越南人访问主页时,增加(并可能创建)适当的计数器,使用一行代码就能实现:

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

同样,看看有多少瑞士人看过/ref/spec网页:

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

并发

map对于并发使用是不安全的:Go没有定义当你同时读取和写入它们时会发生什么。如果你需要从并发执行的goroutine读取和写入map,则访问必须通过某种同步机制进行调解。保护map的一种常见方法是使用sync.RWMutex

此语句声明一个counter变量,它是一个包含map和内嵌sync.RWMutex的匿名结构体。

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

要从counter读取,请获取读锁:

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

要写入counter,请获取写锁:

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

迭代顺序

使用range循环遍历map时,Go语言没有指定迭代顺序,并且不保证从一次迭代到下一次迭代是相同顺序的。如果你需要稳定的迭代顺序,则必须维护一个单独的数据结构来指定该顺序。以下例子使用单独排序的键切片,来按键在切片里的顺序打印输出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])
}