知识卡片
旧桶布局先筛哈希再比键
Go1.12的map用哈希低位选择桶,再以桶内tophash筛选可能位置,最后核对键。高位摘要先过滤,能够减少较大键的逐个比较;桶满后还可链接溢出桶。
这是书中旧版实现的解释,不是map公开语义。Go1.24已切换SwissTable实现,不能把八槽桶、溢出链或固定负载阈值当作当前所有版本的结构。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
其中低位区的值用于选定bucket,高位区的值用于在某个bucket中确定key的位置。这个过程可参考图14-2。 图14-2 hashcode的作用 因此,每个bucket的tophash区域是用于快速定位key位置的
参考来源
- 位置:《Go语言精进之路 _ 从新手到高手的编程思想,方法和技巧 = Go programming from beginners》第14章《14.3 map的内部实现》(来源项目book-sources:extracted/Go语言精进之路 _ 从新手到高手的编程思想,方法和技巧 = Go programming from beginners/_epub-src/Text/Chapter14_0003.xhtml;spine 59,归一字符[1783,1893))
- 结论依据:原文限定Go1.12并解释hashcode两部分,官方SwissTable文章已核验新版边界。
- 原始内容:其中低位区的值用于选定bucket,高位区的值用于在某个bucket中确定key的位置。这个过程可参考图14-2。 图14-2 hashcode的作用 因此,每个bucket的tophash区域是用于快速定位key位置的