Go 数据结构之 - map

---

golang 中，map 是最常用的数据结构之一，golang 的 map 具有无序、非线程安全等特点，为了减少使用过程中的容易出错的问题以及达到最优的程序性能，我们有必要了解下 map 的底层实现原理，本文从 map 的概念到 golang map 的实现，在阅读了其他文档和博客的基础上总结整理在此。

什么是 map？

维基百科的定义

In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

包含键值对（key-value）集合的抽象数据结构（关联数组、符号表或字典），其每个可能的键在该集合中最多出现一次，这样的数据结构就是一种 Map。

为什么要使用 map？

反过来思考，如果不使用 map，一般基础的数据类型就是数组，如果我们使用数组来存储一系列的健值对，无论是查找还是修改，都会变得非常麻烦，最粗暴的办法就是我们需要把 key 哈希一个数字，根据数字来获取数组索引位置的值实现。但是如果每次都自己实现这一套逻辑，无疑会增加我们的工作量，所以实现一个可存储 key value 方便根据 key 高效查找、修改、删除的数据结构就非常迫切。

常见的 map 实现方式

HashTable 哈希表

哈希表是用作最多的 map 的底层实现方式，大概思路是：

• 先初始化一个数组
• 根据 key 哈希计算到一个索引位置
• 添加和删除直接通过计算的哈希值来操作数组对应的索引位置

由于数组在内存是连续的一块内存地址，所以通过索引获取或者修改的操作的时间复杂度为 O(1)，做到了高效添加、修改和删除

哈希表的核心是哈希算法的随机性，试想如何哈希算法不够随机，会导致大量的集中的 key 被哈希到相同的桶位置上，那么会造成哈希冲突。一般常见的哈希算法有：

• 直接寻址法（direct-address table）：取关键字或关键字的某个线性函数值为散列地址。
• 数字分析法：通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。例如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造散列地址。
• 平方取中法 (midsquare method) ：当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。
• 取随机数法：使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。
• 除留取余法：取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要，一般取素数或者直接用 n。

注：这里摘自 《哈希表（Hash Table）与哈希算法》

解决哈希冲突问题

在数据量大的情况下，哈希表肯定会遇到哈希冲突问题，即不同的哈希 key 计算得到相同的哈希值，那么解决哈希冲突的方法一般有两种：

• 链地址法
• 开放寻址法

哈希冲突的影响因素装载因子：装载因子是表示哈希表中元素的填满程度。它的计算公式：装载因子=填入哈希表中的元素个数/哈希表的长度。装载因子越大，填入的元素越多，空间利用率就越高，但发生哈希冲突的几率就变大。反之，装载因子越小，填入的元素越少，冲突发生的几率减小，但空间浪费也会变得更多，而且还会提高扩容操作的次数。装载因子也是决定哈希表是否进行扩容的关键指标，在java的HashMap的中，其默认装载因子为0.75；Python 的 dict 默认装载因子为2/3

链地址法

链地址法的思想是将哈希在同一个桶位置的元素用一个链表串联起来；查找和修改在计算到对应的哈希值之后都需要遍历整个链表。

链地址法优势：

• 合理利用空间，内存使用率高
• 发生冲突后的代价小，不需要过多计算
• 可优化空间大，链表可采用其他数等数据结构来优化

链地址法劣势：

• 查找和修改的时间复杂度升高

开放寻指法

开放寻址法的思想是当遇到哈希冲突时，按照一定的策略再次进行哈希，直到找到没有值的空槽位；所以开放寻址法的前提条件是，槽位的数量必须大于等于元素的数量（必要时候需要进行动态扩容）；常见的开放寻址的策略有：线性探测、平方探测、随机探测、双重哈希等

开放寻址法优势：

• 存储还是数组，对 CPU 缓存友好，易于序列化操作
• 读取和修改的时间复杂度底

开放寻址法劣势：

• 需要重新计算槽位，计算复杂度高
• 使用空间相对增加，内存利用率低

总结：对于小数据量或者确定数据量大小的适合用开放寻址法；对于大数据量的，冲突更多的适合用链地址法

平衡搜索树

数的数据结构的查询复杂度一般在 log(n)，包括：AVL 平衡树和红黑树，这里不做详细解释；

总体比较来看，从时间复杂度上还是哈希表的方式最优；所以更多是采用哈希表来实现 map 、dict、或者字典等数据结构，例如：

• Redis 字典：使用的哈希表，哈希冲突使用的链地址法
• PHP 的字典：使用的哈希表，哈希冲突使用的链地址法
• Java 的 map：使用的哈希表，哈希冲突使用的链地址法
• Python 中 dict：使用的哈希表，哈希冲突使用的开放寻址法
• Go 中的 map：使用的哈希表，哈希冲突使用的链地址法

golang map 实现

golang 的 map 也是使用的哈希表实现，解决哈希冲突也是使用的链地址法，map 的内部结构位 hmap，结构简单如下：

