Golang Map

源码位置

runtime/map.go

底层结构

代码语言：txt复制

type hmap struct {
    count int // 元素个数
    flags uint8
    B uint8 // 桶数量, 2^B个
    noverflow uint16 // 使用的溢出桶数量
    hash0 uint32 // 哈希种子

    buckets unsafe.Pointer // 桶指针
    oldbuckets unsafe.Pointer // 旧桶指针，只在扩容时非空
    nevacuate uintptr // 记录扩容进度,记录下一个迁移的桶编号

    extra *mapextra // 溢出桶信息
}

type bmap struct {
    tophash [8]uint8 // 存哈希值高8位
}

实际bmap后会紧跟8个key和8个value以及溢出桶指针，即类似以下结构

代码语言：txt复制

type bmap struct {
    tophash [8]uint8 // 存哈希值高8位
    keys [8]KeyType
    values [8]ValueType
    overflow *bmap
}

示例图

image.png

注：实际h、k、v并不一定对齐，取决于map的key和value的类型

初始化流程

image.png

B>=4的情况会提前分配2^(B-4)个溢出桶

扩容

负载因子：元素数量/桶数量，即count/2^B

两种扩容情况，一种是增量扩容，一种是等量扩容

等量扩容是在大量删除key的情况下，重新分配k、v排列，减少空间、及溢出桶的使用

扩容规则：

1.翻倍扩容

count/2^B > 6.5，触发翻倍扩容，B

2.等量扩容

B <= 15的情况，count >=2^B即触发等量扩容

B > 15的情况，count >= 2^15即触发等量扩容

渐进式扩容：扩容并非一次性完成所有桶迁移，而是在map操作时分多次完成迁移，防止性能瞬时抖动

迁移 count key map runtimemap golang

0 人点赞