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

Question

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

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

    template    int mult_hash_simple(int key)    {        double A = 0.61803398863412439823150634765625;        double exp = A*key;        return max_key*(exp - (int) exp);    }    template    int mult_hash_advanced(int key)    {    //  const int w = 32;        const unsigned long long A = 2654435769;        unsigned long long r0 = key*A;        return r0 & (  (1 

UPD:更新了一些 var 类型。问题依然存在

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 ) ) ;
}