Knuth 的乘法散列函数通过位移位

Question

我尝试通过 A = 2654435769 的位移位来实现 Knuth 的乘法算法和 2^p 个元素的散列大小但是非移位和移位算法给出不同的结果

我是如何尝试实现这两个算法的：



    模板
    整数 mult_hash_simple（整数键）
    {
        双 A = 0.61803398863412439823150634765625；
        double exp = A*key;
        return max_key*(exp - (int) exp);
    }

    模板
    整数 mult_hash_advanced（整数键）
    {
    // 常量 w = 32;
        const unsigned long long A = 2654435769;
        unsigned long long r0 = key*A;

        return r0 & ( (1

更新：更新了一些变量类型。问题依然存在

Answer 1

以下函数具有等同于mult_hash_simple函数的高级哈希逻辑。

template<int max_key_power, int p>
int mult_hash_advanced(int key)
{
//  const int w = 32;
    const long long w_bit = 4294967295; // Integer representation of binary value that has last 32 ( which is w value )  bits as 1
    const int A = 2654435769; 
    long long r0 = key*A;


    return (( r0 & w_bit ) >> ( 32 - p ) ) ;
}

Knuth 的乘法散列函数通过位移位

Knuth's multiplication hash function via bit shifting

c++

algorithm

hash