Go

Map 实现

Golang 中 map 的底层实现是一个哈希表（hash table），具体来说是一个 bucket 数组。以下是其核心数据结构和实现细节：

主要数据结构

在 Go 语言源码（ runtime/map.go ）中，map 主要由以下结构组成：

  1. hmap （map 的头部结构）
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

type hmap struct {
    count     int    // map 中的元素个数
    flags     uint8  // 状态标志
    B         uint8  // 桶（bucket）数组的大小指数，即桶数量为 2^B
    noverflow uint16 // 溢出桶的近似数量
    hash0     uint32 // 哈希种子

    buckets    unsafe.Pointer // 桶数组指针，数组大小为 2^B
    oldbuckets unsafe.Pointer // 扩容时的旧桶数组
    nevacuate  uintptr       // 扩容时已迁移的桶数量

    extra *mapextra // 额外信息
}
  1. bucket （桶结构）
1
2
3
4
5
6
7

type bmap struct {
    tophash [bucketCnt]uint8 // 存储哈希值的高 8 位，用于快速比较
    // 在这个结构体定义后面 (runtime 内部) 实际还包含以下字段：
    // keys     [bucketCnt]keytype
    // values   [bucketCnt]valuetype
    // overflow *bmap
}

其中 bucketCnt 通常是 8，表示每个桶可以存储 8 个键值对。

工作原理

  1. 哈希计算与桶定位

    • 使用哈希函数计算 key 的哈希值
    • 低位用于选择桶（buckets 数组索引）
    • 高 8 位存储在 tophash 数组中，用于快速比较

  2. 键值对存储结构

    • 每个桶中的键值对不是以键值对的形式交替存储的
    • 而是将所有的 key 放在一起，所有的 value 放在一起
    • 这样做可以优化内存对齐

  3. 溢出桶处理

    • 当一个桶装满 8 个键值对后，会链接到一个溢出桶
    • 溢出桶是从预先分配的溢出桶数组中获取的

  4. 扩容机制

    • 当 map 中的元素数量 > 桶数量 * 6.5（负载因子）时，会触发扩容
    • 或者当溢出桶过多时，也会触发扩容

    • 扩容分为两种类型：

      • 增量扩容：桶数量翻倍（B 值加 1）
      • 等量扩容：桶数量不变，但重新排列元素减少溢出桶

  5. 渐进式迁移

    • 扩容不是一次性完成的，而是渐进式的
    • 每次 map 操作会迁移少量数据
    • 迁移完成前，查找需要同时查询新旧两个桶数组

特殊实现细节

  1. 内存布局优化

    • bucket 结构中，key 和 value 分开存储，可以减少内存填充
    • 小于 128 字节的 key 和 value 直接存储在桶中，大的值存储为指针

  2. 随机遍历顺序

    • map 的遍历顺序是随机的，这是故意设计的
    • 防止程序依赖于特定的遍历顺序

  3. 空 map 和 nil map 的区别

    • nil map 是未初始化的 map，不能添加元素
    • 空 map 是已初始化但没有元素的 map，可以添加元素

  4. 并发不安全

    • 标准库的 map 不是并发安全的
    • 并发读写会导致程序 panic

通过这种复杂而精心设计的数据结构，Go 的 map 实现了高效的增删改查操作，同时在内存使用和性能上做了很好的平衡。