为什么这个函数生成的哈希码不唯一？
https://stackoverflow.com/questions/63897
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我正在测试下面从 Google 搜索中获得的 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
解决方案
我敢打赌，当两个字符串使用您的函数生成相同的散列时，不仅仅是“场合”。事实上，这种情况发生的频率可能比您想象的要高。
有几点需要注意：
首先，会出现哈希冲突。它发生了。即使使用像 MD5（128 位）这样非常非常大的空间，仍然有两个字符串可以生成相同的结果哈希。您必须通过创建存储桶来处理这些冲突。
其次，长整数实际上并不是一个大的哈希空间。与使用更多位相比，您会遇到更多的冲突。
第三，Visual Basic 中有一些库可供您使用（例如 .NET 的 System.Security.Cryptography 命名空间），这将比大多数普通人做得更好。
其他提示
两个字符串具有相同的字符。（注意翻转的“2”和“1”）
这就是哈希值相同的原因。
确保哈希函数考虑了字符的顺序。
哈希函数不保证哈希值的唯一性。如果输入值范围（判断你的样本字符串）大于输出值范围（例如32位整数），那么唯一性在物理上是不可能的。
如果最大的问题是它没有考虑字节的位置，您可以像这样修复它：
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 之前将字符位置添加到其字节值中。
没有哈希函数可以保证唯一性。大约有 40 亿个 32 位整数，因此即使是最好的哈希函数，当呈现大约 40 亿个和 1 个字符串时（很可能是很久以前），也会生成重复项。
转向 64 位哈希甚至 128 位哈希并不是真正的解决方案，尽管它降低了冲突的可能性。
如果您想要更好的哈希函数，您可以查看加密哈希值，但最好重新考虑您的算法并决定是否可以通过其他方式处理冲突。
简单的 XOR 是一个糟糕的哈希：你会发现很多碰撞的弦。一方面，哈希值不依赖于字符串中字母的顺序。
尝试使用 FNV 哈希 http://isthe.com/chongo/tech/comp/fnv/
这非常容易实现。它会在每次异或后移动哈希码，因此不同顺序的相同字母将产生不同的哈希值。
哈希函数并不意味着为不同的字符串返回不同的值。然而，一个好的哈希函数应该为看起来相似的字符串返回不同的值。哈希函数用于搜索的原因有很多，包括搜索大型集合。如果哈希函数很好并且它返回 [0,N-1] 范围内的值，那么 M 个对象的大集合将被分为 N 个集合，每个集合大约有 M/N 个元素。这样，您只需在 M/N 个元素的数组中搜索，而不是在 M 个元素的数组中搜索。
但是，如果你只有 2 个字符串，那就是 不是 更快地计算这些的哈希值！这是 更好的 只是比较两个字符串。
一个有趣的哈希函数可以是：
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;
}
我为他修复了语法突出显示。
另外，对于那些不确定环境或建议更安全的哈希的人：它是经典（.Net 之前）VB，因为.Net 需要括号来调用 CopyMemory。
IIRC，Classic VB 没有内置任何安全哈希值。网上也没有太多信息，所以这可能是他最好的选择。
我不太了解你的工作环境。这是.Net 代码吗？如果您确实想要好的哈希代码，我建议您研究加密哈希（经过验证的算法），而不是尝试编写自己的哈希代码。
顺便说一句，您可以编辑您的帖子并将代码作为代码示例粘贴（请参阅工具栏）吗？这将使它更容易阅读。
“别那样做。”
编写自己的哈希函数是一个很大的错误，因为您的语言肯定已经实现了 SHA-1，这是一个非常好的哈希函数。如果您只需要 32 位（而不是 SHA-1 提供的 160 位），则只需使用 SHA-1 的最后 32 位。
这个特定的哈希函数对字符串中的所有字符进行异或。不幸的是 XOR 是结合的：
(a XOR b) XOR c = a XOR (b XOR c)
因此，具有相同输入字符的任何字符串都将产生相同的哈希码。提供的两个字符串是相同的，除了两个字符的位置不同，因此它们应该具有相同的哈希码。
您可能需要找到更好的算法，MD5将是一个不错的选择。
XOR 运算是可交换的；也就是说，当对字符串中的所有字符进行异或时，字符的顺序并不重要。字符串的所有字谜词都会产生相同的 XOR 哈希值。
在您的示例中，可以通过将“...Gen”后面的“1”与后面的第一个“2”交换来从第一个字符串生成第二个字符串。
你的功能没有任何问题。所有有用的散列函数有时都会产生冲突，您的程序必须准备好解决它们。
当输入散列到已用较早输入标识的值时，就会发生冲突。如果哈希算法无法产生冲突，则哈希值需要与输入值一样大。与仅存储输入值相比，这种散列算法的用途有限。
-阿尔。
这里有 MD5 哈希的可视化基本实现
