知识卡片
固定哈希依赖输入分布
固定哈希函数的“键均匀落槽”概率来自输入键的分布;若不了解分布,就无法仅凭函数外观保证平均性能。
随机哈希在运行开始时从函数族中独立于数据地选函数,使概率来自可控的选择过程,降低固定坏输入持续触发碰撞的风险。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第11章 散列表 · 查看原书依据
the randomization necessary for good average-case behavior then comes from the (known) random process used to pick the hash function
参考来源
- 位置:《算法导论(第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