哈希表是一种非常好用、适用面很广的数据结构,是key-value对的无序集合。它的key是唯一的,通过key可以在常数复杂度时间内进行查询、更新或删除,无论哈希表有多大。
Go语言的map类型就是对哈希表的引用,表示为map[key]value。map中所有的key都是相同的类型,所有的value也是相同的类型,不过key和value可以是不同的类型。key代表的数据类型必须支持==和!=运算符,这样map才能检测指定的key是否已经存在。虽然浮点数支持相等运算符,但是正如我们在第二章提到的,浮点数是不精确的,因此用它做key,不是个好想法,甚至最坏的情况可能发生用NaN来进行比较。value的数据类型是没有限制的。
使用内置函数make创建map:
ages := make(map[string]int) // mapping from strings to ints
也可以使用类似slice语法来创建map:
ages := map[string]int{
"alice": 31,
"charlie": 34,
}
这相当于:
ages := make(map[string]int)
ages["alice"] = 31
ages["charlie"] = 34
还可以通过map[string]int{}来创建空map。
Map中的元素可以通过key来访问:
ages["alice"] = 32
fmt.Println(ages["alice"]) // "32"
使用内置的delete函数可以删除元素:
delete(ages, "alice") // remove element ages["alice"]
上面的所有操作都是安全的,不用担心报错,即使map中不存在相应的元素!查询失败时将返回value类型对应的零值,例如,虽然map中并不存在"bob",但是下面的代码仍然可以正常工作,因为ages["bob"]会返回0:
ages["bob"] = ages["bob"] + 1 // happy birthday!
x += y和 x++ 等短赋值语法也可以用在map上:
ages["bob"] += 1
更简洁的版本:
ages["bob"]++
有一点很重要:map中的元素不是变量,因此不能寻址!!
_ = &ages["bob"] // compile error: cannot take address of map element
不能寻址的原因是:map可能会随着元素的增多重新分配更大的内存空间,旧值都会拷贝到新的内存空间,因此之前的地址就会失效。
可以使用for...range来遍历map中的所有key-value对,这个类似slice的遍历语法,下面的代码中map的key是name,map的value是age:
for name, age := range ages {
fmt.Printf("%s\t%d\n", name, age)
}
Map的迭代顺序是不确定的,而且不同的哈希算法会导致不同的迭代顺序。在实际应用中,遍历的顺序是随机的,甚至每次的遍历顺序可能都不相同。Go语言是有意这么实现的,使用随机的遍历顺序可以避免程序依赖于某种哈希实现,让程序更加强壮。如果要按顺序遍历,必须显式对key排序,可以使用sort包的String函数:
import "sort"
var names []string
for name := range ages {
names = append(names, name)
}
sort.Strings(names)
for _, name := range names {
fmt.Printf("%s\t%d\n", name, ages[name])
}
我们可以获取map中key的数目,因此可以提前给slice分配一个合适的大小,避免内存分配和拷贝。下面的代码创建了一个空的slice,容量刚好可以放下map中所有的key:
names := make([]string, 0, len(ages))
在上面的第一个range循环中,我们只关心具体的key,所以忽略了第二个变量。在第二个循环中,我们只关心value,所以使用'_'空白标识符来忽略第一个变量。
map是引用类型,对应的零值是nil,这时表示map没有引用任何哈希表。
var ages map[string]int
fmt.Println(ages == nil) // "true"
fmt.Println(len(ages) == 0) // "true"
map中的大部分操作:查询、删除、len和range都可以安全地工作在nil map上,nil map的行为和空map类似。但是,向nil map中添加元素时将导致panic:
ages["carol"] = 21 // panic: assignment to entry in nil map
因此,向map中添加数据前,必须先初始化map。
对map的查询总是会成功的。如果key在map中存在,那么获取相应的value;如果key不存在,获取对应value类型的零值,正如之前的ages["bob"]。在一些情况下,这样的机制是没问题的,但是有时候我们需要知道要查询的元素是否真的存在,例如value是int类型时,查询的返回值0就很令人迷惑,到底是value的值就是0呢还是key不存在返回的零值。可以使用下面的方法:
age, ok := ages["bob"]
if !ok { /* "bob" is not a key in this map; age == 0. */ }
也可以结合起来使用:
if age, ok := ages["bob"]; !ok { /* ... */ }
上面的场景下,map的访问产生了两个值,第一个值是value,第二个值是个布尔值,用于报告元素是否存在。布尔变量一般声明为ok,这样在if中使用时意义会非常明确。
和slice一样,map之间也不能进行相等比较,唯一的例外是和nil比较。如果要判断两个map是否相等,我们必须自己实现:
func equal(x, y map[string]int) bool {
if len(x) != len(y) {
return false
}
for k, xv := range x {
if yv, ok := y[k]; !ok || yv != xv {
return false
}
}
return true
}
要注意上面代码中必须用ok来判断y中的元素是否存在,不能简单的用xv != y[k]来判断,不然可能会导致错误的结果:
// True if equal is written incorrectly.
equal(map[string]int{"A": 0}, map[string]int{"B": 42})
Go语言没有set类型,不过我们可以使用map来实现set,利用map中的key是唯一的这个特性。debup程序会读取多行输入,然后打印出第一次出现的行,这里使用map来做所有输入行的集合,确保已经存在的行不会被重复打印:
func main() {
seen := make(map[string]bool) // a set of strings
input := bufio.NewScanner(os.Stdin)
for input.Scan() {
line := input.Text()
if !seen[line] {
seen[line] = true
fmt.Println(line)
}
}
if err := input.Err(); err != nil {
fmt.Fprintf(os.Stderr, "dedup: %v\n", err)
os.Exit(1)
}
}
Go程序员经常利用上面这种编程范式来实现集合。
有的时候我们需要key为slice类型的map,但是因为map的key必须是可比较的,因此slice并不满足条件。不过可以通过映射来解决,首先,定义一个辅助函数k,将slice映射为字符串,确保只有x和y相等时,k(x) == k(y);其次,使用slice时,将slice转换为字符串,再作为map的key使用。
下面的例子中,使用map来记录Add函数的调用次数,这里使用了fmt.Sprintf将字符串列表转换为一个字符串,然后用于map的key,使用%q参数可以给输出的字符串加上双引号:
var m = make(map[string]int)
func k(list []string) string { return fmt.Sprintf("%q", list) }
func Add(list []string) { m[k(list)]++ }
func Count(list []string) int { return m[k(list)] }
使用类似的思想可以处理任何不可比较的key类型,不仅仅是slice。对于可比较的类型,也可以使用上面的思想来实现自定义的比较函数,例如比较字符串时忽略大小写,而不是直接用==比较。同时,k(x)也未必要返回字符串类型,可以返回任何可比较的类型,例如整形、浮点、结构体等。
再看另外一个例子,统计输入中每个Unicode码点出现的次数。虽然Unicode的全部码点(int32)数量巨大,但是实际世界中已使用的码点值并不多,因此这里可以使用map来追踪码点的个数:
// Charcount computes counts of Unicode characters.
package main
import (
"bufio"
"fmt"
"io"
"os"
"unicode"
"unicode/utf8"
)
func main() {
counts := make(map[rune]int) // counts of Unicode characters
var utflen [utf8.UTFMax + 1]int // count of lengths of UTF-8 encodings
invalid := 0 // count of invalid UTF-8 characters
in := bufio.NewReader(os.Stdin)
for {
r, n, err := in.ReadRune() // returns rune, nbytes, error
if err == io.EOF {
break
}
if err != nil {
fmt.Fprintf(os.Stderr, "charcount: %v\n", err)
os.Exit(1)
}
if r == unicode.ReplacementChar && n == 1 {
invalid++
continue
}
counts[r]++
utflen[n]++
}
fmt.Printf("rune\tcount\n")
for c, n := range counts {
fmt.Printf("%q\t%d\n", c, n)
}
fmt.Print("\nlen\tcount\n")
for i, n := range utflen {
if i > 0 {
fmt.Printf("%d\t%d\n", i, n)
}
}
if invalid > 0 {
fmt.Printf("\n%d invalid UTF-8 characters\n", invalid)
}
}
ReadRune会执行UTF-8解码并返回三个值:解码后的rune值、rune经过UTF-8编码后的字节长度以及一个错误值,文件的结尾io.EOF是我们唯一预期的错误值。如果输入不是合法的UTF-8编码字符,那么返回的将是unicode.ReplacementChar字符,且编码长度为1。
charcount还会统计各个UTF-8编码长度对应的字符数目,对此,map并不合适,因为UTF-8编码的长度只有1、2、3、4 四种情况,因此更适合使用数组(数组在内存中是连续排列的,读取性能高很多)。
作为一个实验,我们可以使用charcount程序对本书的英文版进行统计(gopl.io)。虽然书中大部分是英文字符,但是也有一些非ASCII字符。下面是排名前10的非ASCII字符:
下面是不同UTF-8编码长度对应的字符数目:
len count
1 765391
2 60
3 70
4 0
map的value也可以是聚合类型,例如map或slice。在下面的代码中,graph的key是字符串类型,value的类型是map[string]bool,代表一个字符串集合。这里,graph将一个字符串key映射到一个字符串集合。
gopl.io/ch4/graph
var graph = make(map[string]map[string]bool)
func addEdge(from, to string) {
edges := graph[from]
if edges == nil {
edges = make(map[string]bool)
graph[from] = edges
}
edges[to] = true
}
func hasEdge(from, to string) bool {
return graph[from][to]
}
addEdge展现了一个理想的惰性初始化map的方式,也就是只在key第一次出现时才初始化value的值。函数还展示了如何让map的零值也能正常工作:即使from到to的边不存在,graph[from][to]依然可以返回一个有意义的结果。
练习 4.8: 修改charcount程序,使用unicode.IsLetter等函数,统计字母、数字等不同类别字符出现的个数。
练习 4.9: 编写wordfreq程序,统计输入文本中每个单词出现的频率,在第一次调用Scan前先调用input.Split(bufio.ScanWords)函数,把输入按自此分割而不是按行分割。
文章所有权:Golang隐修会 联系人:孙飞,CTO@188.com!
有疑问加站长微信联系(非本文作者)