SpaceX
深入剖析map结构
编辑
2024-07-22
服务端
0
请注意，本文编写于 88 天前，最后修改于 73 天前，其中某些信息可能已经过时。

目录

基本用法
声明和初始化
基本操作
底层实现
hmap
bmap
常用操作
新建
查询
扩容机制
扩容方式
等量扩容
双倍容量扩容
常见问题
原生map中删除元素，内存会自动释放吗？
slices能作为map类型的key吗？

Go语言中的map是一种内置的数据结构，用于存储键值对。map提供了快速查找、插入和删除操作，是实现字典和哈希表的基础。大多数情况下，它都能在O(1)的时间复杂度下实现增删改查功能，若在极端情况下出现所有key都发生哈希碰撞时则退回成链表形式，此时时间复杂度为O(N)。由于哈希表在使用过程中可能会发生内存分配，因此哈希表一般是不允许并发读写的。

基本用法

声明和初始化

使用make函数：

go
m := make(map[string]int, 10) // 创建一个初始容量为10的map

使用字面量：

go
m := map[string]int{
   "one": 1,
   "two": 2,
   "three": 3,
}

基本操作

插入和更新元素：

go
m["four"] = 4
m["one"] = 11 // 更新已有的键值对

获取元素：

go
val := m["one"]

删除元素：

go
delete(m, "two")

检查键是否存在：

go
val, ok := m["three"]
if ok {
   fmt.Println("Key exists with value:", val)
} else {
   fmt.Println("Key does not exist")
}

遍历map：

go
for key, value := range m {
   fmt.Println(key, value)
}

底层实现

Go语言的map底层是一个哈希表，由多个哈希桶（bucket）组成。每个桶可以存储若干个键值对和一些元数据。它使用hash函数将key分配到不同桶中，若出现碰撞冲突时候，则采用链地址法或者开放寻址法解决冲突。 在哈希函数的选择上，会在程序启动时，检测cpu是否支持 AES，如果支持，则使用 AES hash，否则使用 memhash。

冲突解决

  • 链地址法：即每个哈希桶内部维护一个链表，当发生冲突时，将新元素添加到链表中。
  • 开放地址法：当多个键映射到同一个哈希桶时，通过线性探测或二次探测等方法找到下一个空闲的桶位置。

源码中，map主要涉及的结构体有两个，一个叫 hmap（a header for a go map），一个叫 bmap（a bucket for a Go map，通常叫 bucket）。

hmap

下图是完整的关系图

map的结构是 runtime.hmap

go
// A header for a Go map.
type hmap struct {
    count     int                  // 元素个数
    flags     uint8                // 标志位，标志当前map正在写等状态
    B         uint8                // 扩容常量相关字段B是buckets数组的长度的对数 2^B
    noverflow uint16               // 溢出的bucket个数
    hash0     uint32               // 随机数种子，用于计算key的哈希值
    buckets    unsafe.Pointer      // 指向buckets数组，如果元素个数为0时，该值为nil
    oldbuckets unsafe.Pointer      // 结构扩容的时候用于赋值的buckets数组
    nevacuate  uintptr             // 搬迁进度
    extra *mapextra                // 用于扩容的指针，额外记录overflow桶信息
}

可以看到，hamp中有个buckets字段，它是一个指针，最终它指向的桶，是一个结构体bmp

bmap

bmap 就是我们常说的“桶”，它的结构是 runtime.bmap

go
// A bucket for a Go map.
type bmap struct {
    // tophash存储桶内每个key的hash值的高字节
    // tophash[0] < minTopHash表示桶的疏散状态
    // 当前版本bucketCnt的值是8，一个桶最多存储8个key-value对
    tophash [bucketCnt]uint8
}

上面bmap结构是静态结构，在编译过程中 runtime.bmap 会拓展成下面这个新的结构体：

go
type bmap struct{
	tophash [8]uint8
	keys [8]keytype // keytype 由编译器编译时候确定
	values [8]elemtype // elemtype 由编译器编译时候确定
	overflow uintptr // overflow指向下一个bmap，overflow是uintptr而不是*bmap类型，是为了减少gc
}

bmap里面会最多装 8 个 key，这些 key 之所以会落入同一个桶，是因为它们经过哈希计算后，哈希结果是“一类”的。在桶内，又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置（一个桶内最多有8个位置）。

bmap中tophash就是用于实现快速定位key的位置。tophash计算公式如下：

