Question

映射是一种数据结构，用于存储一系列无序的键值对。

映射里基于键来存储值。图 4-23 通过一个例子展示了映射里键值对是如何存储的。映射功能强大的地方是，能够基于键快速检索数据。键就像索引一样，指向与该键关联的值。

图 4-23　键值对的关系

4.3.1　内部实现

映射是一个集合，可以使用类似处理数组和切片的方式迭代映射中的元素。但映射是无序的集合，意味着没有办法预测键值对被返回的顺序。即便使用同样的顺序保存键值对，每次迭代映射的时候顺序也可能不一样。无序的原因是映射的实现使用了散列表，见图 4-24。

图 4-24　映射的内部结构的简单表示

映射的散列表包含一组桶。在存储、删除或者查找键值对的时候，所有操作都要先选择一个桶。把操作映射时指定的键传给映射的散列函数，就能选中对应的桶。这个散列函数的目的是生成一个索引，这个索引最终将键值对分布到所有可用的桶里。

随着映射存储的增加，索引分布越均匀，访问键值对的速度就越快。如果你在映射里存储了 10 000 个元素，你不希望每次查找都要访问 10 000 个键值对才能找到需要的元素，你希望查找键值对的次数越少越好。对于有 10 000 个元素的映射，每次查找只需要查找 8 个键值对才是一个分布得比较好的映射。映射通过合理数量的桶来平衡键值对的分布。

Go 语言的映射生成散列键的过程比图 4-25 展示的过程要稍微长一些，不过大体过程是类似的。在我们的例子里，键是字符串，代表颜色。这些字符串会转换为一个数值（散列值）。这个数值落在映射已有桶的序号范围内表示一个可以用于存储的桶的序号。之后，这个数值就被用于选择桶，用于存储或者查找指定的键值对。对 Go 语言的映射来说，生成的散列键的一部分，具体来说是低位（LOB），被用来选择桶。

图 4-25　简单描述散列函数是如何工作的

如果再仔细看看图 4-24，就能看出桶的内部实现。映射使用两个数据结构来存储数据。第一个数据结构是一个数组，内部存储的是用于选择桶的散列键的高八位值。这个数组用于区分每个键值对要存在哪个桶里。第二个数据结构是一个字节数组，用于存储键值对。该字节数组先依次存储了这个桶里所有的键，之后依次存储了这个桶里所有的值。实现这种键值对的存储方式目的在于减少每个桶所需的内存。

映射底层的实现还有很多细节，不过这些细节超出了本书的范畴。创建并使用映射并不需要了解所有的细节，只要记住一件事：映射是一个存储键值对的无序集合。

4.3.2　创建和初始化

Go 语言中有很多种方法可以创建并初始化映射，可以使用内置的 make 函数（如代码清单 4-45 所示），也可以使用映射字面量。

代码清单 4-45　使用 make 声明映射

// 创建一个映射，键的类型是 string，值的类型是 int
dict := make(map[string]int)

// 创建一个映射，键和值的类型都是 string
// 使用两个键值对初始化映射
dict := map[string]string{"Red": "#da1337", "Orange": "#e95a22"}

创建映射时，更常用的方法是使用映射字面量。映射的初始长度会根据初始化时指定的键值对的数量来确定。

映射的键可以是任何值。这个值的类型可以是内置的类型，也可以是结构类型，只要这个值可以使用 == 运算符做比较。切片、函数以及包含切片的结构类型这些类型由于具有引用语义，不能作为映射的键，使用这些类型会造成编译错误，如代码清单 4-46 所示。

代码清单 4-46　使用映射字面量声明空映射

// 创建一个映射，使用字符串切片作为映射的键
dict := map[[]string]int{}

Compiler Exception:
invalid map key type []string

没有任何理由阻止用户使用切片作为映射的值，如代码清单 4-47 所示。这个在使用一个映射键对应一组数据时，会非常有用。

代码清单 4-47　声明一个存储字符串切片的映射

// 创建一个映射，使用字符串切片作为值
dict := map[int][]string{}

4.3.3　使用映射

键值对赋值给映射，是通过指定适当类型的键并给这个键赋一个值来完成的，如代码清单 4-48 所示。

代码清单 4-48　为映射赋值

// 创建一个空映射，用来存储颜色以及颜色对应的十六进制代码
colors := map[string]string{}

// 将 Red 的代码加入到映射
colors["Red"] = "#da1337"

