知识卡片

普通读书笔记卡 · 1534.a.2.a.2

扩容需重新分布已有键

理解等级:初级

表容量增加后,依表长计算的桶号通常改变,因此扩容不只是多开几个空槽,还需按新规则重新放置已有项。监测负载或链长可提示扩容,但阈值与停顿成本由实现决定。

均摊效率不代表每次操作都很快。完美哈希针对预先约定键集合避免碰撞,不能由原文近似措辞推出任何未知键都能映到有限唯一桶。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 7.19 哈希算法 · 查看原书依据

      你可以跟踪链的长度,如果链太长,则可以扩展哈希表。这可能是一个成本很高的操作,但它不需要经常使用。 存在许多哈希函数的变体。哈希函数的圣杯是完美哈希,它将每个键映射到一个唯一的桶。除非预先知道所有的键,否则几乎不可能创建完美哈希函数,但数学家们已经想出了比本例

    参考来源

    - 位置:《计算机系统解密》7.19 哈希算法(来源项目book-sources,源文件:extracted/计算机系统解密/_epub-src/text/part0086.html) - 结论依据:本项全部正文与图表实际读取,区分作者示例、推导与实现边界;纠错另有明确说明。 - 原始内容:你可以跟踪链的长度,如果链太长,则可以扩展哈希表。这可能是一个成本很高的操作,但它不需要经常使用。 存在许多哈希函数的变体。哈希函数的圣杯是完美哈希,它将每个键映射到一个唯一的桶。除非预先知道所有的键,否则几乎不可能创建完美哈希函数,但数学家们已经想出了比本例