知识卡片
哈希扩容需要重新分桶
桶数量参与索引计算,容量变化后原来的桶位置一般不再正确。扩容要遍历所有有效键值,按新容量重算索引并放入新表,再让新表接管查询。
这和单纯把数组尾部加长不同,搬迁及哈希计算有实际成本。新容量不保证任意输入都均匀;原书教学代码把size清零再逐项put,需要避免把迁移计数和旧计数重复累计。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
需要通过哈希函数来重新计算所有键值对的存储位置,这进一步增加了扩容过程的计算 开销。为此,编程语言通常会预留足够大的哈希表容量,防止频繁扩容。 0.75 「负载因子load factor」是哈希表的一个重要概念,其定义为
参考来源
- 位置:《Hello 算法--Go版本》第06章《哈希表》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/3.html;spine 2,归一字符[15030,15140))
- 结论依据:实际前段扩容说明与extend遍历/size清零代码共同支持。
- 原始内容:需要通过哈希函数来重新计算所有键值对的存储位置,这进一步增加了扩容过程的计算 开销。为此,编程语言通常会预留足够大的哈希表容量,防止频繁扩容。 0.75 「负载因子load factor」是哈希表的一个重要概念,其定义为