使用64位值作为键的哈希表

Question

我有一个哈希表，其键是64位值。表大小可以是不同长度的2的幂，例如2、4、8等等...我想要一个适用于这种情况的哈希表函数，即它具有最小的冲突。例如，如果我想要一个32的表大小，则哈希函数应该为64位输入产生0到31之间的值，并且具有最小的冲突。

我已经找到了32位输入的好解决方案，但还没有找到64位输入的解决方案。

对于32位键，我正在使用以下函数：

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

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

有没有64位的hash32(x)等效方法，这将会很有趣。

- MetallicPriest

---

您对它的工作方式有什么不喜欢的地方？ - sharptooth

@sharptooth: 它发生了太多的碰撞。 - MetallicPriest

希望 "6" 是一个笔误（6 是 2 的倍数，而不是 2 的幂次）。 - Keith Thompson

你尝试过elfhash()吗？它在UNIX中被广泛使用，并已被证明对其所做的事情非常好。 http://courses.cs.vt.edu/~cs3114/Summer11/Notes/T16.HashFunctions.pdf 你所要做的就是将结果模除到任何表大小（32、64等）。 - user402642

Answer 1

这个页面（和这个）有一些适用于整数的哈希函数。这里是一个适用于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;
}

- nos

Answer 2

这似乎运行得相当不错。它使用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;
}

- MetallicPriest

---

你错误地使用了FVN。FVN使用FNV_prime进行乘法，而不是offset_basis。 - osgx

Answer 3

你的32位哈希是一种乘法哈希，使用了一个接近黄金比例的质数，正如Knuth在TAOCP中建议的那样。

phi = 0.5 * (sqrt(5) - 1) = 0.618...

2^32 * phi = 2654435769.497...

2^64 * phi = 11400714819323198485.951...

在32位情况下，2654435761是最近的质数。使用64位，则为11400714819323198549。因此算法变为：

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

- nwellnhof

Answer 4

寻找完美的哈希函数就像寻找圣杯一样。不过这取决于价值。

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

- cprogrammer

---

有没有类似于hash32(x)（我在帖子中定义过）宏的64位简单等效物可用？ - MetallicPriest

int64 CityHash64(const char *s, size_t len)。你可以在此基础上编写宏，效果相同。 - cprogrammer