Map

哈希表是一种巧妙并且实用的数据结构。它是一个无序的 key/value 对的集合，其中所有的 key 都是不同的，然后通过给定的 key 可以在常数时间复杂度内检索、更新或删除对应的 value 。

在 Go 语言中，一个 map 就是一个哈希表的引用，map 类型可以写为 map[K]V ，其中 K 和 V 分别对应 key 和 value 。map 中所有的 key 都有相同的类型，所有的 value 也有着相同的类型，但是 key 和 value 之间可以是不同的数据类型。其中 K 对应的 key 必须是支持 == 比较运算符的数据类型，所以 map 可以通过测试 key 是否相等来判断是否已经存在。虽然浮点数类型也是支持相等运算符比较的，但是将浮点数用做 key 类型则是一个坏的想法，正如第三章提到的，最坏的情况是可能出现的 NaN 和任何浮点数都不相等。对于 V 对应的 value 数据类型则没有任何的限制。

内置的 make 函数可以创建一个 map ：

ages := make(map[string]int) // mapping from strings to ints

我们也可以用 map 字面值的语法创建 map ，同时还可以指定一些最初的 key/value ：

ages := map[string]int{
    "alice":   31,
    "charlie": 34,
}

这相当于：

ages := make(map[string]int)
ages["alice"] = 31
ages["charlie"] = 34

因此，另一种创建空的 map 的表达式是 map[string]int{} 。

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 中的元素并不是一个变量，因此我们不能对 map 的元素进行取址操作：

_ = &ages["bob"] // compile error: cannot take address of map element

禁止对 map 元素取址的原因是 map 可能随着元素数量的增长而重新分配更大的内存空间，从而可能导致之前的地址无效。

要想遍历 map 中全部的 key/value 对的话，可以使用 range 风格的 for 循环实现，和之前的 slice 遍历语法类似。下面的迭代语句将在每次迭代时设置 name 和 age 变量，它们对应下一个键/值对：

for name, age := range ages {
    fmt.Printf("%s\t%d\n", name, age)
}

Map 的迭代顺序是不确定的，并且不同的哈希函数实现可能导致不同的遍历顺序。在实践中，遍历的顺序是随机的，每一次遍历的顺序都不相同。这是故意的，每次都使用随机的遍历顺序可以强制要求程序不会依赖具体的哈希函数实现。如果要按顺序遍历 key/value 对，我们必须显式地对 key 进行排序，可以使用 sort 包的 Strings 函数对字符串 slice 进行排序。下面是常见的处理方式：

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

因为我们一开始就知道 names 的最终大小，因此给 slice 分配一个合适的大小将会更有效。下面的代码创建了一个空的 slice ，但是 slice 的容量刚好可以放下 map 中全部的 key ：

names := make([]string, 0, len(ages))

在上面的第一个 range 循环中，我们只关心 map 中的 key ，所以我们忽略了第二个循环变量。在第二个循环中，我们只关心 names 中的名字，所以我们使用 “_” 空白标识符来忽略第一个循环变量，也就是迭代 slice 时的索引。

map 类型的零值是 nil，也就是没有引用任何哈希表。

var ages map[string]int
fmt.Println(ages == nil)    // "true"
fmt.Println(len(ages) == 0) // "true"

map 上的大部分操作，包括查找、删除、len 和 range 循环都可以安全工作在 nil 值的 map 上，它们的行为和一个空的 map 类似。但是向一个 nil 值的 map 存入元素将导致一个 panic 异常：

ages["carol"] = 21 // panic: assignment to entry in nil map

在向 map 存数据前必须先创建 map 。

通过 key 作为索引下标来访问 map 将产生一个 value 。如果 key 在 map 中是存在的，那么将得到与 key 对应的 value ；如果 key 不存在，那么将得到 value 对应类型的零值，正如我们前面看到的 ages["bob"] 那样。这个规则很实用，但是有时候可能需要知道对应的元素是否真的是在 map 之中。例如，如果元素类型是一个数字，你可能需要区分一个已经存在的 0 ，和不存在而返回零值的 0 ，可以像下面这样测试：

age, ok := ages["bob"]
if !ok { /* "bob" is not a key in this map; age == 0. */ }

你会经常看到将这两个结合起来使用，像这样：

if age, ok := ages["bob"]; !ok { /* ... */ }

在这种场景下，map 的下标语法将产生两个值；第二个是一个布尔值，用于报告元素是否真的存在。布尔变量一般命名为 ok ，特别适合马上用于 if 条件判断部分。

