<p>I'm testing the VB function below that I got from a Google search.  I plan to use it to generate hash codes for quick string comparison. However, there are occasions in which two different strings have the same hash code. For example, these strings</p>

<p>"122Gen 1 heap size (.NET CLR Memory w3wp):mccsmtpteweb025.20833333333333E-02"</p>

<p>"122Gen 2 heap size (.NET CLR Memory w3wp):mccsmtpteweb015.20833333333333E-02"</p>

<p>have the same hash code of 237117279.</p>

<p>Please tell me:
- What is wrong with the function?
- How can I fix it?</p>

<p>Thank you</p>

<p>martin</p>

<hr>

<pre><code>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
</code></pre>

[{'answer_id': 63929, 'author': 'tzot', 'author_id': 6899, 'author_profile': 'https://Stackoverflow.com/users/6899', 'pm_score': 2, 'selected': False, 'text': '<p>Hash functions do not guarantee uniqueness of hash values. If the input value range (judging your sample strings) is larger than the output value range (eg 32 bit integer), then uniqueness is physically impossible.</p>\n'}, {'answer_id': 63933, 'author': 'jjnguy', 'author_id': 2598, 'author_profile': 'https://Stackoverflow.com/users/2598', 'pm_score': 3, 'selected': False, 'text': "<p>The two Strings have the same characters. (Note the '2' and the '1' that are flip-flopped)</p>\n\n<p>That is why the hash value is the same.</p>\n\n<p>Make sure that the hash function is taking into account the order of the characters.</p>\n"}, {'answer_id': 63936, 'author': 'Magnus Akselvoll', 'author_id': 4683, 'author_profile': 'https://Stackoverflow.com/users/4683', 'pm_score': 0, 'selected': False, 'text': "<p>I don't quite see the environment you work in. Is this .Net code? If you really want good hash codes, I would recommend looking into cryptographic hashes (proven algorithms) instead of trying to write your own.</p>\n\n<p>Btw, could you edit your post and paste the code in as a Code Sample (see toolbar)? This would make it easier to read.</p>\n"}, {'answer_id': 63958, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': '<p>"Don\'t do that."  </p>\n\n<p>Writing your own hash function is a big mistake, because your language certainly already has an implementation of SHA-1, which is a perfectly good hash function.  If you only need 32 bits (instead of the 160 that SHA-1 provides), just use the last 32 bits of SHA-1.  </p>\n'}, {'answer_id': 63964, 'author': 'Clinton Pierce', 'author_id': 8173, 'author_profile': 'https://Stackoverflow.com/users/8173', 'pm_score': 4, 'selected': True, 'text': '<p>I\'m betting there are more than just "occasions" when two strings generate the same hash using your function.  In fact, it probably happens more often than you think.</p>\n\n<p>A few things to realize:</p>\n\n<p>First, there will be hash collisions. It happens. Even with really, really big spaces like MD5 (128 bits) there are still two strings that can generate the same resulting hash. You have to deal with those collisions by creating buckets.</p>\n\n<p>Second, a long integer isn\'t really a big hash space. You\'re going to get more collisions than you would if you used more bits.</p>\n\n<p>Thirdly, there are libraries available to you in Visual Basic (like .NET\'s <code>System.Security.Cryptography</code> namespace) that will do a much better job of hashing than most mere mortals.</p>\n'}, {'answer_id': 63967, 'author': 'Rob Walker', 'author_id': 3631, 'author_profile': 'https://Stackoverflow.com/users/3631', 'pm_score': 1, 'selected': False, 'text': "<p>No hash function can guarantee uniqueness.  There are ~4 billion 32-bit integers, so even the best hash function will generate duplicates when presented with ~4 billion and 1 strings (and mostly likely long before).</p>\n\n<p>Moving to 64-bit hashes or even 128-bit hashes isn't really the solution, though it reduces the probability of a collision.</p>\n\n<p>If you want a better hash function you could look at the cryptographic hashes, but it would be better to reconsider you algorithm and decide if you can deal with the collisions some other way. </p>\n"}, {'answer_id': 63984, 'author': 'Garry Shutler', 'author_id': 6369, 'author_profile': 'https://Stackoverflow.com/users/6369', 'pm_score': 1, 'selected': False, 'text': '<p>The <a href="http://msdn.microsoft.com/en-us/library/system.security.cryptography.aspx" rel="nofollow noreferrer">System.Security.Cryptography</a> namespace contains multiple classes which can do hashing for you (such as <a href="http://msdn.microsoft.com/en-us/library/system.security.cryptography.md5.aspx" rel="nofollow noreferrer">MD5</a>) which will probably hash them better than you could yourself and will take much less effort.</p>\n\n<p>You don\'t always have to reinvent the wheel.</p>\n'}, {'answer_id': 63992, 'author': 'Rich', 'author_id': 8261, 'author_profile': 'https://Stackoverflow.com/users/8261', 'pm_score': 1, 'selected': False, 'text': '<p>Simple XOR is a bad hash: you\'ll find lots of strings which collide. The hash doesn\'t depend on the order of the letters in the string, for one thing.</p>\n\n<p>Try using the FNV hash <a href="http://isthe.com/chongo/tech/comp/fnv/" rel="nofollow noreferrer">http://isthe.com/chongo/tech/comp/fnv/</a></p>\n\n<p>This is really simple to implement. It shifts the hash code after each XOR, so the same letters in a different order will produce a different hash.</p>\n'}, {'answer_id': 64002, 'author': 'ballpointpeon', 'author_id': 8269, 'author_profile': 'https://Stackoverflow.com/users/8269', 'pm_score': 0, 'selected': False, 'text': '<p>There\'s a visual basic implementation of MD5 hashing here</p>\n\n<p><a href="http://www.bullzip.com/md5/vb/md5-visual-basic.htm" rel="nofollow noreferrer">http://www.bullzip.com/md5/vb/md5-visual-basic.htm</a></p>\n'}, {'answer_id': 64018, 'author': 'Joel Coehoorn', 'author_id': 3043, 'author_profile': 'https://Stackoverflow.com/users/3043', 'pm_score': 1, 'selected': False, 'text': "<p>I fixed the syntax highlighting for him.  </p>\n\n<p>Also, for those who weren't sure about the environment or were suggesting a more-secure hash:  it's Classic (pre-.Net) VB, because .Net would require parentheses for the the call to CopyMemory.  </p>\n\n<p>IIRC, there aren't any secure hashes built in for Classic VB.  There's not much out there on the web either, so this may be his best bet.</p>\n"}, {'answer_id': 64055, 'author': 'user7936', 'author_id': 7936, 'author_profile': 'https://Stackoverflow.com/users/7936', 'pm_score': 0, 'selected': False, 'text': '<p>This particular hash functions XORs all of the characters in a string.  Unfortunately XOR is associative:</p>\n\n<pre><code>(a XOR b) XOR c = a XOR (b XOR c)\n</code></pre>\n\n<p>So any strings with the same input characters will result in the same hash code.  The two strings provided are the same, except for the location of two characters, therefore they should have the same hashcode.</p>\n\n<p>You may need to find a better algorithm, MD5 would be a good choice.</p>\n'}, {'answer_id': 64158, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 0, 'selected': False, 'text': '<p>The XOR operation is commutative; that is, when XORing all the chars in a string, the order of the chars does not matter.  All anagrams of a string will produce the same XOR hash.</p>\n\n<p>In your example, your second string can be generated from your first by swapping the "1" after "...Gen " with the first "2" following it.</p>\n\n<p>There is nothing wrong with your function.  All useful hashing functions will sometimes generate collisions, and your program must be prepared to resolve them.</p>\n\n<p>A collision occurs when an input hashes to a value already identified with an earlier input.  If a hashing algorithm could not generate collisions, the hash values would need to be as large as the input values.  Such a hashing algorithm would be of limited use compared to just storing the input values.</p>\n\n<p>-Al.</p>\n'}, {'answer_id': 64168, 'author': 'Joel Coehoorn', 'author_id': 3043, 'author_profile': 'https://Stackoverflow.com/users/3043', 'pm_score': 2, 'selected': False, 'text': "<p>If the biggest problem is that it doesn't account for the position of the bytes, you could fix it like this:</p>\n\n<pre><code>Private Function HashCode(Key As String) As Long\n  On Error GoTo ErrorGoTo\n\n  Dim lastEl As Long, i As Long\n  ' copy ansi codes into an array of long'\n  lastEl = (Len(Key) - 1) \\ 4\n  ReDim codes(lastEl) As Long\n  ' this also converts from Unicode to ANSI'\n  CopyMemory codes(0), ByVal Key, Len(Key)\n  ' XOR the ANSI codes of all characters'\n\n  For i = 0 To lastEl - 1\n    HashCode = HashCode Xor (codes(i) + i) 'Xor'\n  Next\n\nErrorGoTo:\n  Exit Function\nEnd Function\n</code></pre>\n\n<p>The only difference is that it adds the characters position to it's byte value before the XOR.</p>\n"}, {'answer_id': 64737, 'author': 'botismarius', 'author_id': 4528, 'author_profile': 'https://Stackoverflow.com/users/4528', 'pm_score': 1, 'selected': False, 'text': '<p>Hash functions are not meant to return distinct values for distinct strings. However, a good hash function should return different values for strings that look alike. Hash functions are used to search for many reasons, including searching into a large collection. If the hash function is good and if it returns values from the range [0,N-1], then a large collection of M objects will be divide in N collections, each one having about M/N elements. This way, you need to search only in an array of M/N elements instead of searching in an array of M elements.</p>\n\n<p>But, if you only have 2 strings, it is <strong>not</strong> faster to compute the hash value for those! It is <strong>better</strong> to just compare the two strings.</p>\n\n<p>An interresing hash function could be:</p>\n\n<pre><code>\n\n    unsigned int hash(const char* name) {\n      unsigned mul=1;\n      unsigned val=0;\n      while(name[0]!=0) {\n        val+=mul*((unsigned)name[0]);\n        mul*=7; //you could use an arbitrary prime number, but test the hash dispersion afterwards\n        name++;\n      }\n      return val;\n    }\n\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/63897', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/8203/']