-1

我的密钥是 64 位地址，输出是 1 字节数 (0-255)。允许碰撞，但发生碰撞的概率应该很低。此外，假设要插入的元素数量很少，可以说不超过 255，以尽量减少鸽子洞效应。

地址是程序中函数的地址。

4

4 回答 4

3 
uint64_t addr = ...
uint8_t hash = addr & 0xFF;

我认为这可以满足您的所有要求。

于 2013-01-31T16:38:58.190 回答
3

我会将 2 个 LSB（最低有效字节）异或在一起，如果分布不好，则添加第三个，依此类推

这背后的基本原理如下：函数地址分布不均匀。问题通常在于较低 (lsb) 位。函数通常需要从可被 4/8/16 整除的地址开始，因此 2-4 lsb 可能毫无意义。通过与下一个字节进行异或运算，您应该可以摆脱大多数这些问题，而且速度仍然非常快。

于 2013-01-31T16:42:17.853 回答
1

Function addresses are, I think, quite likely to be aligned (see this question, for instance). That seems to indicate that you want to skip least significant bits, depending on the alignment.

So, perhaps take the 8 bits starting from bit 3, i.e. skipping the least significant 3 bits (bits 0 through 2):

const uint8_t hash = (address >> 3);

This should be obvious from inspection of your set of addresses. In hex, watch the rightmost digit.

于 2013-01-31T16:47:48.103 回答
1

How about:

uint64_t data = 0x12131212121211B12;

uint32_t d1 = (data >> 32) ^ (uint32_t)(data);
uint16_t d2 = (d1 >> 16) ^ (uint16_t)(d1);
uint8_t  d3 = (d2 >> 8) ^ (uint8_t)(d2);

return d3;

It combined all bits of your 8 bytes with 3 shifts and three xor instructions.

于 2013-01-31T16:48:24.117 回答