• 2026年1月18日
• 分类于 源码分析
• 需要 10 分钟阅读时间

Golang源码分析系列之Map底层实现

映射也被称为哈希表(hash table)、字典。它是一种由key-value组成的抽象数据结构。大多数情况下，它都能在O(1)的时间复杂度下实现增删改查功能。若在极端情况下出现所有key都发生哈希碰撞时则退回成链表形式，此时复杂度为O(N)。

映射底层一般都是由数组组成，该数组每个元素称为桶，它使用hash函数将key分配到不同桶中，若出现碰撞冲突时候，则采用链地址法（也称为拉链法）或者开放寻址法解决冲突。下图就是一个由姓名-号码构成的哈希表的结构图：

Go语言中映射中key若出现冲突碰撞时候，则采用链地址法解决，Go语言中映射具有以下特点：

• 引用类型变量
• 读写并发不安全
• 遍历结果是随机的

数据结构

Go语言中映射的数据结构是runtime.hmap(runtime/map.go):

// A header for a Go map.
type hmap struct {
    count     int //  元素个数，用于len函数返回map元素数量
    flags     uint8 // 标志位，标志当前map正在写等状态
    B         uint8  // buckets个数的对数，即桶数量 = 2 ^ B
    noverflow uint16 // overflow桶数量的近似值，overflow桶即溢出桶，即链表法中存在链表上的桶的个数
    hash0     uint32 // 随机数种子，用于计算key的哈希值

    buckets    unsafe.Pointer // 指向buckets数组，如果元素个数为0时，该值为nil
    oldbuckets unsafe.Pointer // 扩容时指向旧的buckets
    nevacuate  uintptr        // 用于指示迁移进度，小于此值的桶已经迁移完成

    extra *mapextra // 额外记录overflow桶信息
}