如何提高短字符串的散列以避免衝突？

Question

我在使用.NET4中的短字符串進行哈希碰撞時遇到了問題。
編輯：我在使用內置的字符串散列函數。

我實施使用存儲轉換的方向是這樣

public class MyClass 
{ 
    private string _from; 
    private string _to; 

    // More code here.... 

    public MyClass(string from, string to) 
    { 
     this._from = from; 
     this._to = to; 
    } 

    public override int GetHashCode() 
    { 
     return string.Concat(this._from, this._to).GetHashCode(); 
    } 

    public bool Equals(MyClass other) 
    { 
     return this.To == other.To && this.From == other.From; 
    } 

    public override bool Equals(object obj) 
    { 
     if (obj == null) return false; 
     if (this.GetType() != obj.GetType()) return false; 
     return Equals(obj as MyClass); 
    } 
} 

這是依賴於方向的和from和to對象的高速緩存是由短字符串，如「AAB」和「ABA表示」。

我得到這些小字符串的稀疏哈希碰撞，我嘗試了一些簡單的像添加鹽（沒有工作）。

問題是太多我喜歡「AABABA」小弦的碰撞與「ABAAAB」的反向其散列（請注意，這些都不是真實的例子，我不知道，如果AAB和ABA實際上導致衝突！）

和我已經重型像執行MD5（它的工作原理，但要慢得多）

我還實施了從喬恩斯基特這裏的建議：
Should I use a concatenation of my string fields as a hash code? 這工作，但我不知道知道它與我的各種3字符串是多麼可靠。

如何改善和穩定小字符串的散列而不增加太多像MD5的開銷？

編輯：爲迴應發佈的一些答案......緩存是使用從MyClass鍵入的併發字典實現的，如上所述。如果我的代碼簡單的東西像@JonSkeet的代碼鏈接替換GetHashCode上面我貼：

int hash = 17; 
hash = hash * 23 + this._from.GetHashCode(); 
hash = hash * 23 + this._to.GetHashCode();   
return hash; 

一切功能正常。 值得注意的是，在這種特殊的使用情況下，緩存不在多線程環境中使用，所以沒有競爭條件。

編輯：我還應該指出，這種不正當行爲是平臺依賴。它在我完全更新的Win7x64機器上按預期工作，但在未更新的Win7x64機器上無法正常工作。我不知道什麼更新丟失的擴展，但我知道它沒有Win7 SP1 ...所以我會假設也可能有一個框架SP或更新它缺少以及。

編輯：由於抱怨，我的問題不是由哈希函數的問題引起的。我有一個難以捉摸的競爭條件，這就是爲什麼它在一些計算機上工作而不是其他人，以及爲什麼「較慢」的哈希方法使事情正常工作。我選擇的答案是最有用的理解爲什麼我的問題不是字典中的散列衝突。

Answer 1

您確定碰撞是誰造成問題嗎？當你說

我終於發現是什麼原因導致了這個bug

你的意思是你的代碼或其他東西的一些緩慢？如果不是，我很好奇這是什麼問題？因爲任何散列函數（有限域上的「完美」散列函數除外）都會導致衝突。

我把快件的代碼來檢查衝突的3個字母的單詞。而且這段代碼並不會爲它們報告一個單一的衝突。你明白我的意思嗎？看起來像buid-in哈希算法並不是那麼糟糕。

Dictionary<int, bool> set = new Dictionary<int, bool>(); 
char[] buffer = new char[3]; 
int count = 0; 
for (int c1 = (int)'A'; c1 <= (int)'z'; c1++) 
{ 
    buffer[0] = (char)c1; 
    for (int c2 = (int)'A'; c2 <= (int)'z'; c2++) 
    { 
     buffer[1] = (char)c2; 
     for (int c3 = (int)'A'; c3 <= (int)'z'; c3++) 
     { 
      buffer[2] = (char)c3; 
      string str = new string(buffer); 
      count++; 
      int hash = str.GetHashCode(); 
      if (set.ContainsKey(hash)) 
      { 
       Console.WriteLine("Collision for {0}", str); 
      } 
      set[hash] = false; 
     } 
    } 
} 

