golang-map介绍

本文中使用的 go 版本：

go version go1.17.2 darwin/amd64

内容概述

本文介绍 golang 中经常用到的结构-map，简称哈希表、字典。介绍其结构及设计思路。

map 在源码中的结构——hmap

Go 语言采用的核心数据结构是哈希查找表，使用链表解决哈希冲突。

在源码中$GOROOT/src/runtime/map.go，map 的核心结构体是这样的：

// A header for a Go map.
type hmap struct {
    count     int // map中的元素数量，即len(map)时的返回值
    flags     uint8
    B         uint8  // buckets的以2为底的对数, 即2^B=buckets
    noverflow uint16 // 溢出桶的近似数; see incrnoverflow for details
    hash0     uint32 // 哈希种子

    buckets    unsafe.Pointer // 2^B个bucket的数组，may be nil if count==0.
    oldbuckets unsafe.Pointer // 哈希在扩容时用于保存之前 buckets 的字段，它的大小是当前 buckets 的一半；
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // optional fields
}

在上面我们需要关注的核心是buckets，它是一个指针，最终指向了bmap结构体数组

// A bucket for a Go map.
type bmap struct {
    // tophash generally contains the top byte of the hash value
    // for each key in this bucket. If tophash[0] < minTopHash,
    // tophash[0] is a bucket evacuation state instead.
      // 翻译: tophash 存储了每个在该bucket中的key的最高字节，如果tophash[0] < minTopHash，tophash[0]是一个桶疏松状态
    tophash [bucketCnt]uint8
    // Followed by bucketCnt keys and then bucketCnt elems.

    // NOTE: packing all the keys together and then all the elems together makes the
    // code a bit more complicated than alternating key/elem/key/elem/... but it allows
    // us to eliminate padding which would be needed for, e.g., map[int64]int8.
      // 翻译: 注意，把所有键打包在一起，然后再把所有对应值打包在一起，这会比键值对交错更复杂。但这种形式能够消除多余的填充字节，方便内存对齐
    // Followed by an overflow pointer.
}

bucketCnt 是一个常量，它是一个 bucket 能够持有键值对个数的最大值。

它在源码中是这样的：

bucketCntBits = 3
bucketCnt     = 1 << bucketCntBits

即 bucketCnt = 1 左移三位 = 8

bucket 的结构-bmap

在运行时，bmap 的真正结构并不像它在源码里展示的这么简单，在编译期间会创建一个新的结构，这是因为哈希表中能存储的键值对类型不确定，而且 Go 语言也不支持泛型，不可能在源码中全部定义，所以键值对的类型及其占据的内存空间大小只能在编译时进行推导。

具体来说，是在类型检查阶段，在这一步 AST(抽象语法树)将转换为 SSA(静态单赋值)形式的中间代码，map 关键字及其操作将转换为对应的 runtime 函数，例如:

v     := hash[key] // => v     := runtime.mapaccess1(maptype, hash, &key)

所以，bmap 运行时的真正结构是这样：

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

其中，所有的 key 在一个组里，所有的 value 在一个组里，而不是以{key,value}的组来存储，这样能够减少内存对齐带来的内存浪费。

bucket 的结构如下图所示。

如果 bucket 装满了的话，会创建新的 bucket，并使用 overflow 字段指向新的 bucket，形成类似链表的结构。

一个 map 中会存在一个 bucket 数组，它们的关系大概像这样。

让我们暂停分析一下目前的结构，当往 map 中存储一个 kv 对时，通过 k 获取 hash 值，hash 值的低八位和 bucket 数组长度取余，定位到数组中的下标，hash 值的高八位存储在 bucket 中的 tophash 中，用来快速判断 key 是否存在，key 和 value 的具体值则通过指针运算存储，当一个 bucket 满时，通过 overfolw 指针链接到下一个 bucket。

随着哈希表存储的数据逐渐增多，我们会扩容哈希表或者使用额外的桶存储溢出的数据，不会让单个桶中的数据超过 8 个，不过溢出桶只是临时的解决方案，创建过多的溢出桶最终也会导致哈希的扩容。

