uint64_t键的最佳哈希函数是0到最大值的范围是多少？

Question

假设我们有一组元素并希望将它们存储在哈希映射中(例如std::unordered_set),并且每个元素都有一个类型的键,uint64_t其值可以从0到其最大可能值变化,是否是使用琐碎的最佳选择哈希函数,其中键的哈希值本身就是键？它是否依赖于正在使用的容器(即Google的稀疏哈希与来自STL的无序地图)？出现关键值的概率未知.

Answer 1

如果您需要散列的所有内容都是具有未知概率的任何可能值的uint64_t,并且您的输出必须是uint64_t,那么您不会通过更改值获得任何优势.只需使用密钥本身.

如果您对值的分布有所了解或者您的值被限制在较小的范围内(这与了解分布非常相似),那么将变换应用于键可能是有益的,但这取决于容器的实现.只有当表将哈希值转换为存储区索引时,才会减少冲突,但这取决于表的算法和表的当前/平均状态(每个存储桶的使用频率).

Answer 2

我建议一个好的64位混音器,其中有很多可供选择.来自MurmerHash3的终结器相当快,只需五行代码即可完成合理的工作:

key ^= key >> 33;
key *= 0xff51afd7ed558ccd;
key ^= key >> 33;
key *= 0xc4ceb9fe1a85ec53;
key ^= key >> 33;

Numerical Recipes,第3版,推荐:

public static UInt64 Next( UInt64 u )
  {
  UInt64 v = u * 3935559000370003845 + 2691343689449507681;

  v ^= v >> 21;
  v ^= v << 37;
  v ^= v >>  4;

  v *= 4768777513237032717;

  v ^= v << 20;
  v ^= v >> 41;
  v ^= v <<  5;

  return v;
  }