知识卡片

普通读书笔记卡 · 3620.c.1.c

固定哈希依赖输入分布

理解等级:高级

固定哈希函数的“键均匀落槽”概率来自输入键的分布;若不了解分布,就无法仅凭函数外观保证平均性能。

随机哈希在运行开始时从函数族中独立于数据地选函数,使概率来自可控的选择过程,降低固定坏输入持续触发碰撞的风险。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 11 章 11.3 节(`OEBPS/chapter011.xhtml`,文本字符 [20500, 24500))。 - 结论依据:原文对比 static hashing 的未知输入分布与 random hashing 的函数抽样来源。 - 原始内容:the randomization necessary for good average-case behavior then comes from the (known) random process used to pick the hash function