c – knuth乘法哈希

这种实现方式不正确,但正如我在评论中提到的那样,无论如何都可能给出正确的结果.

一个正确的方法(我认为 – 随意阅读TAOCP的相关章节并验证这一点)是这样的:(重要：是的,你必须将结果右移以减少它,而不是使用按位AND.但是,这不是这个功能的责任 – 减少范围不是哈希本身的一部分)

uint32_t hash(uint32_t v)
{
    return v * UINT32_C(2654435761);
    // do not comment about the lack of right shift. I'm not ignoring it. read on.
}

注意uint32_t(而不是int) – 它们确保乘法溢出模2 ^ 32,因为如果选择32作为单词大小,它应该会这样做.这里也没有正确的k移位,因为没有理由将范围缩减归功于基本散列函数,实际上获得完整结果更有用.常量2654435761来自问题,实际建议的常量是2654435769,但这是一个很小的差异,据我所知,不会影响哈希的质量.

其他有效的实现将结果右移一定量(不是完整的字大小,这没有意义,C不喜欢它),这取决于你需要多少位散列.或者他们可以使用其他常数(受某些条件限制)或其他字数.减少散列模数不是有效的实现,而是一个常见的错误,可能它是在散列上进行范围缩减的事实上的标准方法.乘法散列的底部位是最差质量的位(它们依赖于较少的输入),如果您确实需要更多位,则只想使用它们,而减少散列模2的幂则只返回最差的位位.实际上,这相当于丢弃了大部分输入位.减少模数非二次幂是不是很糟糕,因为它确实混合了较高的位,但不是如何定义乘法散列.

所以要清楚,是的,有一个正确的转变,但这是范围减少而不是哈希,只能是哈希表的责任,因为它取决于它的内部大小.

类型应该是无符号的,否则溢出是未指定的(因此可能是错误的,不仅在非二进制补码架构上,而且在过于聪明的编译器上),并且可选的右移将是有符号的移位(错误).

在我在顶部提到的页面上,有这个公式：

这里我们得到A = 2654435761(或2654435769),w = 232且M = 232.计算AK / w得到格式为Q32.32的定点结果,mod 1步只得到32分数位.但这与进行模乘,然后说结果是分数位是一回事.当然,当乘以M时,由于如何选择M,所有分数位都变为整数位,因此它简化为仅仅是一个普通的模乘法.当M是2的较低幂时,如上所述,这恰好使结果右移.