可以通过声明一个未初始化的映射来创建一个值为 nil 的映射（称为 nil 映射）。 nil 映射不能用于存储键值对，否则，会产生一个语言运行时错误，如代码清单 4-49 所示。

代码清单 4-49　对 nil 映射赋值时的语言运行时错误

// 通过声明映射创建一个 nil 映射
var colors map[string]string

// 将 Red 的代码加入到映射
colors["Red"] = "#da1337"

Runtime Error:
panic: runtime error: assignment to entry in nil map

测试映射里是否存在某个键是映射的一个重要操作。这个操作允许用户写一些逻辑来确定是否完成了某个操作或者是否在映射里缓存了特定数据。这个操作也可以用来比较两个映射，来确定哪些键值对互相匹配，哪些键值对不匹配。

从映射取值时有两个选择。第一个选择是，可以同时获得值，以及一个表示这个键是否存在的标志，如代码清单 4-50 所示。

代码清单 4-50　从映射获取值并判断键是否存在

// 获取键 Blue 对应的值
value, exists := colors["Blue"]

// 这个键存在吗？
if exists {
　　fmt.Println(value)
}

另一个选择是，只返回键对应的值，然后通过判断这个值是不是零值来确定键是否存在，如代码清单 4-51 所示。 ^①

代码清单 4-51　从映射获取值，并通过该值判断键是否存在

// 获取键 Blue 对应的值
value := colors["Blue"]

// 这个键存在吗？
if value != "" {
　　fmt.Println(value)
}

在 Go 语言里，通过键来索引映射时，即便这个键不存在也总会返回一个值。在这种情况下，返回的是该值对应的类型的零值。

迭代映射里的所有值和迭代数组或切片一样，使用关键字 range ，如代码清单 4-52 所示。但对映射来说， range 返回的不是索引和值，而是键值对。

代码清单 4-52　使用 range 迭代映射

// 创建一个映射，存储颜色以及颜色对应的十六进制代码
colors := map[string]string{
　　"AliceBlue":　 "#f0f8ff",
　　"Coral":　　　 "#ff7F50",
　　"DarkGray":　　"#a9a9a9",
　　"ForestGreen": "#228b22",
}

// 显示映射里的所有颜色
for key, value := range colors {
　　fmt.Printf("Key: %s　Value: %s\n", key, value)
}

如果想把一个键值对从映射里删除，就使用内置的 delete 函数，如代码清单 4-53 所示。

代码清单 4-53　从映射中删除一项

// 删除键为 Coral 的键值对
delete(colors, "Coral")

// 显示映射里的所有颜色
for key, value := range colors {
　　fmt.Printf("Key: %s　Value: %s\n", key, value)
}

这次在迭代映射时，颜色 Coral 不会显示在屏幕上。

4.3.4　在函数间传递映射

在函数间传递映射并不会制造出该映射的一个副本。实际上，当传递映射给一个函数，并对这个映射做了修改时，所有对这个映射的引用都会察觉到这个修改，如代码清单 4-54 所示。

代码清单 4-54　在函数间传递映射

func main() {
　　// 创建一个映射，存储颜色以及颜色对应的十六进制代码
　　colors := map[string]string{
　　　 "AliceBlue":　 "#f0f8ff",
　　　 "Coral":　　　 "#ff7F50",
　　　 "DarkGray":　　"#a9a9a9",
　　　 "ForestGreen": "#228b22",
　　}

　　// 显示映射里的所有颜色
　　for key, value := range colors {
　　　　fmt.Printf("Key: %s　Value: %s\n", key, value)
　　}

　　// 调用函数来移除指定的键
　　removeColor(colors, "Coral")

　　// 显示映射里的所有颜色
　　for key, value := range colors {
　　　　fmt.Printf("Key: %s　Value: %s\n", key, value)
　　}
}

// removeColor 将指定映射里的键删除
func removeColor(colors map[string]string, key string) {
　　delete(colors, key)
}

如果运行这个程序，会得到代码清单 4-55 所示的输出。

代码清单 4-55　代码清单 4-54 的输出

Key: AliceBlue Value: #F0F8FF
Key: Coral Value: #FF7F50
Key: DarkGray Value: #A9A9A9
Key: ForestGreen Value: #228B22

Key: AliceBlue Value: #F0F8FF
Key: DarkGray Value: #A9A9A9
Key: ForestGreen Value: #228B22

可以看到，在调用了 removeColor 之后， main 函数里引用的映射中不再有 Coral 颜色了。这个特性和切片类似，保证可以用很小的成本来复制映射。