go
func tophash(hash uintptr) uint8 {
	top := uint8(hash >> (sys.PtrSize*8 - 8))
	if top < minTopHash {
		top += minTopHash
	}
	return top
}

上面函数中hash是64位的，sys.PtrSize值是8，所以top := uint8(hash >> (sys.PtrSize*8 - 8))等效top = uint8(hash >> 56)，最后top取出来的值就是hash的最高8位值。bmap的tophash字段不光存储key哈希值的高八位，还会存储一些状态值，用来表明当前桶单元状态，这些状态值都是小于minTopHash的。

为了避免key哈希值的高八位值出现这些状态值相等产生混淆情况，所以当key哈希值高八位若小于minTopHash时候，自动将其值加上minTopHash作为该key的tophash。桶单元的状态值如下：

go
emptyRest      = 0 // 表明此桶单元为空，且更高索引的单元也是空
emptyOne       = 1 // 表明此桶单元为空
evacuatedX     = 2 // 用于表示扩容迁移到新桶前半段区间
evacuatedY     = 3 // 用于表示扩容迁移到新桶后半段区间
evacuatedEmpty = 4 // 用于表示此单元已迁移
minTopHash     = 5 // key的tophash值与桶状态值分割线值，小于此值的一定代表着桶单元的状态，大于此值的一定是key对应的tophash值

bmap中可以装载8个key-value，这8个key-value并不是按照key1/value1/key2/value2/key3/value3…这样形式存储，而采用key1/key2../key8/value1/../value8形式存储，因为第二种形式可以减少padding，源码中以map[int64]int8举例说明。 hmap中extra字段是 runtime.mapextra 类型，用来记录额外信息：

go
// mapextra holds fields that are not present on all maps.
type mapextra struct {
	overflow    *[]*bmap // 指向overflow桶指针组成的切片，防止这些溢出桶被gc了
	oldoverflow *[]*bmap // 扩容时候，指向旧的溢出桶组成的切片，防止这些溢出桶被gc了

	//指向下一个可用的overflow 桶
	nextOverflow *bmap
}

当映射的key和value都不是指针类型时候，bmap将完全不包含指针，那么gc时候就不用扫描bmap。bmap指向溢出桶的字段overflow是uintptr类型，为了防止这些overflow桶被gc掉，所以需要mapextra.overflow将它保存起来。如果bmap的overflow是*bmap类型，那么gc扫描的是一个个拉链表，效率明显不如直接扫描一段内存(hmap.mapextra.overflow)

常用操作

新建

新建map命令，以a := make(map[string]string, len) 为例

  1. 初始化map的结构体hmap
  2. 计算hmap的buckets数量，用hmap.B记录。如果len < 8，hmap.B = 0; 如果len大于8，hmap.B等于len下一个2的指数倍。比如len =14，下一个2的倍速就是16，2^4 = 16,所以hmap.B = 4
  3. 新建 2 ^ hmap.B 个buckets
go
// make(map[k]v, hint), hint即预分配大小
// 不传hint时，如用new创建个预设容量为0的map时，makemap只初始化hmap结构，不分配hash数组
func makemap(t *maptype, hint int, h *hmap) *hmap {
    //初始化hmap结构体
    if h == nil {
        h = new(hmap)
    }
    h.hash0 = fastrand()
    //hint > 8, B一直增长到2的倍数
    B := uint8(0)
        // overLoadFactor(hint, B)只有一行代码：return hint > bucketCnt && uintptr(hint) > loadFactorNum*(bucketShift(B)/loadFactorDen)
        // 即B的大小应满足 hint <= (2^B) * 6.5
        // 一个桶能存8对key-value，所以这就表示B的初始值是保证这个map不需要扩容即可存下hint个元素对的最小的B值
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B
    if h.B != 0 {
        //新建B个buckets，有可能需要新建overflow bucket (B值过大情况下)
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }
    return h
}

查询

  1. 假定B=5，bukets总数是2^5 = 32。计算key散列函数之后的hash值kHash
  2. 根据kHash低5位00110计算确定 bucket 的内存地址, 找到对应6号bucket。
  3. 使用高 8 位 10010111，对应十进制 151，在 6 号 bucket 中寻找 tophash 值（HOB hash）为 151 的 key，找到了 2 号槽位，这样整个查找过程就结束了
  4. 如果在 bucket 中没找到，并且 overflow 不为空，还要继续去 overflow bucket 中寻找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket
