hash table 可能是计算机科学领域最重要的一种数据结构,不同的实现方式会有不同的特性,但通常来说都会提供快速查找、增加和删除的操作。Go 内置了一个名为 map 的 hash table 。
一个 Go map 看起来大概是这样的:
map[KeyType]ValueTypeKeyType 可以是任意 可比较 的类型(后面会介绍),ValueType 可以是任意类型,甚至是另一个 map 。
下面是一个使用 string 作为键值, int 作为值的的 map :
var m map[string]intMap 和指针以及 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])
}