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
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论