推荐6-Go maps in action 翻译

概要介绍

hash table 可能是计算机科学领域最重要的一种数据结构，不同的实现方式会有不同的特性，但通常来说都会提供快速查找、增加和删除的操作。Go 内置了一个名为 map 的 hash table 。

定义和初始化

一个 Go map 看起来大概是这样的：

map[KeyType]ValueType

KeyType 可以是任意 可比较 的类型（后面会介绍），ValueType 可以是任意类型，甚至是另一个 map 。

下面是一个使用 string 作为键值， int 作为值的的 map ：

var m map[string]int

Map 和指针以及 slice 类似，属于引用类型；它并不指向任何已经初始化的 map 。一个未初始化( nil )的 map 在读取的表现很像是一个空的 map ，但是当你给它赋值（写入）的时候会引发一个运行时 panic ，所以不要这么做。你可以这样初始化一个 map ：

m = make(map[string]int)

上述代码可以初始化一个 hash map ，分配内存并且返回一个指向该 map 的指针。实现该数据结构的细节和运行方式是由 Go 语言决定的。在本文中我们只描述用法而非实现。

map 的使用

Go 的 map 语法非常简单和常见。下面是设置 key 为 "route"，值为 66 的代码：

m["route"] = 66

该行代码索引 key 值 "value" 并且赋值给变量 i。

i := m["route"]

如果 key 值找不到，那么将返回该 map 的 value 类型的零值，下面的示例代码中， map 的 value 为 int ，因此零值为 0。

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

内置的 len 函数返回 map 中元素的数量。

n := len(m)

内置的 delete 函数删除 map 中的一个元素。

delete(m, "route")

delete 函数没有返回值，删除不存在的 key 时也不会有任何特殊表现。

下面是返回两个值的赋值方式：

i, ok := m["route"]

上述代码中，如果为 "route" 的 key 存在，那么 i 将是对应的 value，否则为该 map value 类型的零值。第二个名为 ok 的变量，在指定 key 存在的时候为 true ，否则为 false 。

下面代码丢弃了返回的值，使用一个 _ 的占位符放在第一个返回值的位置。

_, ok := m["route"]

迭代 map 使用 range 关键字：

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

使用已有的值初始化一个 map ：

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

使用初始化值的语法生成一个空 map ，等效于 make 函数：

m = map[string]int{}

利用零值特性

我们可以方便的使用 key 不存在时 map 返回零值的特性。

下面的代码中，一个 value 为 boolean 的 map 起到了类似 set 的作用（ bool 类型的零值正好为 false ）。该代码遍历一个链表 Nodes 并打印，同时使用 map （key 为 Node 指针）来检测链表中的环。

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] 在访问过之后返回 true ，未访问过返回 false ，这样避免了返回两个值来检查是否访问过。我们充分利用了零值。

另外一个零值的特性是，将 slice 作为值的 map （译注: slice 的零值为 nil ），由于向一个 nil 的 slice 调用 append 函数会生成一个新的 slice ，于是可以不检查 key 是否存在，而在一行代码里面向一个 slice 为值的 map 添加新的元素。下面的代码中，每一个 Person 都有自己的 Likes，我们可以创建一个 Name 作为键，名为 Likes 的 slice 作为值的 map 。

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

打印出喜欢 "cheese" 的人名列表：

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

打印出喜欢 "bacon" 的人数：

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

由于 range 函数和 len 函数都会将一个 nil 的 slice 看做空的 slice 处理，因此上述两个示例在没有人喜欢 "cheese" 或者 "bacon" 的情况下能够正确运行。

键的类型

上文提到的 map 的键可以为任何 可比较 的类型。Go 语言规范里面精确的定义了 可比较 。简单的说，可比较的类型包括 boolean , numeric , string , pointer , channel ，以及==只==包含上述类型的 interface 、 struct 和 arrays 。典型的不可比较的类型包括 slice 、 map 和函数，这些类型无法使用 == 操作符，也不你那个作为map的键。

显然类似 string ， int 和其他的基础类型可以作为键，但是意外的， struct 也可以做为键。可以使用 struct 来实现 多维 的键值。下面的代码中，hits 这个 map 表示了按照地区统计的网页计数器：

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

hits 是一个 string 为键，一个 string 为键 int 为值的 map 作为值。外部的 map 的键为网页的 url，内部的 map 的键为地区代码。下面的代码获取到澳大利亚的用户访问 "/doc" 的次数：

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

不爽的是，如果要修改这样的数据结构会很笨拙，你需要先检查外部 key 再检查内部 key，并且在需要的时候创建一个新 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"}]++

类似的，需要查看一个瑞士用户访问某个 url 的次数可以用一下代码：

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

并发

Go 语言的 map 并不是并发安全的。在并发读写同一个 map 的时候，结果是未定义的。如果你需要在不同的执行起来的 goroutine 中读写一个 map ，那么必须要用一些同步调用的手段，其中一种是 sync.RWMutex 。

下面的代码定义了一个匿名的，包含一个 map 和一个内置读写锁（ sync.RWMutex ）的结构体。

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 ，迭代序是未定义的。同时，并不保证每次迭代序相同。Go 1.0 实现了随机、无序的迭代。早期的版本，依据不同的实现有可能是有序的，有一些依赖稳定的迭代序的代码带来了兼容性上的 bug。如果你需要一个稳定的迭代序，那么需要自己实现一个。下面示例中，使用了额外的对 key 排序的 slice 来完成有序的迭代：

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