c# - 更好的64位字节数组哈希

我需要一种散列算法，该算法产生的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));
}

最佳答案

问题是您的字符串不是随机的。
在对字符串进行第二次哈希处理之前，先对其进行测试。

关于c# - 更好的64位字节数组哈希，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31464894/