64位到10位散列函数

我想要一个散列函数，它需要一个很长的数字（64位）并产生10位的结果。什么是这种目的最好的散列函数。输入基本上是变量的地址（在Linux上地址是64位或8字节），所以我的散列函数应该为此目的进行优化。64位到10位散列函数

2012-07-06 MetallicPriest

有什么关于你的宇宙中64位值的分布的信息，你可以给我们吗？ – 2012-07-06 09:27:20

对于所有情况，没有“最佳”散列函数。你必须研究你的输入数字的分布和特征。 – 2012-07-06 09:27:29

输入是Linux上变量的地址。 – MetallicPriest 2012-07-06 09:28:26

我想说somethig这样的：

uint32_t hash(uint64_t x) 
{ 
    x >>= 3; 
    return (x^(x>>10)^(x>>20)) & 0x3FF; 
}

的恐怕显著3位是不是非常有用，因为大多数变量是4字节或8字节对齐，所以我们将其删除。然后我们将接下来的30位数据混合在一起（XOR），每个数据位10位。

当然，你也可以采取(x>>30)^(x>>40)^(x>>50)，但我不确定他们是否会在实践中有所作为。

来源

2012-07-06 09:34:30 rodrigo

由于您使用xor-shift进行混合，因此我建议使用Marsaglia描述的64×64矩阵中已知的275个三联体中的一个（例如（7,11,10）或（21， 17,48）。由于这是以伪随机方式混合比特而没有已知的奇异点，因此在执行＆0x3ff之前将所有单词混淆在一起是有效的。这样，每个输入位应该有机会影响所有输出位。也许并不像密码散列那样完美50:50分布，但尽可能好。除此之外，还是一个好主意，+1 – Damon 2012-07-06 09:58:29

最适合大部分发行版是mod by prime，1021是最大的10位素数。没有必要去掉低位。

static inline int hashaddress(void *v) 
{ 
     return (uintptr_t)v % 1021; 
}

如果你想表现可能是一个关注，手头上有几个候补和种族他们在实际的程序。 Microbenchmarks是浪费;几个周期的差异几乎肯定会被缓存效应所淹没，并且大小很重要。

来源

2012-07-06 11:45:43 jthill

我写了一个玩具程序到看到栈，数据区和堆一些真实地址。基本上我宣布4个全局变量，4个当地人，并且做了2个mallocs。打印地址时丢弃了最后两位。这里是从运行的一个一个输出：

20125e8 
20125e6 
20125e7 
20125e4 
3fef2131 
3fef2130 
3fef212f 
3fef212c 
25e4802 
25e4806

这告诉我：

的LSB在此输出（地址的第3位），常常是“开” 和'off'。所以在计算散列时我不会放弃它。丢掉2个LSB似乎就够了。
我们也看到在较低的8-10位中有更多的熵。我们必须使用，当计算散列。
我们知道在一台64位的机器上，virtual addresses are never more than 48 bits wide。

我会怎么做，未来：

/* Drop two LSBs. */ 
a >>= 2; 

/* Get rid of the MSBs. Keep 46 bits. */ 
a &= 0x3fffffffffff; 

/* Get the 14 MSBs and fold them in to get a 32 bit integer. 
The MSBs are mostly 0s anyway, so we don't lose much entropy. */ 
msbs = (a >> 32) << 18; 
a ^= msbs;

现在，我们经过了通过decent 'half avalanche' hash function，而不是滚动我们自己。 “一半雪崩”是指在输入的每一位都有机会在同一位置以影响比特和更高：

uint32_t half_avalanche(uint32_t a) 
{ 
    a = (a+0x479ab41d) + (a<<8); 
    a = (a^0xe4aa10ce)^(a>>5); 
    a = (a+0x9942f0a6) - (a<<14); 
    a = (a^0x5aedd67d)^(a>>3); 
    a = (a+0x17bea992) + (a<<7); 
    return a; 
}

对于一个10位的哈希，使用返回的uint32_t的10个MSB。如果您选择N位散列的N MSB，散列函数将继续正常工作，从而使每个附加位的存储桶数有效地加倍。

我有点无聊，所以我为此写了一个玩具基准。没什么特别的，它会在堆上分配一堆内存并尝试上面描述的散列。来源可以从here。一个示例的结果：

1024桶，产生256个值，29个collissions
1024桶，产生512个值，103个collissions
1024桶，产生1024个值，370个collissions

下一页：我尝试了其他两个哈希在这里回答。他们都有类似的表现。看起来像：只需选择最快的一个;）

来源

2012-07-06 14:54:53 ArjunShankar

64位到10位散列函数

回答

相关问题