Go 源码之 map

一、简介

map 是一种非常常见的数据类型，它可以用于快速地检索数据；是一种 key-value 结构的数据类型，key 是唯一的，value 可以重复

• 键值对为元素的数据集合

• 查询时间复杂度 O (1)，最坏情况下 O (N) ，需要遍历溢出桶

• 核心 hmap 和 buckets 数组（bmap） 两个结构实现，bmap 存储了八个元素

• map 读写：

  • 1. 通过 hmap结构 中的 hash0 计算 key 的哈希值
  • 2. 根据哈希值的低 8 位确定 该key 所在的 buckets（bmap 数组）的位置
  • 3. 再根据哈希值的高 8 位 与 bmap 中的tophash数组（该 bmap 下所有 key 的高 8 位hash 值，比直接从 keys 数组查找更快）

• 找到该 key 所在的下标位置idx，然后从 keys 数组再次比较是否一致：

  • 1. key 一致，则从 values 数组获取值
  • 2. key 不一致，则遍历 overflow（溢出桶），然后返回结果

• map 只能用 len() 不能用 cap()，创建 map 不能指定 len，只能指定 cap，并且 cap 不是实际容量，底层根据 cap 算出实际桶（bmap）数量

• 键不重复 并且 键必须可哈希（int / bool / float / string / array / 指针类型），slice / struct / interface / map 等引用类型不可哈希

二、源码

go/src/runtime/map.go

（一）数据结构

hmap

type hmap struct {
    count     int                    // map中元素的个数
    flags     uint8                  // Map 的状态标志位，包括迭代器状态和是否是引用类型
                                     // flag的一些状态位
                                     // iterator     = 1 // 有遍历器在遍历桶
                                     // oldIterator  = 2 // 有遍历器在遍历旧桶
                                     // hashWriting  = 4 // 有协程在写map
                                     // sameSizeGrow = 8 // 等量扩容，但不是两倍扩容，而是等量扩容

    B         uint8                  // bucket 数组的大小，即2^B个bmap
    noverflow uint16                 // 溢出 bucket 的数量，即产生 hash 冲突的 bucket 数量
    hash0     uint32                 // Map 中的哈希种子，用于 hash 函数

    buckets    unsafe.Pointer        // 指向bucket数组的指针，bucket数组可能会在扩容时被重新分配.
    oldbuckets unsafe.Pointer        // 表示先前的 bucket 数组的指针，用于 Map 扩容时进行转移元素的操作
    nevacuate  uintptr               // 表示当前正在进行 Map 扩容时的进度计数器，少于这个数字的buckets都会被回收

    extra *mapextra                  // 表示与 Map 相关的额外信息,包括 溢出桶 信息
}

type mapextra struct {
   overflow    *[]*bmap         // 存放的所有溢出桶的地址。
   oldoverflow *[]*bmap         // 存放的所有老的溢出桶的地址。这个是针对扩容的时候
   nextOverflow *bmap           // 指向的下一个溢出桶的地址。
}

bmap

// 源码中结构
type bmap struct {
    tophash [bucketCnt]uint8
}
// 实际编译后运行时bucket结构
type bmap struct {
  tophash  [8]uint8         // 存储hash值的前几位，如果小于5，则表示上述的tophash状态码

  keys     [8]keytype       // key数组，隐藏字段
  values   [8]valuetype     // value数组，隐藏字段
  overflow uintptr          // 溢出buceket指针，隐藏字段
}

（二）创建

// 初始化一个可容纳 10 个元素的map，但不是桶的数量
info = make(map[string]string,10)
底层调用 makemap

• 校验

• 创建一个hmap结构体对象

• 生成一个哈希因子hash0 并赋值到hmap对象中（用于后续为key创建哈希值）

• 根据 hint=10，并根据算法规则来创建 B，当前 B 应该为 1

  • hint B

  •   0~8 0

  • 9~13 1

  • 14~26 2

  • …

• 第四步：根据B去创建去创建桶（bmap对象）并存放在buckets数组中，当前bmap的数量应为2.

  • 当B<4时，根据B创建桶的个数的规则为：2^B（标准桶）

  • 当B>=4时，根据B创建桶的个数的规则为：2^B + 2^{B-4}（标准桶+溢出桶）

注意：每个bmap中可以存储8个键值对，当不够存储时需要使用溢出桶，并将当前bmap中的overflow字段指向溢出桶的位置。

