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

如果有64位的hash32(x)等效物会很有趣。

Answer 1

寻找一个完美的哈希函数就像寻找圣杯。无论如何，这取决于值

如果您需要x86上的通用哈希函数，Murmur2、Meiyan、SBox和CRC32为各种键提供了良好的性能。对于64位值，您也可以尝试CityHash。

Answer 2

本页(和本页)有一些适合整数的散列函数。下面是64位整数:

public long hash64shift(long key)
{
  key = (~key) + (key << 21); // key = (key << 21) - key - 1;
  key = key ^ (key >>> 24);
  key = (key + (key << 3)) + (key << 8); // key * 265
  key = key ^ (key >>> 14);
  key = (key + (key << 2)) + (key << 4); // key * 21
  key = key ^ (key >>> 28);
  key = key + (key << 31);
  return key;
}

Answer 3

这似乎工作得很好。它使用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;
}

Answer 4

您的32位哈希是一个乘法哈希，使用Knuth在TAOCP中建议的接近黄金比例的素数。

phi = 0.5 * (sqrt(5) - 1) = 0.618...
2^32 * phi = 2654435769.497...
2^64 * phi = 11400714819323198485.951...

2654435761是32位情况下最接近的素数。对于64位，它是11400714819323198549。所以算法变成了:

unsigned int getHashKey(unsigned long x) {
    return (x * 11400714819323198549ul) >> (64 - h_bits);
}