Sirius
所有文章 标签 分类 系列 关于
Sirius

目录

目录

Golang map

Fan avatarFan  收录于  类别 Golang 和 系列 Golang系列
     约 2501 字   预计阅读 11 分钟 
系列 - Golang系列

好的，我们来深入地讲解 Go 语言内置 map 的实现原理，并包含一个 Mermaid 结构图来帮助理解。

Go 的 map 是一个高度优化的哈希表实现。它在设计上兼顾了高性能的平均查找、插入、删除操作，并通过一个独特的渐进式扩容机制，避免了在扩容时产生长时间的程序暂停 (STW - Stop-The-World)。

Go map 的实现主要围绕两个核心的内部结构体：hmap 和 bmap。

  1. hmap (哈希表头结构)

    hmap 是 map 的“头部”或“描述符”。当我们声明一个 map 变量时，这个变量实际上就是一个指向 hmap 结构体的指针。它包含了 map 的所有元信息：

    // runtime/map.go 中的 hmap 结构体（简化版）
type hmap struct {
    count     int    // map中元素的数量
    B         uint8  // 桶的数量，实际桶数量为 2^B
    hashseed  uint32 // 哈希种子，用于计算哈希值，防止哈希冲突攻击
    buckets   unsafe.Pointer // 指向桶数组的指针，大小为 2^B
    oldbuckets unsafe.Pointer // 扩容时，指向旧的桶数组的指针，否则为 nil
    nevacuate uintptr      // 扩容进度计数器，指向下一个需要迁移的旧桶
    // ... 其他字段
}
graph TB

subgraph "Go Map Structure"

H[hmap header] --> B[buckets array]

H --> OB[oldbuckets array]

H --> E[extra info]

B --> B0[bucket 0]

B --> B1[bucket 1]

B --> B2[bucket 2]

B --> BN[bucket N]

B0 --> OF0[overflow bucket]

B1 --> OF1[overflow bucket]

style H fill:#ff9999

style B fill:#99ff99

style OB fill:#ffcc99

end

  1. bmap (哈希桶结构)

    bmap 就是所谓的“桶” (Bucket)，是真正存储键值对的地方。

    • 每个桶固定可以存放 8 个 键值对。

    • 为了加速查找，它并不会直接存放完整的 key，而是先存放 key 的哈希值的高8位 (tophash)。

    • 当一个桶存满后，它会通过一个 overflow 指针链接到一个“溢出桶”，形成一个链表结构。这就是拉链法 (Chaining) 解决哈希冲突的方式。

    bmap 的内存布局大致如下：

    // runtime/map.go 中的 bmap 结构体（简化版）
type bmap struct {
    tophash  [8]uint8       // 存储8个key的tophash值（哈希值的高8位）
    keys     [8]keytype     // 8个key，紧随tophash之后
    values   [8]valuetype   // 8个value，紧随keys之后
    overflow unsafe.Pointer // 指向溢出桶的指针
}

    tophash 的存在是一个关键优化。在查找 key 时，可以先快速地比较这 8 个字节，只有当 tophash 匹配时，才需要去比较完整的、可能很长的 key，大大提高了查找效率。

graph TD
    subgraph Map Variable
        m_ptr["map[K]V (指针)"]
    end

    subgraph hmap [hmap 结构体]
        count["count: 元素数量"]
        B["B: log2(桶数量)"]
        buckets_ptr["buckets (指针)"]
        oldbuckets_ptr["oldbuckets (指针)"]
    end
    
    subgraph Buckets Array ["桶数组 (2^B 个 bmap)"]
        bmap0["Bucket 0 (bmap)"]
        bmap1["Bucket 1 (bmap)"]
        bmap_etc["..."]
        bmap_last["Bucket N (bmap)"]
    end

    subgraph bmap1_detail [Bucket 1 内部结构]
        tophash1["tophash[8] (高8位哈希)"]
        kv_pairs1["K/V 对 (8个)"]
        overflow_ptr1["overflow (指针)"]
    end

    subgraph bmap_overflow_detail [溢出桶 内部结构]
        tophash_ovf["tophash[8]"]
        kv_pairs_ovf["K/V 对 (8个)"]
        overflow_ptr_ovf["overflow (指针)"]
    end
    
    m_ptr --> hmap;
    hmap --> buckets_ptr;
    buckets_ptr --> bmap0;
    buckets_ptr --> bmap1;
    buckets_ptr --> bmap_etc;
    buckets_ptr --> bmap_last;
    
    bmap1 --> tophash1;
    bmap1 --> kv_pairs1;
    bmap1 --> overflow_ptr1;
    
    overflow_ptr1 --> bmap_overflow_detail;

  1. Go 运行时会为每个 map 实例在创建时生成一个随机的哈希种子 (hashseed)。

  2. 对一个 key 进行哈希时，会使用与 key 类型对应的哈希算法，并结合这个 hashseed 来计算出一个 64 位的哈希值。

  3. 这个哈希值被分为两部分：

    • 低 B 位: 用于在 buckets 数组中定位到具体的桶。例如，如果 B=5，则有 2^5=32 个桶，哈希值的低5位就决定了 key 属于哪个桶。

    • 高 8 位: 作为 tophash 存入桶中，用于快速筛选。

