更好的 64 位字节数组哈希

Question

我需要一种哈希算法，它可以生成 64 位哈希码 (long)，其冲突比 String.GetHashCode() 少，而且速度快（不对加密函数的昂贵调用）。这是 FNV 的一个实现，它在测试 200 万个随机字符串后仍然显示 3% 的冲突。我需要这个数字更低。

void Main()
{
    const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!#@$%^&*()_+}{\":?><,./;'[]0123456789\";
    const int n = 2000000;
    var random = new Random();
    var hashes = new HashSet<long>();
    int collisions = 0;
    for(int i = 0; i < n; i++)
    {
        var len = random.Next(chars.Length);
        var str = new char[len];
        for (int j = 0; j < len; j++)
        {
            str[j] = chars[random.Next(chars.Length)];
        }
        var s = new String(str);
        if(!hashes.Add(Get64BitHash( s ))) collisions++;
    }
    Console.WriteLine("Collision Percentage after " + n + " random strings: " + ((double)collisions * 100 / n));
}


public long Get64BitHash(string str)
{
  unchecked
  {
     byte[] data = new byte[str.Length * sizeof(char)];
     System.Buffer.BlockCopy(str.ToCharArray(), 0, data, 0, data.Length);

     const ulong p = 1099511628211UL;
     var hash = 14695981039346656037UL;
     foreach(var d in data)
     {
        hash ^= d;
        hash *= p;
     }
     return (long) hash;
  }
}

以上代码的示例输出：

2000000个随机字符串后的碰撞百分比：3.01485 %

3% 与调用 String.GetHashCode() 的碰撞百分比相同。我需要更好的东西。

PS: 有可能我正在做一些非常长的事情。

编辑： 已解决。 Get64BitHash 上面的方法是正确的。问题是我的琴弦不是随机的。在确保字符串是唯一的（参见下面修改后的代码）后，我在将近 5000 万个唯一字符串上得到零冲突，而使用 String.GetHashCode().[=18= 时冲突约为 1% ]

void Main()
{
    const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!#@$%^&*()_+}{\":?><,./;'[]0123456789\";
    const int n = 200000000;
    var random = new Random();
    var hashes = new HashSet<long>();
    var strings = new HashSet<string>();
    int collisions = 0;
    while(strings.Count < n)
    {
        var len = random.Next(chars.Length);
        var str = new char[len];
        for (int j = 0; j < len; j++)
        {
            str[j] = chars[random.Next(chars.Length)];
        }
        var s = new String(str);
        if(!strings.Add(s)) continue;
        if(!hashes.Add(s.GetHashCode())) collisions++;
    }
    Console.WriteLine("Collision Percentage after " + n + " random strings: " + ((double)collisions * 100 / strings.Count));
}

Answer 1

3% is the same collision percentage as just calling String.GetHashCode()

也许这就是理论上的最优值。内置的哈希码还不错。尝试使用 SHA2 来确认这是你能做的最好的。

由于您的测试字符串是随机的，因此哈希码也可能分布良好。

通过不创建两个似乎没有任何作用的临时缓冲区来优化功能。直接访问字符 (str[0])。这样您就可以保存副本并每次迭代处理两个字节。

Answer 2

问题是您的字符串不是随机的。在第二次散列之前测试您的字符串。

Answer 3

你应该计算真正的哈希冲突，因为它们中的大多数是字符串冲突造成的。

声明如下：

var hashesString = new HashSet<string>();
int collisionsString = 0 ;
int testedCollisions = 0 ;

然后修改你的代码如下：

   if(hashesString.Add(s))
   { // Count collisions only for new strings
     testedCollisions++ ;
     if (!hashes.Add(Get64BitHash( s ))) collisions++;
   }
 }
 Console.WriteLine("Collision Percentage after " + testedCollisions + " random strings: " + ((double)collisions * 100 / testedCollisions));

我用更新后的代码做了一个运行，没有真正的碰撞（只有 60 000 个重复的字符串）。

更好的 64 位字节数组哈希

Better 64-bit byte array hash

c#

hashcode