这是本节的多页打印视图。 点击此处打印.

返回本页常规视图.

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 实现了高效的增删改查操作，同时在内存使用和性能上做了很好的平衡。