// A header for a Go map.
type hmap struct {
    // 元素个数，调用 len(map) 时，直接返回此值
    count     int
    flags     uint8
    // buckets 的对数 log_2
    B         uint8
    // overflow 的 bucket 近似数
    noverflow uint16
    // 计算 key 的哈希的时候会传入哈希函数
    hash0     uint32
    // 指向 buckets 数组，大小为 2^B
    // 如果元素个数为0，就为 nil
    buckets    unsafe.Pointer
    // 扩容的时候，buckets 长度会是 oldbuckets 的两倍
    oldbuckets unsafe.Pointer
    // 指示扩容进度，小于此地址的 buckets 迁移完成
    nevacuate  uintptr
    extra *mapextra // optional fields
}

B 是 buckets 数组的长度的对数，buckets 数组的长度就是 2^B。bucket 里面存储了 key 和 value，buckets 是一个指针，最终它指向的是一个结构体：

type bmap struct {
    tophash [bucketCnt]uint8
}

但这只是表面(src/runtime/hashmap.go)的结构，编译期间会给它加料，动态地创建一个新的结构：

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype // 存储多个 key
    values   [8]valuetype // 存储多个 value
    pad      uintptr
    overflow uintptr
}

bmap 其实就是一个桶的结构，桶里最多装8个key，这8个key的哈希计算得到的值是一样的。在桶内又会根据计算出来的高8位来决定 key 到底落到桶里的哪个位置（一个桶内最多8个位置）

从图中可以看出，[]bmap 是整个哈希表数组，每个桶的结构为 bmap，每一个 bmap 可以存储最多 8 个元素（根据元素的高8位和低8位决定在哪个位置），overflow 指针会指向新扩容的新的桶，下面我们针对 map 的具体操作捞说明整个哈希map的实现是怎样的。

map 操作实现

添加元素

添加或创建 map：

a := make(map[string]int)

汇编语言可以看到，实际上底层调用的是 makemap 函数，主要做的工作就是初始化 hmap 结构体的各种字段，例如计算 B 的大小，设置哈希种子 hash0 等等，函数大概如下：

func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap {
    // 初始化 hamp
    if h == nil {
        h = (*hmap)(newobject(t.hmap))
    }
    h.count = 0
    h.B = B
    h.extra = extra
    h.flags = 0
    h.hash0 = fastrand()
    h.buckets = buckets
    h.oldbuckets = nil
    h.nevacuate = 0
    h.noverflow = 0
    return h
}

注意：这里可以看到 makemap 函数返回的是一个指针，*hmap，所以这里我们就会明白，map 数据结构本身是引用类型，传递到函数内部，即使 copy 了一份新的结构，但是底层的指针指向的内存不变。

这里可以回回顾下 slice 的底层实现：

// runtime/slice.go
type slice struct {
    array unsafe.Pointer // 元素指针
    len   int // 长度 
    cap   int // 容量
}

结构体内部包含底层的数据指针。makeslice 返回的值。

主要原因：一个是指针（hmap），一个是结构体（slice）。Go 语言中的函数传参都是值传递，在函数内部，参数会被 copy 到本地。hmap指针 copy 完之后，仍然指向同一个 map，因此函数内部对 map 的操作会影响实参。而 slice 被 copy 后，会成为一个新的 slice，对它进行的操作不会影响到实参。

查找key值

查找key对应的值，首先我们需要定位到 key 在哈希表中的位置。key 定位的流程如下：

简化下整体的查找流程：

1. 将 key 传入哈希函数（不同类型的key的哈希函数可能不同）
2. 计算得到对应的哈希值 int64 位的二进制数值
3. 当前哈希对象的生成的桶的数量 buckets 的数量，取决于 B 的大小，即 2^B 的桶的数量。取哈希值对应的末尾的 B 位二进制数。举例：图中的哈希对象的桶的对数 B=5，即 2^5 = 32 个 buckets，那么就取哈希结果二进制的末尾 5 位 00110 = 6，就定位到了 bucket 的位置
4. 找到对应的 bucket 位置，bucket 里是一个 bmap 的链表，循环 bmap 的链表中的每一个 tophash 列表，根据哈希结果二进制对应的高 8 位的值和每个 bmap 结构里的 tophash 值进行对比
   • 如果值相等，就找到了具体的 key 和 value 的位置，即相等的 tophash 的索引位置
   • 如果值不相等，就继续循环直到 overflow 指针找到末尾链表，没有找到返回 nil
5. 定位到 key 的位置之后，里面存储着 8 个对应的 key 和 value
6. 返回对应 key 在 bmap 索引位置的 value

更新key值

更新 key 值和查找基本一样的流程，区别只是在于最后更新一下 value 的值。
核心还是一个双层循环，外层根据低位值遍历 bucket 和它的 overflow bucket，内层根据高8位遍历整个 bucket 的 tophash 找到对应的 key 的索引

注意：更新和读取的时候，go 会设置一个标志位 flag，用来标记是否有其他的程序正在写入数据，如果有的话会触发并发读写的 panic

删除key值

删除 key 值也比较简单，找到之后清空对应的 key 和 val 以及 tophash 置为空

遍历 map

