知识卡片

普通读书笔记卡 · 5654.d.1.a.3.a.1.a

取模与混合需要匹配输入

理解等级:中级

简单哈希可把输入逐项累积再压到有限范围,乘法或旋转能把次序信息混入状态;单纯加法或单纯异或则无法区分某些重排输入。选择模数还要结合输入的周期性。

质数可缓解某些公因数周期,却不保证任意输入均匀,质数自身倍数仍可聚集。原书xorHash实际又乘31加字节且最后按位与,和“纯异或、最后取模”的文字不一致,不能照它证明纯异或性质或当通用安全哈希。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      如果输入key 恰好满足这种等差数列的数据分布,那么哈希值就会出现聚堆,从而加重哈希冲突。现在,假 13 设将modulus 替换为质数 ,由于key modulus 之间不存在公约数,因此输出的哈希值的均匀性会明显 提

    参考来源

    - 位置:《Hello 算法--Go版本》第06章《哈希表》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/3.html;spine 2,归一字符[25725,25835)) - 结论依据:实际质数/合数周期反例及四段代码,保留输入结构而非质数万能结论。 - 原始内容:如果输入key 恰好满足这种等差数列的数据分布,那么哈希值就会出现聚堆,从而加重哈希冲突。现在,假 13 设将modulus 替换为质数 ,由于key modulus 之间不存在公约数,因此输出的哈希值的均匀性会明显 提