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

返回本页常规视图.

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