我尝试通过 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 类型。问题依然存在
最佳答案
以下函数具有等同于 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 ) ) ;
}
关于c++ - Knuth 的乘法散列函数通过位移位,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28463794/