下载掌阅APP，畅读海量书库
立即打开
在高级编程语言中，数组通常按照索引访问，而字典（或称映射）则通过Key来访问。Go语言通过内置的map类型来满足基于Key访问的需求。Go的map内部采用散列表实现，以实现快速增加、删除和查找操作。在Go语言中，map的Key查找操作的时间复杂度为 O （1），即常数级别。尽管map的扩容可能会导致性能下降，时间复杂度在最坏情况下达到了 O （ n ），但Go语言已采取多种优化措施来减轻这种影响。
在定义map时，我们必须确定Key和Value的类型。值得注意的是，map的Value可以是任意类型，但是Key不能是所有的类型。map的Key常见的类型包括string、int等。然而，像切片或者函数这样的类型是不能作为map的Key的。总体而言，只有能够用“==”符号进行比较的类型才能作为map的Key。map的定义语法如下：
上述语法仅创建了一个指向hmap结构的指针变量，并没有分配hmap结构体的内存，更没有进行初始化。因此，这种状态下的map变量还不能使用，否则会触发访问nil指针触发的panic错误。
创建和初始化map有三种不同的语法，可以用make来创建，也可以使用字面量的方式。以下是初始化map的三种方式的示例：
在编译时，编译器识别到这些语法，并转换为相应的函数调用，调用makemap来创建并初始化一个hmap结构体，并将该结构体的指针赋给m变量。hmap结构体的定义如代码清单2-14所示：
代码清单2-14 hmap结构体的定义
hmap是map的核心结构体，本质上是散列表的实现。它在基本散列表结构上增加了一些设计和优化，例如对垃圾回收的优化以及对冲突率的控制，使其结构略显复杂。散列表需要解决散列冲突的问题，hmap通过数组加链表的方式来解决这一问题。
hmap本身是一个管理结构体，其内存大小是固定的。map的Key/Value数据存储在名为bmap（bucket map的缩写）的结构体中。bmap的内存大小则取决于Key/Value的大小。bmap结构体的定义如代码清单2-15所示。
代码清单2-15 bmap结构体的定义
从上述定义可以看出，bmap结构体中只定义了一个tophash字段。这是因为编译器需要在编译时动态构造bmap结构体的字段内容，完整的bmap结构体会包含更多字段，其定义如代码清单2-16所示。
代码清单2-16 完整的bmap结构体的定义
这么做的原因是，在定义map变量之前，我们无法知道Key、Value的类型和内存占用，只有在编译时才能通过分析得到。在Go语言的很多场景中，编译器都在后台默默地进行着这种辅助工作。bmap的定义便是一个典型的例子。
bmap最多存储8对Key/Value。如果元素的数量超出了这一限制，就需要创建一个新的bmap结构体，多个bmap结构体通过overflow字段构成一个链表。bmap的内存大小是在编译期间计算得到的，之后固定不变。hmap和bmap结构体的关系如图2-8所示。
图2-8 hmap和bmap结构体的关系
hmap作为核心管理结构，承载了map中的Key/Value的存储功能。实际的数据存储在bmap结构体中。Go语言的map通过结合数组和链表的方式来解决散列冲突问题。首先，Key通过散列算法的计算得到散列值，然后根据这个散列值将Key分配到hmap.buckets数组的某个bucket中，最后在该bucket对应的bmap链表上进行查找，最终找到Key存取的位置。
接下来将深入探讨map的读取、写入以及删除等操作。
在Go语言中，map的读取、写入、删除操作都是通过Key进行的。下面是操作map的基本方法：
上述操作背后对应着不同的函数过程，接下来将逐一探讨这些操作的原理。
1.map读取
Go语言提供了两种读取map的语法，以适应不同的使用场景。以下是两种map读取方式的示例代码：
如果map里不存在指定的Key，直接取值的方式并不会引发panic或其他错误，而只会返回对应类型的“零值”。例如，如果Value是字符串类型，则返回值为空字符串。
在不需要区分值本身为空还是Key不存在的场景下，我们可以使用直接取值的方式。但若需明确区分这两种情况，则第二种方式更为适合，通过第二个返回的布尔值来判断Key是否存在，如果为true，则表明Key存在于map中。
在编译期间，编译器会根据上述不同的读取方式转换为相应的函数调用。直接取值的场景对应mapaccess1函数的调用，而需要判断Key是否存在的场景则对应mapaccess2函数的调用。这两个函数的逻辑非常相似。接下来将详细探讨mapaccess2函数的具体实现，如代码清单2-17所示。
代码清单2-17 mapaccess2函数的实现
mapaccess2函数的实现逻辑相对简单。首先，通过Key计算得到一个散列值，该散列值一部分用于定位bucket，另一部分用于在bucket内部快速查找Key/Value。接着，利用散列值定位到对应的bucket。为了解决散列冲突问题，采用了链表的方式扩展bmap，即通过bmap的overflow字段指向下一个bmap结构体，从而形成一个链表。
bmap是map内部的存储单位，每个bmap有8个槽位，最多可以存储8个Key/Value。在访问某个Key时，我们会遍历这个bmap的所有元素，如果没找到对应的Key，则继续去链表的下一个bmap节点中搜索，直到找到对应的Key。图2-9直观地展示了散列计算的过程。
图2-9 散列计算示意
在访问散列表时，推荐使用v, ok :=m[key]的方式，这样既可以确切地知道Key是否存在，也可以避免任何潜在的歧义。
2.map写入
map的写入过程就是一个Key/Value的插入或者更新的过程。具体的更新示例如下：
当编译器识别到map赋值的语句时，将其转换成mapassign函数的调用。其内部的前期流程和读取过程类似。mapassign函数的实现如代码清单2-18所示。
代码清单2-18 mapassign函数的实现
首先，根据Key计算出来的散列值找到对应的bucket，然后在bucket内部查找Key的位置，确认Key所在的位置后，更新Key/Value的值。如果对应的bmap已满，将调用hmap.newoverflow函数进行扩容，分配一个新的bmap结构体，并将其作为链表的新节点连接到尾部。
在遍历bmap的内部元素时，会先比较tophash，再比较Key。如果Key原来不存在，则执行插入流程，此时会分配Key/Value需要的内存空间，并通过typedmemmove把Key复制到相应的内存位置，随后返回Value的内存地址。如果Key已存在，则进行更新操作，直接返回Value的内存地址。
值得注意的是，无论插入还是更新，在mapassign函数中只会返回Value的内存地址，而不负责Value的赋值。Value的具体赋值过程是在mapassign函数外部完成的，由编译器在编译期间生成的专门代码来处理。对于map["key"]="value"这样的代码，其汇编代码的简化版如下所示：
在实际的编译过程中，有很多针对性的优化措施。例如，当Key的类型为字符串时，赋值操作将调用mapassign_faststr函数；如果Key是int64类型，则会调用mapassign_fast64函数，其内部处理逻辑与mapassign函数相似，这里不再详细阐述具体的优化细节。
3.map删除
在Go语言中，要删除map中的一个元素，通常使用delete（m,key）函数。编译器会将该函数转换为对mapdelete函数的调用。mapdelete函数内部的逻辑与读取和写入操作相似，要先定位到Key所在的位置。首先，通过给定的Key计算出散列值，接着通过该散列值找到对应的bucket，并在bucket内部进行遍历，最终定位到Key的具体位置。一旦找到Key的位置，就会执行以下主要步骤：
❑ 将bmap的tophash数组中对应的位置重置为empty。
❑ 清理bmap中对应的Key/Value的内存值，使Key/Value的内存不再被引用，从而在后续可以被垃圾回收器回收。
因此，删除流程本质上也是赋值操作，只不过这次赋值的内容是empty和nil值。这个流程与map写入逻辑极为相似，这里就不再详细展开了。
在Go语言中，可以使用for-range结构来遍历map的内部元素。然而，需要注意的是，Go的map是无序的结构，这意味着在遍历过程中，元素的出现顺序是不可预测的。如果有按顺序遍历的需求，那么用户需要在外部单独维护一个有序结构来存放Key，然后再结合map来实现有序遍历。
为了强调map遍历的无序性，并阻止用户基于遍历顺序做出错误假设，Go语言的设计者甚至在每次遍历时会故意生成一个随机因子，以打乱元素的遍历顺序，从而使得每次遍历的序列都是不同的。以下是map遍历的代码示例：
在上面的代码中，每次打印出的Key/Value的顺序可能会不同。for-range遍历的原理很简单，可以分解为三个要素：
1）初始化（init）。
2）终止条件的判断（condition）。
3）条件递进（increment）。
map遍历的伪代码如下所示：
编译器检测到map和for-range结合使用时，会将其转换为对mapiterinit和mapiternext两个函数的调用，分别对应for循环的初始化、条件递进部分。终止条件则是根据mapiternext函数的返回结果来判断的。下面我们逐一分析这三个部分。
1.for初始化
在讨论map的遍历逻辑之前，我们首先来看迭代器的hiter结构体。hiter是在map遍历过程中使用的一个核心数据结构，它在初始化、递进和终止条件判断等环节中发挥着重要作用。hiter结构体的定义如代码清单2-19所示。
代码清单2-19 hiter结构体的定义
在hiter结构体中，hiter.key和hiter.elem用于访问当前的Key/Value。mapiterinit函数的主要作用就是构造一个hiter迭代器实例。mapiterinit函数的实现如代码清单2-20所示。
代码清单2-20 mapiterinit函数的实现
从上述代码可以看出，其主要工作是初始化hiter结构体，并计算遍历的起始位置。在mapiterinit函数中，使用fastrand（）函数来生成一个随机因子，从而故意打乱每次遍历的顺序，确保遍历的顺序在每一次都是随机的。
2.for条件递进
for循环的条件递进和终止判断都依赖于mapiternext函数的执行。在每一次迭代中，都会调用此函数来推动循环向前，并决定是否结束循环。mapiternext函数的实现如代码清单2-21所示。
代码清单2-21 mapiternext函数的实现
mapiternext函数的处理较为复杂，主要是为了应对垃圾回收以及在遍历过程中可能发生的map结构变动等情况。但其核心逻辑是比较直观的：从mapiterinit函数确定的startBucket开始，处理每个bucket，包括bucket的溢出链表，直到所有bucket节点都被处理完成，此时hiter.key、hiter.elem都会被设置成nil值，这标志着for循环的终止条件已达成。
3.for终止条件
当for-range和map结合使用时，终止条件的判断很简单：只需要检查hiter.key是否为nil。如果为nil，则终止for循环。
在Go语言中，map的应用场景非常广泛，它通常作为内存中的Key/Value存储方案。得益于底层散列表的实现，map的查询性能非常高效，这使得它特别适用于读多写少的场景。但需要注意的是，Go语言中的map并不是并发安全的。因此在涉及并发操作时，开发者需要自行采取措施保障其安全性。如需一个并发安全的map，也可以选用标准库的sync.Map结构。开发者可以根据自身的需求和场景，选择最合适的使用方式。