knuth乘法哈希

Question

这是Knuth乘法散列的正确实现吗？

int hash(int v)
{
    v *= 2654435761;
    return v >> 32;
}

乘法中的溢出会影响算法吗？

如何提高这种方法的性能？

Answer 1

Knuth乘法散列用于{0, 1, 2, ..., 2^p - 1}从整数k 计算散列值.

假设p在0到32之间,算法如下:

• 将alpha计算为最接近2 ^ 32(-1 + sqrt(5))/ 2的整数.我们得到alpha = 2 654 435 769.

• 计算k*alpha并减少结果模2 ^ 32:

  k*alpha = n0*2 ^ 32 + n1,0 <= n1 <2 ^ 32

• 保持n1的最高p位:

  n1 = m1*2 ^(32-p)+ m2,0 <= m2 <2 ^(32-p)

因此,在C++中正确实现Knuth乘法算法是:

std::uint32_t knuth(int x, int p) {
    assert(p >= 0 && p <= 32);

    const std::uint32_t knuth = 2654435769;
    const std::uint32_t y = x;
    return (y * knuth) >> (32 - p);
}

忘记将结果移动(32-p)是一个重大错误.因为你会失去哈希的所有好的属性.它会将偶数序列转换为偶数序列,这将非常糟糕,因为所有奇数时隙都将保持未被占用.这就像拿一杯好酒并与可乐混合.顺便说一句,网络上充斥着人们错误地引用Knuth并使用乘法2 654 435 761而不采用更高的位.我刚开了Knuth,他从未说过这样的话.看起来有些人认为他"聪明"决定采用接近2 654 435 769的素数.

请记住,大多数哈希表实现不允许在其接口中使用这种签名,因为它们只允许

uint32_t hash(int x);

并减少hash(x)modulo 2 ^ p来计算x的哈希值.那些哈希表不能接受Knuth乘法哈希.这可能是为什么这么多人忘记采用更高的p位完全破坏算法的原因.所以你不能使用std::unordered_map或者使用Knuth乘法散列std::unordered_set.但我认为这些哈希表使用素数作为大小,因此Knuth乘法哈希在这种情况下没有用.使用hash(x) = x将非常适合这些表格.

资料来源:"算法导论,第三版",Cormen等,13.3.2 p:263

资料来源:"计算机编程艺术,第3卷,排序和搜索",DE Knuth,6.4 p:516

Answer 2

好的,我在TAOCP第3卷(第2版),第6.4节,第516页中进行了查阅.

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

一个正确的方法(我认为 - 随意阅读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's(与s相对int) - 它们确保乘法溢出模2 ^ 32,因为如果选择32作为单词大小,它应该这样做.这里也没有正确的转变k,因为没有理由将范围缩减归功于基本散列函数,实际上获得完整结果更有用.恒2654435761是从问题的实际建议不变的是2654435769,但是这是一个小的差异,由于据我所知不会影响哈希的质量.

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

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

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

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

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