更好的64位字节数组哈希

本文关键字：数组 哈希 字节数 字节 64位 更好 | 更新日期: 2023-09-27 18:03:02

我需要一个哈希算法，它产生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()碰撞~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));
}

更好的64位字节数组哈希

问题是你的字符串不是随机的。

3%与仅仅调用String.GetHashCode()

相同。

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

因为你的测试字符串是随机的，哈希码也可能是很好的分布。

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

您应该计算真正的哈希碰撞，因为大多数碰撞是由字符串碰撞引起的。

声明以下内容:

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));

我用更新的代码运行，得到没有真正的冲突(只有60000个重复的字符串)。

相关文章：