1

我正在测试我从谷歌搜索得到的下面的 VB 函数。我打算用它来生成哈希码以进行快速字符串比较。但是，有时两个不同的字符串具有相同的哈希码。例如，这些字符串

“122Gen 1 堆大小（.NET CLR 内存 w3wp）：mccsmtpteweb025.20833333333333E-02”

“122Gen 2 堆大小（.NET CLR 内存 w3wp）：mccsmtpteweb015.20833333333333E-02”

具有相同的哈希码 237117279。

请告诉我： - 该功能有什么问题？- 我该如何解决？

谢谢

马丁

Private Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (dest As Any, src As Any, ByVal bytes As Long)

Private Function HashCode(Key As String) As Long
  On Error GoTo ErrorGoTo

  Dim lastEl As Long, i As Long
  ' copy ansi codes into an array of long'
  lastEl = (Len(Key) - 1) \ 4
  ReDim codes(lastEl) As Long
  ' this also converts from Unicode to ANSI'
  CopyMemory codes(0), ByVal Key, Len(Key)
  ' XOR the ANSI codes of all characters'

  For i = 0 To lastEl - 1
    HashCode = HashCode Xor codes(i) 'Xor'
  Next

ErrorGoTo:
  Exit Function
End Function
4

14 回答 14

10

我敢打赌，当两个字符串使用您的函数生成相同的哈希时，不仅仅是“场合”。事实上，它发生的频率可能比你想象的要多。

需要意识到的几点：

首先，会有哈希冲突。它发生了。即使使用像 MD5（128 位）这样非常非常大的空间，仍然有两个字符串可以生成相同的结果哈希。您必须通过创建存储桶来处理这些冲突。

其次，长整数并不是真正的大哈希空间。与使用更多位相比，您将获得更多的碰撞。

第三，Visual Basic 中有一些可用的库（如 .NET 的System.Security.Cryptography命名空间），它们在散列方面比大多数普通人做得更好。

于 2008-09-15T15:30:38.560 回答
8

这两个字符串具有相同的字符。（注意“2”和“1”被翻转）

这就是哈希值相同的原因。

确保哈希函数考虑了字符的顺序。

于 2008-09-15T15:27:16.463 回答
4

散列函数不保证散列值的唯一性。如果输入值范围（判断您的样本字符串）大于输出值范围（例如 32 位整数），那么唯一性在物理上是不可能的。

于 2008-09-15T15:26:35.670 回答
2

如果最大的问题是它没有考虑字节的位置，你可以像这样修复它：

Private Function HashCode(Key As String) As Long
  On Error GoTo ErrorGoTo

  Dim lastEl As Long, i As Long
  ' copy ansi codes into an array of long'
  lastEl = (Len(Key) - 1) \ 4
  ReDim codes(lastEl) As Long
  ' this also converts from Unicode to ANSI'
  CopyMemory codes(0), ByVal Key, Len(Key)
  ' XOR the ANSI codes of all characters'

  For i = 0 To lastEl - 1
    HashCode = HashCode Xor (codes(i) + i) 'Xor'
  Next

ErrorGoTo:
  Exit Function
End Function

唯一的区别是它将字符位置添加到 XOR 之前的字节值。

于 2008-09-15T15:55:34.053 回答
1

没有哈希函数可以保证唯一性。有大约 40 亿个 32 位整数，因此即使是最好的哈希函数在出现大约 40 亿个和 1 个字符串时也会产生重复（而且很可能很久以前）。

迁移到 64 位散列甚至 128 位散列并不是真正的解决方案，尽管它降低了冲突的可能性。

如果您想要一个更好的哈希函数，您可以查看加密哈希，但最好重新考虑您的算法并决定是否可以通过其他方式处理冲突。

于 2008-09-15T15:31:14.237 回答
1

System.Security.Cryptography命名空间包含多个可以为您进行散列的类（例如MD5），这可能会比您自己更好地散列它们，并且会花费更少的精力。