value, ok := m[key] 的过程：

  1. 计算 key 的哈希值，得到桶索引和 tophash。

  2. 根据桶索引找到对应的 bmap。

  3. 遍历该 bmap 的 tophash 数组，将目标 tophash 与这 8 个值进行比较。

  4. 如果 tophash 匹配，再比较完整的 key 是否相等。

  5. 如果 key 相等，则找到了目标，返回对应的 value 和 true。

  6. 如果遍历完当前桶仍未找到，并且 overflow 指针不为 nil，则顺着指针跳转到溢出桶，重复步骤 3-5。

  7. 如果所有桶（包括溢出桶）都找完了仍未找到，则返回 value 的零值和 false。

m[key] = value 的过程：

  1. 首先执行与查找相同的流程，以确定 key 是否已经存在。

  2. 如果 key 已存在，直接更新对应的 value，操作结束。

  3. 如果 key 不存在，就在当前桶（或其溢出桶链表）中寻找一个空的槽位。

  4. 找到空槽位后，将 tophash、key 和 value 存入，并使 hmap.count 加一。

  5. 如果在所有桶中都找不到空槽位，则创建一个新的溢出桶，链接到链表末尾，并将新元素存入新溢出桶的第一个槽位。

  6. 每次插入后，都会检查是否需要扩容。

delete(m, key) 的过程：

  1. 执行与查找相同的流程，找到 key 所在的槽位。

  2. 如果找到了，就将该槽位的 key 和 value 清零（设置为类型的零值），并将对应的 tophash 设置为一个特殊状态（例如 emptyRest），表示此槽位为空，但可能后面还链接着其他元素。

flowchart TD

A["map[key] = value"] --> B["计算 hash(key)"]

B --> C[提取低B位]

C --> D[定位bucket]

D --> E{bucket已满?}

E -->|否| F[找到空位插入]

E -->|是| G[创建overflow bucket]

G --> H[链接到原bucket]

H --> F

F --> I[更新count]

J["value := map[key]"] --> K["计算 hash(key)"]

K --> L[提取低B位]

L --> M[定位bucket]

M --> N[遍历bucket链]

N --> O{找到key?}

O -->|是| P[返回value]

O -->|否| Q[返回零值]

style A fill:#ff9999

style J fill:#99ff99

这是 Go map 设计的精髓之一，它避免了像 Java HashMap 那样在扩容时需要一次性 rehash 所有元素而导致的长时间卡顿。

当 map 的负载因子 (load factor) 超过一个阈值（默认为 6.5）时，会触发扩容。

  • 负载因子 = hmap.count / (2^B)

  1. 分配新空间：当触发扩容时，Go 会分配一个两倍于旧桶数组大小的新桶数组。hmap.oldbuckets 指向旧的桶数组，hmap.buckets 指向新的桶数组。

  2. 不立即迁移数据：此时不会立即将所有数据从旧桶迁移到新桶。

  3. 平摊式迁移：迁移工作被“平摊”到后续的每一次插入和删除操作中。

    • 当一个写操作（插入或删除）发生时，如果它定位到的桶还没有被迁移，Go 运行时会顺便将这个旧桶中的所有数据 rehash 并迁移到新桶数组的对应位置（通常一个旧桶的数据会分散到两个新桶中）。

    • hmap.nevacuate 计数器记录了迁移进度。

  4. 迁移期间的读操作：如果读操作定位到的桶还在旧桶数组中，则直接从旧桶中读取。

  5. 迁移完成：当所有的旧桶都迁移到新桶后 (nevacuate 完成计数)，hmap.oldbuckets 指针被设为 nil，扩容过程正式结束。

这种设计使得单次操作的耗时更加平滑，代价是扩容期间 map 会占用约两倍的内存空间，并且操作的平均耗时会略有增加。但对于追求低延迟的后端服务来说，这是一个非常值得的权衡。

sequenceDiagram

participant M as Map

participant OB as Old Buckets

participant NB as New Buckets

Note over M: 负载因子 > 6.5 或 overflow太多

M->>NB: 创建新bucket数组 (2倍大小)

M->>M: 设置oldbuckets = buckets

M->>M: 设置buckets = newbuckets

loop 渐进式迁移

M->>OB: 读取老bucket

M->>M: 重新计算hash分布

M->>NB: 迁移到新bucket位置

Note over M: 每次操作迁移1-2个bucket

end

M->>OB: 清理oldbuckets

Note over M: 迁移完成
更新于 2025-07-02
阅读原始文档 | 查看源代码 | 报告问题
 | 主页