和 slice 一样，map 之间也不能进行相等比较；唯一的例外是和 nil 进行比较。要判断两个 map 是否包含相同的 key 和 value ，我们必须通过一个循环实现：

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 来区分元素不存在，与元素存在但为 0 的。我们不能简单地用 xv != y[k] 判断，那样会导致在判断下面两个 map 时产生错误的结果：

// True if equal is written incorrectly.
equal(map[string]int{"A": 0}, map[string]int{"B": 42})

Go 语言中并没有提供一个 set 类型，但是 map 中的 key 也是不相同的，可以用 map 实现类似 set 的功能。为了说明这一点，下面的 dedup 程序读取多行输入，但是只打印第一次出现的行。（它是1.3节中出现的 dup 程序的变体。）dedup 程序通过 map 来表示所有的输入行所对应的 set 集合，以确保已经在集合存在的行不会被重复打印。

ch4/dedup

Unresolved include directive in modules/ROOT/pages/ch4/ch4-03.adoc - include::example$/ch4/dedup/main.go[]

Go 程序员将这种忽略 value 的 map 当作一个字符串集合，并非所有 map[string]bool 类型 value 都是无关紧要的；有一些则可能会同时包含 true 和 false 的值。

有时候我们需要一个 map 或 set 的 key 是 slice 类型，但是 map 的 key 必须是可比较的类型，但是 slice 并不满足这个条件。不过，我们可以通过两个步骤绕过这个限制。第一步，定义一个辅助函数 k ，将 slice 转为 map 对应的 string 类型的 key ，确保只有 x 和 y 相等时 k(x) == k(y) 才成立。然后创建一个 key 为string 类型的 map ，在每次对 map 操作时先用 k 辅助函数将 slice 转化为 string 类型。

下面的例子演示了如何使用 map 来记录提交相同的字符串列表的次数。它使用了 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 类型。这种技术对于想使用自定义 key 比较函数的时候也很有用，例如在比较字符串的时候忽略大小写。同时，辅助函数 k(x) 也不一定是字符串类型，它可以返回任何可比较的类型，例如整数、数组或结构体等。

这是 map 的另一个例子，下面的程序用于统计输入中每个 Unicode 码点出现的次数。虽然 Unicode 全部码点的数量巨大，但是出现在特定文档中的字符种类并没有多少，使用 map 可以用比较自然的方式来跟踪那些出现过的字符的次数。

ch4/charcount

Unresolved include directive in modules/ROOT/pages/ch4/ch4-03.adoc - include::example$/ch4/charcount/main.go[]

ReadRune 方法执行 UTF-8 解码并返回三个值：解码的 rune 字符的值，字符 UTF-8 编码后的长度，和一个错误值。我们可预期的错误值只有对应文件结尾的 io.EOF 。如果输入的是无效的 UTF-8 编码的字符，返回的将是 unicode.ReplacementChar 表示无效字符，并且编码长度是 1 。

charcount 程序同时打印不同 UTF-8 编码长度的字符数目。对此，map 并不是一个合适的数据结构；因为UTF-8 编码的长度总是从 1 到 utf8.UTFMax（最大是 4 个字节），使用数组将更有效。

作为一个实验，我们用 charcount 程序对英文版原稿的字符进行了统计。虽然大部分是英语，但是也有一些非 ASCII 字符。下面是排名前 10 的非 ASCII 字符：

下面是不同 UTF-8 编码长度的字符的数目：

Map 的 value 类型也可以是一个聚合类型，比如是一个 map 或 slice 。在下面的代码中，graph 这个 map 的 key 类型是一个字符串，value 类型 map[string]bool 代表一个字符串集合。从概念上讲，graph 将一个字符串类型的 key 映射到一组相关的字符串集合，它们指向新的 graph 的 key 。

ch4/graph

Unresolved include directive in modules/ROOT/pages/ch4/ch4-03.adoc - include::example$/ch4/graph/main.go[]

其中 addEdge 函数惰性初始化 map 是一个惯用方式，也就是说在每个值首次作为 key 时才初始化。 hasEdge 函数显示了如何让 map 的零值也能正常工作；即使 from 到 to 的边不存在，graph[from][to] 依然可以返回一个有意义的结果。

练习 4.8：修改 charcount 程序，使用 unicode.IsLetter 等相关的函数，统计字母、数字等 Unicode 中不同的字符类别。

Unresolved include directive in modules/ROOT/pages/ch4/ch4-03.adoc - include::example$/ch4/exercise/main.go[]

练习 4.9：编写一个程序 wordfreq 程序，报告输入文本中每个单词出现的频率。在第一次调用 Scan 前先调用 input.Split(bufio.ScanWords) 函数，这样可以按单词而不是按行输入。

Unresolved include directive in modules/ROOT/pages/ch4/ch4-03.adoc - include::example$/ch4/exercise/main.go[]