哈希算法是一种将任意大小的数据转换为固定大小数字的函数，广泛应用于查找表等场景。本文将介绍一种基于Zobrist哈希算法的改进方法，以期减少哈希碰撞并提高哈希函数的效率。
在之前关于国际象棋引擎编程的文章中，了解到了一种非常酷的哈希技术，用于为棋盘状态生成几乎唯一的哈希码。尽管国际象棋游戏有几乎无限的状态，Zobrist哈希算法却能够为每个棋局状态提供几乎唯一的哈希码。认为可以将Zobrist算法应用于更常见的事物，比如单词。
哈希碰撞发生在两个不同的对象（在本文中是字符串）产生相同的哈希码时。.NET已经包含了一个字符串的哈希函数，名为GetHashCode，它将任何对象转换为整数。
使用466,545个英文单词的数据集，.NET的GetHashCode函数只产生了48次碰撞，因此在大多数场景下它已经足够好了。如果能接受48次碰撞，那么可能不需要继续阅读本文。以下是一些具有相同.NET哈希码的单词示例：
Zobrist哈希通过逐位XOR随机数来工作。在国际象棋引擎中，为移动生成随机数，移动由从一格移除棋子然后将其放在另一格定义。
在哈希单词时，考虑为每个字符生成随机数，然后像在Zobrist哈希中一样进行操作。对单词中的每个字符执行一次逐位XOR操作。以下是C#语言的实现：
public static int ZobHash(this string text) {
var hash = ZobRandom.Start;
foreach (var c in text) {
hash ^= ZobRandom.Numbers[c];
}
return hash;
}
但是，这样做得到了218,163次碰撞，这并不令人鼓舞。让看看为什么会有这么多碰撞。以下是一些示例：
正如看到的，Zobrist哈希为单词提供了相同的哈希码，而不考虑字母的顺序，即XOR操作的顺序。这就是XOR的工作方式，它非常适合存储棋局状态，因为导致棋盘位置的移动顺序并不重要，它仍然是相同的游戏状态。但对于单词的哈希，这并不适用。
让尝试扩展Zobrist哈希，使得字母的顺序也影响最终的哈希码。如果尝试对每个字符的随机数进行循环位移（非常快速的操作）会怎样？
循环位移将数字中的位向左（或向右，如果愿意的话）推动，如下所示：
以下是循环左移位的函数：
private static uint RotateLeft(uint value, int count) {
var r = count % 32;
return (value << r) | (value >> (32 - r));
}
最终的哈希函数如下：
public static uint ZobHash(this string text) {
var hash = ZobRandom.Start;
var i = 1;
foreach (var c in text) {
hash ^= RotateLeft(ZobRandom.Numbers[c], i++);
}
return hash;
}
如上所述，Zobrist哈希使用一系列随机数。出于某种原因，函数使用某些随机数效果更好。可能不幸选择了一个不好的随机种子，最终导致更多的哈希碰撞。因此，实现Zobrist哈希函数也是关于选择一个好的随机种子。
以下是对466,545个独特的英文单词进行计数的性能和碰撞次数的结果。还与Brandon Dahler nuget System.Data.HashFunction中的一些其他哈希函数进行了比较。
以下是对字节数组进行哈希的结果：
| 函数 | 10^6 Words/s | 碰撞 |
|---|---|---|
| ZobHash | 4.67 | 5 |
| GetHashCode .net | 7.52 | 1592 |
以下是对字符串进行哈希的结果（无需转换为字节数组，速度更快）：
| 哈希函数 | 10^6 Words/s | 碰撞 |
|---|---|---|
| ZobHash | 24.6 | 5 |
| ZobHashLong | 25.9 | 0 |
| GetHashCode .net | 51.8 | 48 |