// hint 也就是创建 map 时指定的容量，根据 hint 计算出 B，然后创建 2^B 个桶
func makemap(t *maptype, hint int, h *hmap) *hmap {
  -------------------- 内存溢出校验 -------------------- 
    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
    if overflow || mem > maxAlloc {
        hint = 0
    }
    --------------------  初始化一个hmap，如果h为nil则重新初始化 -------------------- 
    if h == nil {
        h = new(hmap)
    }
    -------------------- 生成哈希种子 -------------------- 
    h.hash0 = fastrand()
    -------------------- 根据 hint 初始化B的大小 -------------------- 
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B

    -------------------- 根据 B 创建 bmap 和 溢出桶 nextOverflow -------------------- 
    if h.B != 0 {
        var nextOverflow *bmap
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }
    return h
}

（三）新增

var info=make(map[string]string)
info["name"] = "******"
底层调用 mapassign

• 校验

• 根据哈希因子 hash0 计算 key 的哈希值； 如计算 name 哈希结果：011011100011111110111011011

• 根据一定条件判断是否进行 扩容 、迁移 操作，也就是 rehash

• 根据哈希值的后 B 位的值来决定将此键值对存放到那个桶中（bmap），实际上计算出来的是 buckets 的下标：

        将哈希值和桶掩码（B个为1的二进制）进行 & 运算，最终得到哈希值的后B位的值。假设当B为1时，其结果为 0 ：

        哈希值：011011100011111110111011010

        桶掩码：000000000000000000000000001

        结果： 000000000000000000000000000 = 0

        通过示例你会发现，找桶的原则实际上是根据后B为的位运算计算出 索引位置，然后再去buckets数组中根据索引找到目标桶（bmap)

• 确定 bmap 之后，将 tophash、key、value分别写入到桶中的三个数组中，后续会根据 tophash 比较相同则再去比较key

• 如果桶已满，则通过 overflow 找到溢出桶，并在溢出桶中继续写入

• hmap的个数count++（map中的元素个数+1）

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    -------------------- 校验 -------------------- 
   if h == nil {
        panic(plainError("assignment to entry in nil map"))
    }
    if h.flags&hashWriting != 0 {                                   // 并发读写
        fatal("concurrent map writes")
    }
    -------------------- 计算 hash 值 -------------------- 
    hash := t.hasher(key, uintptr(h.hash0))
    h.flags ^= hashWriting                                          // 标记为正在写

again:
    bucket := hash & bucketMask(h.B)
    -------------------- 根据一定条件判断是否需要扩容 -------------------- 
    if h.growing() {
        growWork(t, h, bucket)
    }
    -------- 根据哈希值的后 B 位的值对应 buckets 数组的下标，然后将 tophash、key、value 写入 bmap 中 --------- 
    -------- 如果桶已满，则通过 overflow 找到溢出桶，并在溢出桶中继续写入    -------- 
    ................

    -------------------- hmap的个数count++  -------------------- 
    h.count++

    return elem
}

（四）查询

var name=info["name"] 

• 校验

• 根据哈希因子 hash0 计算 key 的哈希值； 如计算 name 哈希结果：011011100011111110111011011

• 根据哈希值的后 B 位的值来决定将此键值对存放到那个桶中（bmap），实际上计算出来的是 buckets 的下标

• 确定 bmap 后，再根据 key 的哈希值计算 出tophash（高 8 位），快速比较 tophash 确定元素下标，然后再去 key 和 value 中 获取元素

• 当前桶如果没找到，则根据 overflow 再去溢出桶中找，均未找到则表示 key 不存在

（五）删除

在 Go 语言中，使用 delete 内置函数删除 map 中的元素时，并不是直接将元素从内存中物理移除，而是采用做标记的方式，下面详细介绍具体过程和原因。具体删除过程：

当调用 delete(m, key) 时（其中 m 是 map，key 是要删除的键），Go 语言的运行时会执行以下操作：

查找键值对：根据 key 计算哈希值，然后定位到对应的桶（bucket），在桶及其可能存在的溢出桶中查找该 key 对应的键值对。

标记删除：一旦找到对应的键值对，不会立即释放该键值对所占用的内存空间，

而是将该位置对应的 tophash 值标记为一个特殊值（例如 emptyOne），以此来表示该位置的键值对已经被删除。

