吃透 Golang 基础：数据结构之 Map

Map

Hash Map 是无序的 key/value 对集合，其中所有的 key 都是不同的。通过给定的 key 可以在常数时间复杂度内完成检索、更新或删除对应的 value（基于 Hash Map 的增删改查操作时间复杂度为$ O(1) $）

概述

Go 中的 map 就是一个 Hash Map 的引用，map 类型可以写为 map[K]V，其中K和V分别对应 key 和 value。map 中所以 key 可以是相同类型，所以 value 可以是相同类型，但 key 和 value 的类型可以不同。需要注意的是，K对应的 key 必须支持==比较运算符，这样 map 就可以通过测试 key 是否相等来判断传入的 key 是否已经存在。另一个要注意的点是最好不要使用浮点数作为 key，因为浮点数的比较是不准确的。value 的类型没有任何限制。

初始化

可以使用内置的 make 函数创建一个 map（make 只能用于创建 slice/map/channel）：

ages := make(map[string]int)

也可以使用字面值语法来创建一个新的 map，同时可以指定初始的 key/value：

ages := map[string]int{"yggp": 24,"ed": 24,
}// 上述方式等价于
ages := map[string]int{}
ages["yggp"] = 24
ages["ed"] = 24fmt.Println(ages["yggp"])	// 访问 map 当中的元素时可以通过 key 对应的下标来访问

删除

可以使用内置的 delete 函数删除元素：

delete(ages, "ed")	// remove element ages["ed"]

通过内置的 delete，将会直接删除 ages 这个 map 当中的 key/value。在 LeetCode 的 LRU Cache 这道题当中就会用到 delete 来删除 Cache 当中最近最久未使用的 key/value。

访问不存在的 key 返回 value 的零值

上述所有的增/删/改/查操作都是安全的，即使这些元素不在操作的 map 当中。如果一个 key 的查找失败了，那么将直接返回 value 对应的零值，比如ages["kevin"]的查找结果将直接返回 int 类型的零值0。对于ages["kevin"] = ages["kevin"] + 1这样的语句也是可以正常执行的，该语句自右向左执行，最终ages["kevin"]的值为 1。+=和++也可以用于 value 为整型的 map 上。

需要注意的是，map 中的元素不是一个变量，因此我们不能对 map 的元素进行取址操作：

// ❌非法的取址操作, compile error
_ = &ages["ed"]

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

遍历 map

可以通过 range 风格的 for 循环来遍历 map 中的 key/value pair：

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

map 的迭代顺序是不确定的，在实践中，遍历的顺序是随机的，也就是每一次遍历的顺序都不相同。因此，Go 的 map 是无序的，如果想要有序，可以首先取出所有的 key 到 slice 当中，然后再对 slice 进行排序，用 slice 当中排序后的结果索引 map 当中的 value。

map 自身的零值

map 类型的零值是 nil，也就是没有任何引用的 Hash Map。

var ages map[string]int
fmt.Println(ages == nil)	// true
fmt.Println(len(ages) == 0)	// true, 意味着 nil 的 map 长度为 0

map 上的大部分操作，包括查找、删除、len 和 range 循环都可以安全工作在 nil 的 map 上，但是试图向 nil 的 map 增加值会导致 panic。也就是说，向 map 当中存数据之前必须先创建好 map。

map 索引时返回的第二个参数

我们已经知道，通过 key 作为索引下标来访问 map 会产生一个 value。无论 key/value pair 之前是否已经记录在了 map 当中，都会产生相应的结果：如果 key 存在，则返回对应的 value 值，否则返回 value 类型的零值。有些情况下我们想要确切地知道 key/value 是否存在于 map 当中，这个时候就可以用到 map 索引返回的第二个参数：

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

上面代码块的ok就是第二个参数，它是一个 bool 值，代表 key 对应的 value 是否存在于 map 当中。

和 slice 一样，map 与 map 之间是不可比较的，map 本身只能和 nil 进行比较，来判断 map 是否引用了 Hash Map。如果想要比较两个类型相同的 map，唯一的方法就是逐 key/value 进行比较。

使用 map 实现 set

Go 当中没有 set 类型，但是我们可以通过 map 来模拟一个 set 类型。一种常见的 set 声明方法是：

// ... ... ...
st := make(map[string]bool)
// ... ... ...

可以使用忽略 value 的 map 作为一个 string 类型的 set，关键在于通过 map 查找返回的第二个参数 ok 来判断当前 key 是否已经存在于 map 当中，这恰好模拟了 set 的效果。

最开始的时候我们已经提到 map 的 value 类型可以是任何类型，比如 map 或 slice。下面的例子来自于《Go 语言圣经》，graph 是一个 map，它的 key 是 string，value 类型是 map[string]bool，代表一个字符串集合。具体来说，graph 将 string 类型的 key 映射到一组相关的 string set：

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 时才初始化。hasEdge 显示了如何让 map 的零值也能正常工作：即使 from 到 to 的边不存在，graph[from][to]仍然可以返回 bool 的零值 false 作为有意义的结果。