go
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    //如果有goroutine正在写入map，则不允许读。所以map是非线程安全的
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    ......
    //确定key所在的bucket内存地址
    m := bucketMask(h.B)
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    //如果oldbuckets里面有值，从oldbuckets取值
    if c := h.oldbuckets; c != nil {
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {
            b = oldb
        }
    }
    //获取key hash算法之后的高8位
    top := tophash(hash)
bucketloop:
    for ; b != nil; b = b.overflow(t) {
        //bucketCnt = 8，遍历tophash数组，tophash[i]等于kHash高8位的i值 并且 bucket的第i个的key与所给的key相等的value值
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                continue
            }
            //对比 bucket的第i个的key与所给的key是否相等，相等就取对应的value值
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if alg.equal(key, k) {
                v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                return v
            }
        }
    }
    return unsafe.Pointer(&zeroVal[0])
}

扩容机制

map使用哈希表的目的就是要快速查找到目标 key，然而，随着向 map 中添加的 key 越来越多，key 发生碰撞的概率也越来越大。bucket 中的 8 个 cell 会被逐渐塞满，查找、插入、删除 key 的效率也会越来越低。最理想的情况是一个 bucket 只装一个 key，这样，就能达到 O(1) 的效率，但这样空间消耗太大，用空间换时间的代价太高。

在golang中，采用一个 bucket 里装载 8 个 key，定位到某个 bucket 后，还需要再定位到具体的 key，这实际上又用了时间换空间。当然，必须有一个度，不然所有的 key 都落在了同一个 bucket 里，直接退化成了链表，各种操作的效率直接降为 O(n)。

因此，需要有一个指标来衡量前面描述的情况，这就是装载/负载因子（load factor），它是哈希表中元素数量与哈希桶数量的比值。Go 源码里是这样定义装载因子的：

go
loadFactor := count / (2^B)

其中，count 就是 map 的元素个数，2^B 表示 bucket 数量。

map扩容的触发条件主要是基于装载因子（load factor），在超过某个阈值时会进行扩容。具体的阈值和扩容策略可能会根据Go语言的版本有所不同。 触发条件

  • 装载因子超过阈值，源码里定义的阈值是 6.5。
  • overflow数量 > 2^15时，也即overflow数量超过32768时。
go
// src/runtime/hashmap.go/mapassign
// 触发扩容时机
if !h.growing() && (overLoadFactor(int64(h.count), h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
                hashGrow(t, h)
        }

// 条件1 装载因子超过 6.5
func overLoadFactor(count int64, B uint8) bool {
        return count >= bucketCnt && float32(count) >= loadFactor*float32((uint64(1)<<B))
}

// 条件2 overflow buckets 太多
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
        if B < 16 {
                return noverflow >= uint16(1)<<B
        }
        return noverflow >= 1<<15
}

扩容方式

go会采用采用渐进式扩容，避免一次性迁移数据过多造成性能问题。在进行新增、更新时候会触发扩容操作然后进行扩容操作，每次最多迁移2个bucket。我们常见的有以下两种扩容类型。

等量扩容

所谓等量扩容，实际上并不是扩大容量，buckets数量不变，重新做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，以使bucket的使用率更高，进而保证更快的存取。

上面说的 hashGrow() 函数实际上并没有真正地“搬迁”，它只是分配好了新的 buckets，并将老的 buckets 挂到了 oldbuckets 字段上。真正搬迁 buckets 的动作在 growWork() 函数中，而调用 growWork() 函数的动作是在 mapassign 和 mapdelete 函数中。也就是插入或修改、删除 key 的时候，都会尝试进行搬迁 buckets 的工作。先检查 oldbuckets 是否搬迁完毕，具体来说就是检查 oldbuckets 是否为 nil。

双倍容量扩容

当装载因子过大时，就新建一个bucket，新的bucket长度是原来的2倍，然后旧bucket数据搬迁到新的bucket。 总结来说，不论是等容量扩容，还是双倍容量扩容，都会新创建一个buckets，然后将hmap.buckets指向这个新的buckets，hmap.oldbuckets指向旧的buckets。

常见问题

原生map中删除元素，内存会自动释放吗？

  • 如果删除的元素是值类型，如int，float，bool，string以及数组和struct，map的内存不会自动释放；
  • 如果删除的元素是引用类型，如指针，slice，map，chan等，map的内存会自动释放，但释放的内存是子元素应用类型的内存占用；
  • 将map设置为nil后，内存被回收；

slices能作为map类型的key吗？

在golang规范中，可比较的类型都可以作为map key。不能作为map key 的类型包括：

  • slices
  • maps
  • functions

本文作者:sora

本文链接:

版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！