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

作者 Andrew Gerrand

---