这样在后续的查找操作中，如果遇到标记为已删除的位置，会直接跳过。

之后在扩容时进行清理删除

（六）扩容

在 Go 语言中，map 是基于哈希表实现的，随着键值对的不断添加，为了保证 map 的性能，避免过多的哈希冲突，会在必要时进行扩容操作

1. 扩容条件

• 负载因子过高：负载因子（load factor）是指 map 中键值对的数量与桶数量的比值：

  • 当负载因子map中数据总个数 / 桶个数 > 6.5 时，会触发扩容。

  • 负载因子过高意味着每个桶中的平均键值对数量较多，哈希冲突的概率会增大，从而影响查找和插入的性能

• 溢出桶过多：使用了太多的溢出桶时（溢出桶使用的太多会导致map处理速度降低）

  • B <=15，已使用的溢出桶个数 >= 2^B 时，引发等量扩容

  • B > 15，已使用的溢出桶个数 >= 2^{15} 时，引发等量扩容

2. 扩容类型

• 翻倍扩容：负载因子过高；翻倍扩容会将桶的数量翻倍，然后将旧桶中的键值对重新分配到新的桶中（也会清理一些删除的 key）

• 等量扩容：溢出桶过多；主要是因为溢出桶过多而触发扩容时，会进行等量扩容

  • 等量扩容并不会增加桶的数量，而是重新组织数据，将旧桶中的键值对重新分配到新的桶中，以减少溢出桶的数量

func hashGrow(t *maptype, h *hmap) {
    // If we've hit the load factor, get bigger.
    // Otherwise, there are too many overflow buckets,
    // so keep the same number of buckets and "grow" laterally.
    bigger := uint8(1)
    if !overLoadFactor(h.count+1, h.B) {
        bigger = 0
        h.flags |= sameSizeGrow
    }
    oldbuckets := h.buckets
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
    ...
}

扩容后：

• B会根据扩容后新桶的个数进行增加（翻倍扩容新B=旧B+1，等量扩容 新B=旧B）

• oldbuckets指向原来的桶（旧桶）

• buckets指向新创建的桶（新桶中暂时还没有数据）

• nevacuate设置为0，表示如果数据迁移的话，应该从原桶（旧桶）中的第0个位置开始迁移

• noverflow设置为0，扩容后新桶中已使用的溢出桶为0

• extra.oldoverflow设置为原桶（旧桶）已使用的所有溢出桶。即：h.extra.oldoverflow = h.extra.overflow

• extra.overflow设置为nil，因为新桶中还未使用溢出桶

• extra.nextOverflow设置为新创建的桶中的第一个溢出桶的位置。

3. 扩容步骤：迁移式 rehash

• 步骤 1：分配新的桶数组

        等量扩容：分配一个与旧桶数组大小相同的新桶数组。

        翻倍扩容：分配一个大小为旧桶数组两倍的新桶数组。

• 步骤 2 ： 设置扩容标记

        在 hmap 结构体中设置相应的标记，指示 map 正在进行扩容操作。同时，将新桶数组的指针保存到 hmap 中。

• 步骤 3：渐进式迁移数据

        Go 语言的 map 扩容采用渐进式迁移的方式，即不是一次性将所有旧桶中的键值对迁移到新桶中，而是在后续的插入、删除和查找操作中，逐步将旧桶中的键值对迁移到新桶中。

        具体过程如下：

        每次操作迁移少量数据：在每次对 map 进行插入、删除或查找操作时，会检查是否正在进行扩容。如果正在扩容，会将旧桶中的部分键值对迁移到新桶中。

        每次迁移的键值对数量是有限的，通常是一个桶中的所有键值对。

        更新桶的状态：在迁移键值对时，会更新旧桶和新桶的状态，标记哪些桶已经迁移完成。

• 步骤 4：完成扩容

        当所有旧桶中的键值对都迁移到新桶中后，扩容操作完成。此时，会释放旧桶数组的内存，并将 hmap 中的桶指针指向新桶数组。

三、常见问题

1.  bmap 的数量为什么是 2^B 次方？

方便位运算，bitmap

2.  为什么要进行等量扩容？

让元素更加紧凑，刚好利用内存，比如 map 中有 1000 个 元素，但是可能存在一些删除的元素，应该将溢出桶的元素迁移到删除的元素的位置

