为什么此函数生成的哈希码不是唯一的？
我正在测试下面从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
解决方案
回答
哈希函数不能保证哈希值的唯一性。如果输入值范围(判断示例字符串)大于输出值范围(例如32位整数)，则从物理上讲不可能唯一。
回答
这两个字符串具有相同的字符。 (请注意已翻转的" 2"和" 1")
这就是为什么哈希值相同的原因。
确保哈希函数考虑了字符的顺序。
回答
我不太了解我们所使用的环境。这是.Net代码吗？如果我们确实想要好的哈希码，我建议我们研究加密散列(经过验证的算法)，而不要尝试编写自己的散列码。
顺便说一句，我们可以编辑帖子并将代码粘贴为代码示例(请参见工具栏)吗？这将使其更易于阅读。
回答
"不要那样做。"
编写自己的哈希函数是一个很大的错误，因为语言肯定已经具有SHA-1的实现，这是一个非常好的哈希函数。如果只需要32位(而不是SHA-1提供的160位)，则只需使用SHA-1的后32位。
回答
我敢打赌，当两个字符串使用函数生成相同的哈希值时，不仅仅是"场合"。实际上，它发生的频率可能比我们想象的要多。
要实现的几件事：
首先，会有哈希冲突。它发生了。即使使用MD5(128位)之类的非常大的空间，仍然有两个字符串可以生成相同的结果散列。我们必须通过创建存储桶来处理这些冲突。
其次，长整数并不是很大的哈希空间。与使用更多位相比，我们将获得更多的碰撞。
第三，Visual Basic中提供了一些库(例如.NET的System.Security.Cryptography名称空间)，它们比大多数凡人都能更好地进行哈希处理。
回答
没有哈希函数可以保证唯一性。大约有40亿个32位整数，因此，当使用约40亿个和1个字符串(并且很可能早就出现)时，即使是最好的哈希函数也会生成重复项。
迁移到64位甚至128位哈希实际上不是解决方案，尽管它降低了发生冲突的可能性。
如果我们想要更好的哈希函数，可以查看加密哈希，但是最好重新考虑算法并决定是否可以通过其他方式处理冲突。
回答
System.Security.Cryptography命名空间包含多个可以为我们进行哈希处理的类(例如MD5)，这可能会比我们自己更好地对它们进行哈希处理，并且所需的工作量要少得多。
我们不必总是重新发明轮子。
回答
简单的XOR是一个不好的哈希值：我们会发现很多冲突的字符串。一方面，哈希不依赖于字符串中字母的顺序。
尝试使用FNV哈希http://isthe.com/chongo/tech/comp/fnv/
这真的很容易实现。它将在每个XOR之后移动哈希码，因此相同字母以不同顺序将产生不同的哈希。
回答
这里有一个可视化的MD5哈希基础实现
http://www.bullzip.com/md5/vb/md5-visual-basic.htm
回答
我为他修复了语法突出显示。
另外，对于那些不确定环境或者建议使用更安全的哈希的用户：它是Classic(.Net之前的)VB，因为.Net在调用CopyMemory时需要括号。
IIRC，没有为Classic VB内置的任何安全哈希。网上也没有太多东西，所以这可能是他最好的选择。
回答
此特定的哈希函数对字符串中的所有字符进行XOR。不幸的是，XOR是关联的：
(a XOR b) XOR c = a XOR (b XOR c)
因此，任何具有相同输入字符的字符串都将产生相同的哈希码。提供的两个字符串是相同的，除了两个字符的位置不同，因此它们应具有相同的哈希码。
我们可能需要找到更好的算法，MD5将是一个不错的选择。
回答
XOR操作是可交换的；也就是说，当对字符串中的所有字符进行XOR运算时，字符的顺序无关紧要。字符串的所有字谜都将产生相同的XOR哈希。
在示例中，可以通过将" ... Gen"后的" 1"与紧随其后的第一个" 2"交换来生成第二个字符串。
功能没有错。所有有用的哈希函数有时都会产生冲突，因此程序必须准备好解决它们。
当输入散列到已经由较早的输入标识的值时，就会发生冲突。如果哈希算法无法生成冲突，则哈希值将需要与输入值一样大。与仅存储输入值相比，这种哈希算法的用途有限。
-Al
回答
如果最大的问题是它不能解决字节的位置，则可以这样解决：
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之前的字节值中。
回答
哈希函数并不旨在为不同的字符串返回不同的值。但是，一个好的哈希函数应该为看起来相似的字符串返回不同的值。出于多种原因，使用哈希函数进行搜索，包括搜索大型集合。如果散列函数很好，并且它返回的值在[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;
}
