c++ - knuth 乘法哈希

Question

这是 Knuth 乘法哈希的正确实现吗。

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

乘法溢出会影响算法吗？

如何提高该方法的性能？

Answer 1

Knuth 乘法哈希用于根据整数 k 计算 {0, 1, 2, ..., 2^p - 1} 中的哈希值。

假设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)

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

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 的质数。

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

uint32_t hash(int x);

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

来源:“Introduction to Algorithms, third edition”，Cormen 等人，13.3.2 p:263

资料来源:“计算机编程艺术，第 3 卷，排序和搜索”，D.E.高德纳，6.4 p:516