65.9K
CodeProject 正在变化。 阅读更多。
Home

一种新的哈希函数 - ZobHash

KristianEkman
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.86/5 (65投票s)

2018年1月16日

CPOL

5分钟阅读

viewsIcon

68615

downloadIcon

1262

我们能否编写一个新的更好的哈希函数？

引言

我认为大多数现有的哈希函数都是由非常聪明的人在多年前开发的。哈希算法可能已经不可能再改进了，但我还是得尝试一下下面的想法。

背景

但首先，众所周知，哈希函数是将任意大小的数据转换为固定大小的数字的函数。它被广泛应用于例如查找表。

在我之前的一篇文章中，关于国际象棋引擎编程1，我学到了一种非常酷的国际象棋棋盘状态的哈希技术。Zobrist 哈希5 被证明能够为游戏中的每个国际象棋局面提供几乎唯一的哈希码，即使国际象棋游戏几乎有无限的状态。我认为我们可以使用 Zobrist 算法来哈希更常见的东西，例如单词。结果将在最后揭晓。(它奏效了！)

正如你可能知道的，.NET 已经包含了一个用于string的哈希函数。这个方法叫做GetHashCode，它将任何对象转换为一个整数。

我想知道是否可以使用 Zobrist 的想法创建一个更好的函数，并且碰撞更少。

哈希冲突

哈希冲突发生在两个不同的对象，在此例中是string，产生相同的哈希码时。

我正在使用一个包含 466,545 个英语单词3的列表。 .NET 中的GetHashCode函数在这个数据集上只产生了 48 个冲突，所以它在大多数情况下可能已经足够好了。如果你对 48 个冲突感到满意，那就不用继续往下看了。这里有一些具有相同 .NET 哈希码的单词示例。

  • furnaces ferrate
  • matinee cistronic
  • toeholds argon
  • unsmart pulped

你可能会争辩说，既然数据集是已知的，那么创建一个没有冲突的完美哈希算法会很容易。我们可以为每个单词分配一个唯一的数字。

然而，这并不是本次调查的目的。我们希望哈希函数能够用于任何语言的任何单词，并且碰撞的概率非常低。

Zobrist 哈希

Zobrist 哈希通过按位异或 (XOR) 随机数来工作。在国际象棋引擎中，会为每个移动生成随机数，而一个移动是通过从一个方格移除一个棋子然后将其放在另一个方格上来定义的。
有两个玩家颜色，六种棋子类型和 64 个方格。 2 * 6 * 64 = 768 个随机数。
(不考虑王车易位和吃过路兵，但你懂我的意思。)

在哈希单词时，我想到我们可以为每个字符生成随机数，然后执行与 Zobrist 哈希相同的操作。单词中的每个字符都执行一次按位异或操作。

public static int ZobHash(this string text)
{
    var hash = ZobRandom.Start;
    foreach (var c in text)
        hash ^= ZobRandom.Numbers[c];
    return hash;
}

但是这样做，我得到了 218,163 个冲突。这并不令人鼓舞，但与其放弃，不如看看为什么会有这么多冲突。

这里有一些例子

  • abied abide
  • abiegh abeigh
  • acidly acidyl
  • acron acorn

正如你所见，Zobrist 哈希为单词生成相同的哈希码，而与字母的顺序无关，也就是说，异或操作的顺序无关。
异或就是这样工作的，它非常适合存储国际象棋游戏状态，因为导致一个棋盘局面的移动顺序无关紧要，它仍然是相同的游戏状态。但对于单词的哈希来说，它却无效。

改进 Zobrist 算法

让我们尝试扩展 Zobrist 哈希，以便字母的顺序也能影响最终的哈希码。
如果我们尝试对每个字符的随机数进行循环位移（非常快的操作）呢？
循环位移就像这样将数字中的位向左（或向右，如果你愿意）推移

当数字 153，其二进制为 10011001
向左循环位移后，结果是 00110011
当你移动两次（下一个字符）时 01100110

这是循环左移的函数。

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.HashFunction4 的一些其他哈希函数进行了比较。
如果您有建议比较更多哈希函数，请在下方评论。

这些是哈希 byte-arrays 的结果。

生成 32 位哈希码的函数

函数 106 词/秒 碰撞
ZobHash 4.67 5
.net GetHashCode 7.52 1592
JenkinsOneAtATime 3.99 36
BernsteinHash 4.57 343
CRC 3.17 23
ELF64 4.32 4347
JenkinsLookup2 3.67 23
JenkinsLookup3 3.64 30
ModifiedBernsteinHash 5.69 320
MurmurHash1 3.86 27
xxHash 3.15 16
Djb2 5.55 344

生成 64 位哈希码的函数

函数 106 词/秒 碰撞
ZobHashLong 5.3 0
FNV1 3.24 0
FNV1a 3.11 0

这些是哈希string的结果（没有转换为 byte-array 的话速度快很多）

哈希函数 106 词/秒 碰撞
ZobHash 24.6 5
ZobHashLong 25.9 0
.net GetHashCode 51.8 48

结论

与其他所有测试函数相比，ZobHash 的性能都很好。对于生成 32 位哈希码的函数，它的碰撞率最低。有一些函数速度更快，但它们会产生更多的冲突。
有趣的是，.NET 的GetHashCode根据是哈希 byte 数组还是string，会产生不同数量的冲突。

对于 64 位哈希码函数，所有测试函数均未产生冲突，但 ZobHash 是最快的。

链接

  1. Test-Driven-Chess-Artificial-Intelligence
  2. https://en.wikipedia.org/wiki/Hash_function
  3. https://github.com/dwyl/english-words
  4. https://github.com/brandondahler/Data.HashFunction/
  5. https://en.wikipedia.org/wiki/Zobrist_hashing

到此为止，别忘了投票！

谢谢！

历史

  • 2018年1月16日 - 版本 1.0.0
  • 2018年1月19日 - 版本 1.0.1
    • 修复了int右移的 bug。将int更改为uint
    • 添加了简单的 C 语言实现
© . All rights reserved.