爲什麼這個函數生成的哈希碼不是唯一的？

Question

我正在測試我從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 

Answer 1

我敢打賭，當兩個字符串使用你的函數產生相同的散列時，不僅僅是「場合」。事實上，它可能比你想象的更頻繁地發生。

有幾件事情來實現：

首先，將有散列碰撞。它發生了。即使真的非常大的空間像MD5（128位），仍然有兩個字符串可以生成相同的結果散列。你必須通過創建桶來處理這些衝突。

其次，長整數並不是真正的大哈希空間。如果你使用更多的位，你將會碰到更多的碰撞。

第三，在Visual Basic中可以使用庫（比如。NET的System.Security.Cryptography命名空間），它將比大多數凡人做得更好。

Answer 2

哈希函數不保證哈希值的唯一性。如果輸入值範圍（判斷您的示例字符串）大於輸出值範圍（例如32位整數），則唯一性在物理上是不可能的。

Answer 3

這兩個字符串具有相同的字符。 （注意翻轉的'2'和'1'）

這就是爲什麼哈希值是相同的。

確保散列函數考慮到字符的順序。

Answer 4

我不太清楚你的工作環境。這是.Net代碼嗎？如果你真的想要好的散列碼，我建議你看一看密碼哈希（經過驗證的算法），而不是試圖自己寫。

順便說一句，你可以編輯你的文章並粘貼代碼作爲代碼示例（見工具欄）？這會使閱讀更容易。

Answer 5

「不要這樣做。」

編寫你自己的散列函數是一個很大的錯誤，因爲你的語言當然已經有了SHA-1的實現，這是一個非常好的散列函數。如果您只需要32位（而不是SHA-1提供的160位），則只需使用SHA-1的最後32位。

Answer 6

沒有散列函數可以保證唯一性。有大約40億32位整數，所以即使是最好的散列函數，當呈現大約40億個和1個字符串（大多數可能很久以前）時，也會產生重複。

移動到64位散列或甚至128位散列並不是真正的解決方案，儘管它減少了碰撞的可能性。

如果你想要一個更好的散列函數，你可以看看密碼哈希值，但是重新考慮你的算法並決定你是否可以用其他方式處理碰撞會更好。

Answer 7

System.Security.Cryptography命名空間包含多個可以爲你做散列的類（例如MD5），它們可能比你自己更好地散列它們，並且花費更少的工作量。

你並不總是必須重新發明輪子。

Answer 8

簡單異或是一個糟糕的散列：你會發現大量的字符串相撞。首先，哈希不依賴於字符串中字母的順序。

嘗試使用FNV哈希http://isthe.com/chongo/tech/comp/fnv/

這是實現非常簡單。它在每次XOR後移動哈希碼，所以不同順序的相同字母會產生不同的哈希。

Answer 9

有MD5散列的這裏

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

Answer 10

我固定的語法高亮他的視覺基本實現。

此外，對於那些誰不知道有關環境或暗示了一個更安全的哈希：它的經典（pre-.Net）VB，因爲淨將需要爲調用CopyMemory的括號。

IIRC，Classic VB沒有內置的安全哈希。網絡上沒有太多的東西，所以這可能是他最好的選擇。

Answer 11

這個特殊的散列函數異或字符串中的所有字符。不幸的是XOR是結合的：

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

因此，任何以相同的輸入字符的字符串將導致相同的散列碼。提供的兩個字符串是相同的，除了兩個字符的位置，因此它們應該具有相同的哈希碼。

您可能需要找到更好的算法，MD5將是一個不錯的選擇。

Answer 12

異或操作是可交換的;也就是說，當對字符串中的所有字符進行異或時，字符的順序無關緊要。字符串的所有字符將產生相同的XOR散列。

在你的例子中，你的第二個字符串可以從你的第一個字符串開始，通過交換「... Gen」後面的「1」和後面的第一個「2」來生成。

你的功能沒有問題。所有有用的哈希函數有時會產生衝突，並且您的程序必須準備好解決它們。

當輸入散列到已用先前輸入標識的值時發生衝突。如果散列算法不能產生衝突，則散列值需要與輸入值一樣大。與僅存儲輸入值相比，這樣的散列算法將是有限的使用。

-Al。

Answer 13

如果最大的問題是，它不佔字節的位置，你可以解決它是這樣的：

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 

唯一的區別是，它添加字符位置給它的字節值在異或之前。

Answer 14

散列函數並不意味着爲不同的字符串返回不同的值。但是，一個好的散列函數應該爲看起來相似的字符串返回不同的值。散列函數用於搜索許多原因，包括搜索大型集合。如果散列函數好，並且它返回範圍[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; 
    }