克努特乘哈希 [英] knuth multiplicative hash

问题描述

这是一个正确实施克努特乘法散列。

Is this a correct implementation of the Knuth multiplicative hash.

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

是否溢出，乘法影响算法？

Does overflow in the multiplication affects the algorithm?

如何改善这种方法的性能？

How to improve the performance of this method?

推荐答案

好吧，我看着它在TAOCP第3卷（第2版），第6.4节，516页。

Ok, I looked it up in TAOCP volume 3 (2nd edition), section 6.4, page 516.

这是实施不正确，但正如我在评论中提到的可以的给出正确的结果呢。

This implementation is not correct, though as I mentioned in the comments it may give the correct result anyway.

有一个正确的方法（我觉得 - 觉得免费阅读TAOCP中的有关章节和验证）是这样的：

A correct way (I think - feel free to read the relevant chapter of TAOCP and verify this) is something like this:

uint32_t hash(uint32_t v)
{
    return v * UINT32_C(2654435761);
}

注意 uint32_t的的（相对于 INT 的） - 他们确保乘法溢出模2 ^ 32，因为它是假设如果选择32作为字大小做

Note the uint32_t's (as opposed to int's) - they make sure the multiplication overflows modulo 2^32, as it is supposed to do if you choose 32 as the word size.

其它有效实施权一定量（不完整的字的大小虽然，这是没有道理和C ++不喜欢它）转移的结果，这取决于你有多少哈希位所需要的。或者，他们可能会使用其他不变（符合一定条件）或其他字的大小。

Other valid implementations shift the result right by some amount (not the full word size though, that doesn't make sense and C++ doesn't like it), depending on how many bits of hash you need. Or they may use an other constant (subject to certain conditions) or an other word size.

该类型应该是无符号，否则溢出是不确定的（从而可能错了，不只是对非二进制补码架构也对过分聪明的编译器）和可选右移将是签订移（错误的）。

The type should be unsigned, otherwise the overflow is unspecified (thus possibly wrong, not just on non-2's-complement architectures but also on overly clever compilers) and the optional right shift would be a signed shift (wrong).

在我提到顶部的页面上，有以下公式：

On the page I mention at the top, there is this formula:

在这里，我们有A = 2654435761，W = 2 ³² 和M = 2 ³² 。计算AK /瓦特给出与格式Q32.32定点结果，模1步骤只需要32个分数位。但是，这只是同样的事情做一个模乘，然后说，结果是小数位。当然，当由M相乘，所有的小数位成为因为M个如何被选择整数位，所以它简化到只是一个普通的旧模乘。当M是二的低功率，这只是右移位的结果，如上述

Here we have A = 2654435761, w = 2³² and M = 2³². Calculating AK/w gives a fixed-point result with the format Q32.32, the mod 1 step takes only the 32 fraction bits. But that's just the same thing as doing a modular multiplication and then saying that the result is the fraction bits. Of course when multiplied by M, all the fraction bits become integer bits because of how M was chosen, and so it simplifies to just a plain old modular multiplication. When M is a lower power of two, that just right-shifts the result, as mentioned.

这篇关于克努特乘哈希的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！