9

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

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

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

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

4

4 回答 4

22

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

资料来源：“算法简介，第三版”，Cormen 等人，13.3.2 p:263

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

于 2017-01-08T21:17:10.970 回答
15

好的，我在 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（与int's 相对）——它们确保乘法溢出模 2^32，如果您选择 32 作为字长，则应该这样做。这里也没有右移k，因为没有理由将范围缩小的责任交给基本的散列函数，而获得完整结果实际上更有用。常数 2654435761 来自问题，实际建议的常数是 2654435769，但据我所知，这是一个很小的差异，不会影响哈希的质量。

其他有效的实现将结果向右移动一定量（虽然不是完整的字长，这没有意义，C++ 也不喜欢它），具体取决于您需要多少位散列。或者他们可以使用其他常量（受某些条件限制）或其他字长。减少哈希模数不是一个有效的实现，而是一个常见的错误，可能是对哈希进行范围减少的事实上的标准方法。乘法散列的底部位是质量最差的位（它们依赖于较少的输入），如果您确实需要更多位，您只想使用它们，而将散列模数为 2 的幂只会返回最差的位位. 事实上，这也相当于丢弃了大部分输入位。以非二次幂为模减少并不是那么糟糕，因为它确实混合了更高的位，但这不是乘法散列的定义方式。

所以要清楚，是的，有一个右移，但那是范围缩小而不是散列，只能是散列表的责任，因为它取决于它的内部大小。

类型应该是无符号的，否则溢出是未指定的（因此可能是错误的，不仅在非 2 的补码架构上而且在过于聪明的编译器上）并且可选的右移将是有符号的移位（错误）。

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

克努特公式

这里我们有 A = 2654435761（或 2654435769），w = 2 32和 M = 2 32。计算 AK/w 给出了格式为 Q32.32 的定点结果，模 1 步骤仅采用 32 个小数位。但这与做模乘然后说结果是分数位是一样的。当然，当乘以 M 时，由于 M 的选择方式，所有小数位都变为整数位，因此它简化为一个普通的旧模乘法。如前所述，当 M 是 2 的较低幂时，这恰好使结果右移。

于 2012-08-08T20:19:50.603 回答
2

可能会迟到，但这是 Knuth 方法的 Java 实现：

对于大小为 N 的哈希表： 

public long hash(int key) {
    long l = 2654435769L;
    return (key * l >> 32) % N ;
}
于 2019-01-12T13:00:02.220 回答
0

如果输入参数是一个指针，那么我使用它

#include <inttypes.h>

uint32_t knuth_mul_hash(void* k) {
  ptrdiff_t v = (ptrdiff_t)k * UINT32_C(2654435761);
  v >>= ((sizeof(ptrdiff_t) - sizeof(uint32_t)) * 8); // Right-shift v by the size difference between a pointer and a 32-bit integer (0 for x86, 32 for x64)
  return (uint32_t)(v & UINT32_MAX);
}

我通常在 hashmap 实现、字典、集合等中使用它作为默认的后备散列函数......

于 2016-05-30T12:06:38.093 回答