知识卡片
乘移哈希截取乘积中间位
乘移法让 w 位键 k 乘以 w 位常数 a,只保留乘积的低 w 位,再取其中最高的 ℓ 位作为槽号,表大小 m=2^ℓ。它可用整数乘法、取模 2^w 与右移高效实现;若 a 固定,速度快仍不保证任意键集的平均性能。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第11章 散列表 · 查看原书依据
The desired ℓ-bit hash value consists of the ℓ most significant bits of r0.
参考来源
- 位置:《算法导论(第4版)》第 11 章 11.3.1 节(`OEBPS/chapter011.xhtml`,文本字符 [25000, 29000);图 11.4/Art_P385–P386)。
- 结论依据:原文说明乘积低半字和其最高 ℓ 位的提取,并强调固定乘移函数缺少平均性能保证。
- 原始内容:The desired ℓ -bit hash value consists of the ℓ most significant bits of r 0 .