3.  bmap 中的 tophash 是什么有什么作用？

tophash 是 key 哈希值的高八位，主要用来快速比较两个键是否相同

比如现在 插入 key name ，则在确定桶之后， 获取 name 的哈希值的高八位和 bmap 中的 tophash 快速判断比较 key 是否存在，存在的下标

从而到 key 和 value 数组中根据下标获取数据，

不直接比较 key 是因为 key 可能会很大，tophash 比较会快速很多

4.  map 的 value 为什么不可寻址？

key 通过 hash 算出具体的 bucket，然后将 key 和 value 复制 到 bucket，不是指针引用，所以不可寻址，

如果用指针寻址的话，在扩容迁移时， map 进行了扩容或者重新分配内存，原来的指针地址无效，发送程序错误，因此设计为不可寻址

5.  map 是如何解决哈希冲突的？

哈希冲突碰撞：多个 key 的 hash 结果一致，hash 到同一个 bucket，解决方法：

• 链表法： 将一个 bucket 实现成一个链表，落在同一个 bucket 中的 key 都会插入这个链表

• 开放寻址法： 则是碰撞发生后，通过一定的规律，在数组的后面挑选“空位”，用来放置新的 key

go map 采用的是 链表法，使用 溢出桶 来存放 相同 hash 结果的 value

6.  为什么 map 是无序的？

• hash 结果本身就是无序的

• map 扩容之后，key 会发生迁移

• map底层在遍历的时候也是无序遍历的，并不是从第一个桶开始依次遍历

7.  map 使用时需要注意哪些问题？

• key 必须是可比较的类型，如整数、字符串和指针等，但是切片、函数和结构体等类型是不可比较的，因此不能用作键

• Map 中的元素是无序的

• 如果使用未初始化的 Map，会导致运行时错误。需要使用 make() 函数来初始化 Map。

• Map 在并发环境下不是安全的

8.  map 是如何进行扩容的？

• 当 Map 中的元素数量超过了负载因子（load factor）和哈希表容量的乘积时，map 就会触发扩容操作。在 Go 中，负载因子默认为 6.5。

• Go Map 在扩容时会创建一个新的哈希表，非一次性（渐进式）将原来的键值对重新散列到新的哈希表中。为了减少哈希冲突，新哈希表的容量是原来的两倍，并且容量一定是 2 的幂次方。

• 在重新散列过程中，Go Map 会根据哈希值将原来的键值对分配到新哈希表中的对应位置上。如果两个键值对的哈希值相同，会使用链式哈希表（chained hash table）的方式进行处理，将它们放在同一个桶（bucket）中。

• 一旦所有的键值对都已经重新散列到新的哈希表中，Go Map 就会将原来的哈希表释放掉，将新的哈希表作为 Map 的内部存储结构。

注意：  由于扩容操作可能会导致大量的重新散列操作，因此在扩容时可能会造成一定的性能影响。为了避免频繁扩容，可以在创建 Map 时指定一个较大的容量，或者手动调用 runtime.GC()  来触发垃圾回收操作，以释放未使用的内存。

9.  map 的 panic 能被 recover 吗？

• 不能，直接抛出 throw("concurrent map read and map write")

10.  并发使用 map 除了加锁还有其他方案吗？

多读少写的情况，建议使用 sync.Map

11.  sync.Map 和加锁有什么区别？

• 不需要显式的加锁/解锁

• 降低锁的粒度，适用 多读少写 场景，读是原子操作，不需要加锁

12.  Map 的查询时间复杂度？

正常情况下是 O (1)，极端情况下，也就是哈希冲突碰撞严重情况下：O (N)，需要遍历溢出桶

13.  Map Rehash 的策略是怎样的？什么时机会发生 Rehash？

rehash 也就是 扩容、迁移；在 map 元素达到一定条件的情况下，发生扩容操作：

rehash 的策略：增量式 rehash，在新增 key 的情况下逐步将 oldbuckets 元素迁移到 buckets

14.  Map rehash 具体会影响什么？哈希结果会受到什么影响？

只会影响 key 在 map 中的存储位置，不会改变哈希结果

15.  Map Rehash 过程中存放在旧桶的元素如何迁移？

在 新增 key 时 逐步增量迁移

16.  sync.Map 的 Load() 流程

17. sync.Map Store() 如何保持缓存层和底层 Map 数据是相同的?