预备

简单了解完了 map 的构成之后，接下来要介绍的就是对 map 的具体操作了，为了读者能更好的理解，这里要先讲一些预备知识。从何讲起？先来思考一个问题，我们都知道 go 是强类型的语言，并且目前为止(go1.17)都还不支持泛型，那么要怎么让 map 支持这么多类型呢？

先来看看别的强类型语言是怎么做的吧

C++的 map

首先来看看 c++，这里用到了 c++的特性之一————模板(也就是泛型啦)，c++标准模板库 STL 提供了 std::unordered_map，经常用来实现 hashmap。

This is the declaration for std::unordered_map. It’s a template, so the actual values of the parameters depend on how the template is instantiated.

这里是std::unordered_map的定义，它是一个模板，所以实际的参数值决定模板如何初始化。

template<
    class Key,                             // the type of the key
    class T,                               // the type of the value
    class Hash = std::hash<Key>,           // the hash function
    class KeyEqual = std::equal_to<Key>,   // the key equality function
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;

通过这些参数能知道：

• key 和 value 的类型Key、T，也就知道了它们的大小。
• KeyEqual，类型是std::equal_to<Key>，表示这个是一个处理Key的哈希函数，用来求 key 的哈希值
• Allocator，类型是std::equal_to<Key>，同样也是处理Key的函数，用于比较两个 key

有了这些信息，编译器就能在编译时确定类型，生成对应的确定类型的代码了。

来源: 引用 1¹

c++的 map 查询操作简单来说是这样的，如上图，首先我们将 key 传给 std::hash 函数以得到 key 的 hash 值。然后做掩码并取到 bucket 数组中的序号，接着再遍历对应 bucket 的 entry 列表并用 std::equal_to 函数来比较 key。

java 的 map

第二个要谈的是 java，不出所料，java 中 hashmap 类型就是java.util.Hashmap。

在 java 中， java.util.Hashmap只能够操作对象，因为 java 万物皆对象 🤪，所有的对象都来源于java.lang.Object，可以继承或重写hashCode 和 equals 方法。

当然，有 8 种基础类型不能够这样操作boolean， int， short， long， byte， char， float， and double，因为它们不是java.lang.Object的子类，难道说基础类型没法作为 key 或 value 吗？非也，为了解决这个限制，java 会隐式转换基础类型为它们对应的对象，这种操作叫装箱。

来源: 引用 1¹

java 中的查找是这样的，首先我们调用 key 的 hashCode 方法来获取它的 hash 值，然后做掩码操作，获取到 bucket 数组中的对应位置，里面存放了一个指向 Entry 的指针。Entry 中有一个 key，一个 value，还有一个指向下一个 Entry 的指针，形成了一个 linked list。

优缺点

现在我们知道了 hashmap 在 c++和 java 中的实现了，来比较一下他们的优缺点：

c++

优点：

• key 和 value 类型的大小在编译期间就确定了。
• 不需要装箱操作。
• 由于代码在编译期间就定下来了，所以其他编译优化操作例如内联，常数折叠和死代码删除就可以介入了。

总之，C++中的 map 和自己为每种 key/value 类型组合手写的特定 map 一样快速高效，因为本质就是一样的，模板为你生成了对应的代码。

缺点：

• 代码膨胀，每个不同的类型映射都有对应的一份 map 代码
• 编译时间增长，继上一点，更多的代码会带来更久的编译时间

java

优点:

• 基于多态，一份 map 代码的实现可以用于任何 java.util.Object 的子类。只需要编译一份 java.util.Object，在每个 class 文件中就都可以引用了。

缺点：

• 基本类型的 map 必须用通过装箱操作转化为对象。装箱操作会增加垃圾回收的压力，并且额外的指针引用会增加缓存压力（每个对象都必须通过另外的指针来查找）。
• Hash 和 equals 函数需要代码编写者来实现。不正确的 hash 和 equals 函数会减慢 map 的运行速度，甚至导致 map 的行为错误。

