knuth乘法哈希 [英] knuth multiplicative hash

问题描述

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

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.

类型应该是无符号的，否则溢出是未指定的（因此可能错误，不只是在非2's补码结构，但也在过于聪明的编译器）

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 ³² 2 ³² 。计算AK / w给出了格式为Q32.32的定点结果，mod 1步骤只取32个小数位。但这只是做一个模数乘法，然后说结果是分数位。当然，当乘以M时，由于如何选择M，所有分数位变为整数位，因此它简化为仅仅是一个简单的模乘。当M是2的较低次方时，如上所述，只是右移结果。

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.

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