map遍历的过程，是按序遍历 bucket 的，同时遍历 bucket 里面的 tophash 对应的 key 和 value，但其实，为了保证遍历map的结果是无序的，还做了以下事情：map在遍历时，并不是从固定的0号bucket开始遍历的，每次遍历，都会从一个随机值序号的bucket，再从其中随机的cell开始遍历。然后再按照桶序遍历下去，直到回到起始桶结束。

注意：go map 的遍历总是无序的，不能用map来作为有序数据存储

map 扩容

为什么需要扩容

如果 map 添加的数据越来越多，导致 hash 碰撞的几率越来越大，造成 bmap 里的链表会越来越长，整个的查找的时间复杂度将会严重退化，直至变成一个链表的查找时间复杂度。当 map 将要添加、修改或删除 key 时，都会检查是否需要扩容，扩容实际上是以空间换时间的手段。

扩容的时机

哈希表只有在添加元素的时候会触发扩容，在赋值、删除的动作下会触发扩容行为，扩容的条件如下：

• 触发 load factor 的最大值，负载因子已达到当前界限
• 溢出桶 overflow buckets 过多

扩容的方案

扩容的方案主要如下：

• 根据需扩容的原因不同（overLoadFactor/tooManyOverflowBuckets），分为两类容量规则方向，为等量扩容（不改变原有大小）或双倍扩容
• 新申请的扩容空间（newbuckets/newoverflow）都是预分配，等真正使用的时候才会初始化
• 扩容完毕后（预分配），不会马上就进行迁移。而是采取增量扩容的方式，当有访问到具体 bukcet 时，才会逐渐的进行迁移（将 oldbucket 迁移到 bucket）

扩容完成后迁移（搬迁）：
插入（包括修改）、删除 key 的时候，都会尝试进行搬迁 buckets 的工作：

1. 每次至多搬迁 2 个 bucket
2. 一次性搬迁将会造成比较大的延时，采用逐步搬迁策略

map 常见问题

• float 类型可以作为 map 的 key

  可以的，除了 slice，map，functions 其他都可以

• map 中的 key 为什么是无序的

  1. map 在扩容后，会发生 key 的迁移，导致在原来的桶里的位置改变
  2. map 的遍历不是从0开始遍历的，每次随机取一个值遍历的

• map 是不是线程安全的？

  不是线程安全的；
  在添加、修改、删除的时候都会写一个标志位，发现有标记为1，直接 panic

• map 删除一个 key 发生了什么？

  1. 计算 key 的哈希结果
  2. 如果发生在扩容，直接搬迁
  3. 如果不是扩容，定位到 key 的位置
  4. 直接清零

• map 的扩容过程是怎样的？

  参考上面的扩容介绍

• map 如何赋值的？

  1. 计算 key 的哈希结果
  2. 判断是否有标记位
  3. 如果有标记位，直接 panic
  4. 定位到 key 的位置，修改

• map 如何遍历？

  1. 每次随机生成一个数字
  2. 双层循环
  3. 如果正在扩容搬迁，也需要循环搬迁的内容

• 比较两个 map 相等？

  只能循环遍历 map 的每一个元素

• 赋值的时候会触发扩容吗？

  不会，只有添加元素才会

• 负载因子是什么？过高会带来什么问题？它的变动会对哈希表操作带来什么影响吗？

  过高会触发扩容

• 溢出桶越多会带来什么问题？

  触发扩容，时间复杂度高

• 是否要扩容的基准条件是什么？

  负载因子和链表长度

• 扩容的步骤是怎么样的？涉及到了哪些数据结构？

• 扩容是一次性扩容还是增量扩容？

  增量扩容

• 正在扩容的时候又要扩容怎么办？

  扩容完成后下一次扩容

总结

Go语言的map，底层是哈希表实现的，通过链地址法解决哈希冲突，它依赖的核心数据结构是数组加链表。

map中定义了2的B次方个桶，每个桶中能够容纳8个key。根据key的不同哈希值，将其散落到不同的桶中。哈希值的低位（哈希值的后B个bit位）决定桶序号，高位（哈希值的前8个bit位）标识同一个桶中的不同 key。

当向桶中添加了很多 key，造成元素过多，超过了装载因子所设定的程度，或者多次增删操作，造成溢出桶过多，均会触发扩容。

扩容分为增量扩容和等量扩容。增量扩容，会增加桶的个数（增加一倍），把原来一个桶中的 keys 被重新分配到两个桶中。等量扩容，不会更改桶的个数，只是会将桶中的数据变得紧凑。不管是增量扩容还是等量扩容，都需要创建新的桶数组，并不是原地操作的。

扩容过程是渐进性的，主要是防止一次扩容需要搬迁的 key 数量过多，引发性能问题。触发扩容的时机是增加了新元素， 桶搬迁的时机则发生在赋值、删除期间，每次最多搬迁两个 桶。查找、赋值、删除的一个很核心的内容是如何定位到 key 所在的位置。

参考资料

• 哈希表（Hash Table）与哈希算法
• 深入理解 Go map：赋值和扩容迁移
• 深入理解Golang中map设计