以64位值为键的哈希表

Question

我有一个哈希表,其键是64位值.表大小可以是不同的功率长度2,例如2,4,8等...我想要一个适用于这种情况的哈希表函数,也就是说,它具有最小的冲突.例如,如果我希望表大小为32,则散列函数应生成0到31之间的值,并且64位输入的冲突最小.

我已经找到了32位输入的良好解决方案,但是还没有64位输入.

对于32位密钥,我正在使用此功能

#define hash32(x)   ( (x) * 2654435761 )

unsigned int getHashKey( unsigned long x )
{
  return hash32(x) >> ( 32 - h_bits );
}

将hash32(x)等效于64位会很有趣.

Answer 1

这似乎工作得很好。它使用 64 位的 FVN 哈希常量，http://isthe.com/chongo/tech/comp/fnv/。

#define hash64(x)       ( (unsigned long)(x) * 14695981039346656037 )
#define H_BITS          4   // Hashtable size = 2 ^ 4 = 16
#define H_SHIFT_64      ( 64 - H_BITS )

unsigned int getHashKey( unsigned long x )
{
  return hash64(x) >> H_SHIFT_64;
}