【翻译】go语言中的map实战

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

业余时间翻译，水平很差，如有瑕疵，纯属无能。

原文链接

http://blog.golang.org/go-maps-in-action

1. 简介

哈希表是计算机科学中最重要的数据结构之一。许多哈希表的实现有着千差万别的特性，但是总体上他们都提供了快速查询，添加和删除功能。go语言提供了内置数据类型map。

2. 声明和初始化

map的声明格式如下：

map[KeyType] ValueType

KeyType类型必须是可以比较的，而ValueType可以是任意类型，甚至是另一个map。

以下这个m是一个键值为string，值为int的哈希表：

var m map[string]int

哈希表类型是引用类型，像指针或者切片m指向的值是nil；它没有指向一个初始化了的哈希表。一个nil哈希表在读的时候，像一个空的哈希表，但是尝试向m中写数据会引发一个运行时panic，所以别那样做。使用内置函数make初始化一个哈希表：

m = make(map[string]int)

make函数申请并初始化了一个哈希表的数据结构并且返回一个指向这个初始化好了的哈希表。　哈希表的数据结构是go本身运行时的一个实现细节，并没有被语言本身所规定【翻者补充：类似c++不同编译器如何实现虚函数一样吧】。文章中只关心哈希表的使用而非实现。

3. 使用哈希表

go中的哈希表的使用方法和其他语言相似，向哈希表中插入一个键为“route”值为66的语句为：

m["route"] = 66

查询键为“route”并且把对应的值赋给新的变量i的语句为：

i := m["route"]

如果查询的键值在哈希表中不存在，将拿到值类型的“0”值。以m为例，值类型为int，则“0”值为1：

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

len是返回哈希表中数据个数的内置函数：

n := len(m)

delete是删除哈希表中某一键值数据的内置函数：

delete(m, "route")

delete函数返回值为空，如果键值不存在则不做任何操作。

使用两个返回值的方式可以检查键值是否存在：

i, ok := m["route"]

在这个语句中，i被赋值为哈希表中键值为“route”的值。如果那个键值不存在，i被赋值为值类型中的“0”值。第二个返回值是布尔类型，如果是true，表明键值存在，否则不存在。

如果只是检查键值是否存在，则第一个返回值使用下划线“_"：

_, ok := m["route"]

如果要遍历一个哈希表中的内容，使用range关键字：

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

如果要初始化数据，使用哈希表的字面表示：

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

同样的语法可以初始化一个空的哈希表，这种用法达到的效果和make一致：

m = map[string]int{}

4. 利用“0”值　

在哈希表中查询数据，如果键值不存在，返回一个值类型的“0”值是很方便的：

It can be convenient that a map retrieval yields a zero value when the key is not present.

例如，一个布尔值的哈希表可以被用来当做一个set使用（布尔类型的“0”值是false）。下边这个例子遍历一个Node的链表并且打印他们的值，它使用了一个Node的指针为key的哈希表去判断链表中是否有环：

    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已经被访问过了，如果是假，表明还没有。这样就不需要使用两个返回值的方式去检查n是否在map中真的存在；默认的“0”值帮我们做了。

另一个有用的例子是切片的哈希表。想一个空切片中添加数据会申请一个新的切片所以想一个切片的map中append数据会只是占用一行；不需要检查key是否存在。在下边的例子中，切片用被用来存放person类型的值，每个Person有一个Name字段和一个切片，这个例子中创建了一个哈希表关联每种物品和一个喜欢他的人的切片。【做了个倒排？】

    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的People:

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

打印出喜欢bacon的人数

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

注意，这里range函数和len函数都把nil切片看做一个长度为零的切片，即使没有人喜欢cheese或者bacon，也不会有问题。

5. 键的类型

像刚才提过的，键的类型必须是可比较的。go语言的spec中准确的定义了这个要求，简而言之，可以比较的类型包括：布尔，数字，字符串，指针，消息channel，接口类型和任何包含了以上类型的结构体和数组。不在此范围的类型包括切片，哈希表和函数；这些类型不能使用 “==” 做比较，也不能被用来做哈希表的键值。

很明显字符串，整型和其他基础类型可以作为哈希表的键。意想不到的是结构体也可以作为键值，例如，这个哈希表的哈希表可以用来存放不同国家的访问数。

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

这是一个键为字符串，值为字符串到int的哈希表。最外边表的每一个键值是到达内部哈希表的路径，每个被嵌套的哈希表的键值是一个两个字母的国家码。这个表达式可以得到一个澳大利亚人访问文档页面的次数。

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

另一方面，使用结构体作为键的哈希表可以解除这种复杂性：

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

当一个越南人访问主页的时候，一行就可以搞定：

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

查看多少个瑞士人查看了spec页面的语句也很简单：

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

6. 并发

哈希表在有并发的场景并不安全：同时读写一个哈希表的后果是不确定的。如果你需要使用goroutines同时对一个哈希表做读写，对哈希表的访问需要通过某种同步机制做协调。一个常用的方法是是使用 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()

7. 遍历顺序

当使用range循环遍历一个哈希表的时候，遍历顺序是不保证稳定的。因为Go1版本将map的便利顺序随机化了，如果程序依赖之前实现中的稳定的便利顺序的话。【翻者注。。不知道怎么翻译】如果你需要一个稳定的遍历顺序，你必须维护一个独立的数据结构用来保证这个顺序。下面这个例子使用了一个独立的排序切片，按照键值顺序打印一个 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])
}

By Andrew Gerrand