您不必总是重新发明轮子。

于 2008-09-15T15:32:49.147 回答
1

简单的 XOR 是一个糟糕的哈希：你会发现很多字符串发生冲突。一方面，哈希不依赖于字符串中字母的顺序。

尝试使用 FNV 哈希http://isthe.com/chongo/tech/comp/fnv/

这真的很容易实现。它在每次异或之后移动哈希码，因此不同顺序的相同字母将产生不同的哈希。

于 2008-09-15T15:33:43.250 回答
1

我为他修复了语法突出显示。

此外，对于那些不确定环境或建议更安全的哈希的人：它是经典（.Net 之前）VB，因为.Net 需要括号来调用 CopyMemory。

IIRC，Classic VB 没有内置任何安全哈希。网络上的内容也不多，所以这可能是他最好的选择。

于 2008-09-15T15:36:49.623 回答
1

哈希函数并不意味着为不同的字符串返回不同的值。然而，一个好的散列函数应该为看起来相似的字符串返回不同的值。哈希函数用于搜索的原因有很多，包括搜索大型集合。如果散列函数是好的并且如果它返回范围 [0,N-1] 的值，那么 M 个对象的大型集合将被划分为 N 个集合，每个集合具有大约 M/N 个元素。这样，您只需在 M/N 元素的数组中进行搜索，而不是在 M 元素的数组中进行搜索。

但是，如果你只有 2 个字符串，计算它们的哈希值并不会更快！最好只比较两个字符串。

一个 interresing 哈希函数可以是：



    unsigned int hash(const char* name) {
      unsigned mul=1;
      unsigned val=0;
      while(name[0]!=0) {
        val+=mul*((unsigned)name[0]);
        mul*=7; //you could use an arbitrary prime number, but test the hash dispersion afterwards
        name++;
      }
      return val;
    }
于 2008-09-15T17:03:37.930 回答
0

我不太了解您工作的环境。这是 .Net 代码吗？如果您真的想要好的哈希码，我建议您研究加密哈希（经过验证的算法），而不是尝试编写自己的哈希码。

顺便说一句，您可以编辑您的帖子并将代码粘贴为代码示例（参见工具栏）吗？这将使阅读更容易。

于 2008-09-15T15:27:54.870 回答
0

“不要那样做。”

编写自己的哈希函数是一个很大的错误，因为您的语言肯定已经实现了 SHA-1，这是一个非常好的哈希函数。如果您只需要 32 位（而不是 SHA-1 提供的 160 位），则只需使用 SHA-1 的最后 32 位。

于 2008-09-15T15:29:50.107 回答
0

这里有一个 MD5 散列的可视化基本实现

http://www.bullzip.com/md5/vb/md5-visual-basic.htm

于 2008-09-15T15:34:46.147 回答
0

这个特殊的散列函数对字符串中的所有字符进行异或。不幸的是 XOR 是关联的：

(a XOR b) XOR c = a XOR (b XOR c)

因此，任何具有相同输入字符的字符串都会产生相同的哈希码。提供的两个字符串是相同的，除了两个字符的位置，因此它们应该具有相同的哈希码。

您可能需要找到更好的算法，MD5 将是一个不错的选择。

于 2008-09-15T15:41:27.660 回答
0

XOR 操作是可交换的；也就是说，当对字符串中的所有字符进行异或运算时，字符的顺序无关紧要。字符串的所有字谜将产生相同的 XOR 哈希。

在您的示例中，您的第二个字符串可以通过将“...Gen”之后的“1”与后面的第一个“2”交换来从第一个字符串生成。

你的功能没有问题。所有有用的散列函数有时都会产生冲突，你的程序必须准备好解决它们。

当输入散列到已经用较早输入标识的值时，就会发生冲突。如果散列算法不能产生冲突，则散列值需要与输入值一样大。与仅存储输入值相比，这种散列算法的用途有限。

-阿尔。

于 2008-09-15T15:53:58.443 回答