知识卡片
随机奇乘数换取速度
在乘移法中随机选奇数乘数 a,可构成 2/m 通用函数族:不同键的碰撞概率至多 2/m,而非通常通用性的 1/m。它以略宽的概率上界换取更快的机器级计算;“2/m 通用”不等于没有保证。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第11章 散列表 · 查看原书依据
The family of hash functions H given by equation (11.5) is 2/m-universal.
参考来源
- 位置:《算法导论(第4版)》第 11 章定理 11.5(`OEBPS/chapter011.xhtml`,文本字符 [37000, 39500);Art_P392)。
- 结论依据:原文陈述奇数乘数函数族的 2/m 碰撞上界,并解释速度优势。
- 原始内容:The family of hash functions H given by equation (11.5) is 2/ m -universal.