go 的 map

总结一下，c++的 map 就是写重复的代码来兼容不同的映射类型，将类型信息硬编码在代码中，而 java 的 map 使用一套代码，将操作对象统一，以多态形式处理不同类型的对象，即相当于等到运行时获取类型信息。

go 语言是什么方式呢？首先 go 没有泛型，没法像 C++模板一样生成所有相应类型映射的代码，那怎么以一套代码处理所有类型呢？(interface{}吗？留给大家思考)

这里先给出答案，并不是用 interface{}，go 的 map 的特别之处，在于它不是单单编译阶段就处理完成，需要编译时和运行时的相互协作。

编译时重写

在上文有提到过，编译器会重写 map 操作为 runtime 函数调用，例如:

v := hash[key] // => v := runtime.mapaccess1(maptype, hash, &key)

这里的 runtime 函数就是关键了，我们以runtime.mapaccess1函数举例介绍。

runtime 函数

先来看看runtime.mapaccess1函数，这是一个用来访问 map 的函数，签名:

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer

解释一下这些参数:

• key， 一个指针，指向了你提供的 key 值。
• h ，指向 runtime.hmap 结构的指针。
• t 是个指向 maptype 的指针。

🤓 来了，经过上文介绍，这里 key 和 h 的作用我想读者都能够很好的理解，但是它们都没有解决问题，关键所在就是这里的maptype，它使得通用的 *hmap 可以服务于（几乎）任意 key 和 value 类型的组合。在你的程序中对于每一个独立的 map 定义都会有一个特定的maptype值。例如，有一个 maptype 值描述了从 string 到 int 的映射，另一个描述了 string 到 http.Headers 的映射，等等。

因此，go 在编译期间做的事是，创建对应的 maptype，在调用 runtime 的 map 函数的时候当做参数传入，提供 hmap 需要的信息。

maptype

type maptype struct {
    typ    _type
    key    *_type
    elem   *_type
    bucket *_type // internal type representing a hash bucket
    // function for hashing keys (ptr to key, seed) -> hash
    hasher     func(unsafe.Pointer, uintptr) uintptr
    keysize    uint8  // size of key slot
    elemsize   uint8  // size of elem slot
    bucketsize uint16 // size of bucket
    flags      uint32
}

这是 maptype 的结构定义，包含了特定 map 中从 key 映射到 elem 所需的各种属性细节。如 key 和 elem 的类型信息(_type 类型中)，哈希函数。

// Needs to be in sync with ../cmd/link/internal/ld/decodesym.go:/^func.commonsize,
// ../cmd/compile/internal/reflectdata/reflect.go:/^func.dcommontype and
// ../reflect/type.go:/^type.rtype.
// ../internal/reflectlite/type.go:/^type.rtype.
type _type struct {
    size       uintptr
    ptrdata    uintptr // size of memory prefix holding all pointers
    hash       uint32
    tflag      tflag
    align      uint8
    fieldAlign uint8
    kind       uint8
    // function for comparing objects of this type
    // (ptr to object A, ptr to object B) -> ==?
    equal func(unsafe.Pointer, unsafe.Pointer) bool
    // gcdata stores the GC type data for the garbage collector.
    // If the KindGCProg bit is set in kind, gcdata is a GC program.
    // Otherwise it is a ptrmask bitmap. See mbitmap.go for details.
    gcdata    *byte
    str       nameOff
    ptrToThis typeOff
}

在 _type 类型中，记载的是类型信息，比如它的大小size，该类型判断是否相等的方法euqal。

总结，go 的 map 没有重复的 map 代码，靠的是多个maptype来提供不同的类型信息，在运行时从参数maptype中获取需要的类型信息，通过这个机制，go 不必生成大量的重复 map 代码，也不用特殊处理基础类型，以一套 map 代码就能够处理所有的类型映射，并且性能依然优秀。使用方式简单清晰，的确是优秀的设计！

引用

Runtime:源码解析 Golang 的 map 实现原理