返回主题:内置数据结构的底层实现

知识卡片

普通读书笔记卡 · 1474.a.1

渐进扩容

理解等级:未标注

书中旧版 Go map 扩容时先保留旧桶,后续写入逐步迁移相关桶,避免单次搬完整张表。它体现以多次操作分摊迁移成本的设计取舍。Go 1.24 起内置 map 改用 Swiss Table,不能把这套旧桶迁移机制当作现行实现。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《Go语言底层原理剖析》第8章《哈希表与Go语言实现机制》8.5.5节《map重建原理》 - 结论依据:原文说明旧桶迁移不在触发扩容时一次完成,而由后续写入逐步触发,因此可得出书中旧版运行时的渐进迁移结论。Go 官方 2025 年文档说明 Go 1.24 切换 Swiss Table,故本卡将其限定为旧版实现;“写时复制”是原书称呼,不据此推断持久化数据结构语义。 - 原始内容:重建时需要调用hashGrow函数……新桶会存储到buckets字段,旧桶会存储到oldbuckets字段……要注意的是,这里并没有实际执行将旧桶中的数据转移到新桶的过程。数据转移遵循写时复制(copy on write)的规则,只有在真正赋值时,才会选择是否需要进行数据转移,其核心逻辑位于growWork和evacuate函数中。在进行写时复制时,并不是所有的数据都一次性转移,而是只转移当前需要的旧桶中的数据。