知识卡片

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

乘移哈希截取乘积中间位

理解等级:高级

乘移法让 w 位键 k 乘以 w 位常数 a,只保留乘积的低 w 位,再取其中最高的 ℓ 位作为槽号,表大小 m=2^ℓ。它可用整数乘法、取模 2^w 与右移高效实现;若 a 固定,速度快仍不保证任意键集的平均性能。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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 .