Console.WriteLine("Generated {0} of {1} hashes", set.Count, count); 

雖然你可以挑選幾乎衆所周知的散列函數的任何（如大衛提到的），甚至選擇一個「完美」的哈希值，因爲它看起來像你的域名是有限的（如最小完美hash）......它如果問題的根源是真正的碰撞，那將是很好的理解。

更新

我想說的是，.NET內置的散列函數的字符串是沒有那麼糟糕。它不會給出太多的碰撞，您需要在常規場景中編寫自己的算法。這並不取決於字符串的長度。如果你有很多6符號的字符串，並不意味着你看到碰撞的機會比用1000符號的字符串更高。這是散列函數的基本屬性之一。

再次，另一個問題是，什麼樣的問題，你是因爲碰撞的體驗？所有內置哈希表和字典都支持衝突解決。所以我會說你所能看到的只是......可能有些緩慢。這是你的問題嗎？

至於你的代碼

return string.Concat(this._from, this._to).GetHashCode(); 

這可能會導致問題。因爲在每個哈希碼計算上你都會創建一個新的字符串。也許這是什麼原因導致你的問題？

int hash = 17; 
hash = hash * 23 + this._from.GetHashCode(); 
hash = hash * 23 + this._to.GetHashCode();   
return hash; 

這將是更好的方法 - 只是因爲你不在堆上創建新的對象。實際上，這是這種方法的一個要點 - 在不創建新對象的情況下，獲得具有複雜「關鍵」的對象的良好散列碼。所以如果你沒有一個單一的價值鍵，那麼這應該適合你。順便說一句，這不是一個新的散列函數，這只是一種結合現有散列值而不影響散列函數主要屬性的方法。

Answer 2

任何常見的散列函數都應該適用於此目的。如果你碰到這樣的短串，我會說你正在使用一個異常糟糕的散列函數。您可以使用Jenkins或Knuth's而沒有問題。

這裏是一個非常簡單的哈希函數，應該是足夠的。 （在實現C，但應該很容易移植到任何類似的語言。）

unsigned int hash(const char *it) 
{ 
unsigned hval=0; 
while(*it!=0) 
{ 
    hval+=*it++; 
    hval+=(hval<<10); 
    hval^=(hval>>6); 
    hval+=(hval<<3); 
    hval^=(hval>>11); 
    hval+=(hval<<15); 
} 
return hval; 
} 

注意，如果要修剪此函數的輸出的比特，你必須使用至少顯著位。你也可以使用mod來減少輸出範圍。字符串的最後一個字符只會影響低位。如果你需要一個更均勻的分佈，改變return hval;到return hval * 2654435761U;。

更新：

public override int GetHashCode() 
{ 
    return string.Concat(this._from, this._to).GetHashCode(); 
} 

這是壞了。它從=「foot」，to =「ar」與從=「foo」到=「tar」一樣。由於您的Equals函數並不認爲這些函數相同，所以您的散列函數不應該這樣做。可能的解決方法包括：

1）表格，「XXX」的字符串，來討論討論這一點。 （這是假設字符串「XXX」幾乎從未出現在您輸入的字符串。

2）將「從」的哈希值與「到」哈希值。你將不得不使用一個聰明的組合功能。例如，XOR或sum將導致from =「foo」，to =「bar」將從=「bar」到=「foo」的哈希相同。不幸的是，如果不知道哈希函數的內部結構，選擇正確的組合函數並不容易。您可以嘗試：

int hc1=from.GetHashCode(); 
int hc2=to.GetHashCode(); 
return (hc1<<7)^(hc2>>25)^(hc1>>21)^(hc2<<11);