获取以Int64存储的44位数字的GetHashCode()的最佳方法

本文关键字：最佳 方法 GetHashCode 44位 Int64 存储 获取 数字 | 更新日期: 2023-09-27 18:24:36

我在Dictionary<MyKey, MyValue>中存储了大约5000000个对象。

MyKey是一个结构，它将我的密钥的每个组成部分（5个不同的数字）打包在Int64（ulong）的最右边44位中。

由于ulong总是从20个零位开始，我的直觉是，返回原生Int64.GetHashCode()实现可能会比哈希码实现只考虑实际使用的44位更频繁地发生冲突（尽管从数学上讲，我不知道从哪里开始证明这一理论）。

这增加了对.Equals()的调用次数，并使字典查找速度变慢。

Int64.GetHashCode()的.NET实现如下所示：

public override int GetHashCode()
{
    return (int)this ^ (int)(this >> 32);
}

如何最好地实现GetHashCode()？

获取以Int64存储的44位数字的GetHashCode()的最佳方法

我无法开始提出散列44位数字的"最佳"方法。但是，我可以建议一种方法将其与64位哈希算法进行比较。

一种方法是简单地检查一组数字的碰撞次数（正如McKenzie等人在选择哈希算法中所建议的）除非你要测试集合的所有可能值，否则你需要判断你得到的碰撞次数是否可以接受。这可以用类似于的代码来完成

var rand = new Random(42);
var dict64 = new Dictionary<int, int>();
var dict44 = new Dictionary<int, int>();
for (int i = 0; i < 100000; ++i)
{
    // get value between 0 and 0xfffffffffff (max 44-bit value)
    var value44 = (ulong)(rand.NextDouble() * 0x0FFFFFFFFFFF);
    var value64 = (ulong)(rand.NextDouble() * ulong.MaxValue);
    var hash64 = value64.GetHashCode();
    var hash44 = (int)value44 ^ (int)(value44>> 32);
    if (!dict64.ContainsValue(hash64))
    {
        dict64.Add(hash64,hash64);
    }
    if (!dict44.ContainsValue(hash44))
    {
        dict44.Add(hash44, hash44);
    }
}
Trace.WriteLine(string.Format("64-bit hash: {0}, 64-bit hash with 44-bit numbers {1}", dict64.Count, dict44.Count));

换句话说，一致地生成100000个随机64位值和100000个随机44位值，对每个值执行散列并跟踪唯一值。

在我的测试中，这为44位数字生成了99998个唯一值，为64位数字生成99997个唯一值。因此，对于44位数字和64位数字，这是一个更少的冲突。我希望44位数字的冲突更少，因为可能的输入更少。

我不会告诉你64位散列方法对于44位是"最好的"；你必须决定这些结果是否对你的情况有利。

理想情况下，您应该使用应用程序可能生成的实际值进行测试。考虑到这些都是44位的值，很难将其与ulong.GetHashCode()产生的碰撞进行比较（即，您会得到相同的结果）。如果基于常量种子的随机值不够好，请使用更好的方法修改代码。

虽然事情可能"感觉"不对劲，但科学表明，如果没有可重复的测试来证明改变是必要的，那么改变某些事情是没有意义的。

这是我试图回答这个问题的尝试，尽管答案与我预期的相反，但我还是发布了这个问题。（尽管我可能在某个地方犯了错误——我几乎希望如此，并且对我的测试技术持批评态度。）

  // Number of Dictionary hash buckets found here:
  // http://stackoverflow.com/questions/24366444/how-many-hash-buckets-does-a-net-dictionary-use
  const int CNumberHashBuckets = 4999559;
  static void Main(string[] args)
  {
     Random randomNumberGenerator = new Random();
     int[] dictionaryBuckets1 = new int[CNumberHashBuckets];
     int[] dictionaryBuckets2 = new int[CNumberHashBuckets];
     for (int i = 0; i < 5000000; i++)
     {
        ulong randomKey = (ulong)(randomNumberGenerator.NextDouble() * 0x0FFFFFFFFFFF);
        int simpleHash = randomKey.GetHashCode();
        BumpHashBucket(dictionaryBuckets1, simpleHash);
        int superHash = ((int)(randomKey >> 12)).GetHashCode() ^ ((int)randomKey).GetHashCode();
        BumpHashBucket(dictionaryBuckets2, superHash);
     }
     int collisions1 = ComputeCollisions(dictionaryBuckets1);
     int collisions2 = ComputeCollisions(dictionaryBuckets2);
  }
  private static void BumpHashBucket(int[] dictionaryBuckets, int hashedKey)
  {
     int bucketIndex = (int)((uint)hashedKey % CNumberHashBuckets);
     dictionaryBuckets[bucketIndex]++;
  }
  private static int ComputeCollisions(int[] dictionaryBuckets)
  {
     int i = 0;
     foreach (int dictionaryBucket in dictionaryBuckets)
        i += Math.Max(dictionaryBucket - 1, 0);
     return i;
  }

我试图模拟Dictionary所做的处理将如何工作。OP表示，他在一本字典中有"大约5000000个"对象，根据引用的来源，字典中将有4999559个或5999471个"桶"。

然后，我生成5000000个随机的44位密钥来模拟OP的Dictionary条目，对于每个密钥，我用两种不同的方式进行散列：简单的ulong。GetHashCode（）和我在评论中建议的另一种方法。然后，我使用模将每个哈希代码转换为一个bucket索引——我假设Dictionary就是这样做的。这用于增加伪桶，作为计算碰撞次数的一种方式。

不幸的是（对我来说）结果并不像我所希望的那样。对于4999559个桶，模拟通常指示大约180万次碰撞，而我的"超级哈希"技术实际上有更多的碰撞（大约0.01%）。对于5999471个桶，通常会有大约160万次碰撞，而我所谓的超级哈希可能会减少0.1%的碰撞。

因此，我的"直觉"是错误的，似乎没有理由试图找到一种更好的哈希代码技术。

相关文章：