這個散列函數會異常頻繁地碰撞嗎？

我有下面的代碼來產生對象的哈希：這個散列函數會異常頻繁地碰撞嗎？

public int GetHashCode(MyType obj) 
{ 
    return (obj.Prop1.GetHashCode() + obj.Prop2.GetHashCode() + obj.Prop3.GetHashCode()).GetHashCode(); 
}

即我添加所有屬性的哈希碼，然後採取這個哈希。

在回顧中，一位同事建議說這會頻繁發生碰撞。我不知道這是正確的，因爲：

鑑於散列碼與選擇相同的頻率之間的正數和負數，它們環繞，我不認爲有我們獲得有關可能性的任何其他信息的這些數字的總和與數字本身相反
在它們的總和是非隨機的程度上，散列碼被設計爲使得「靠近在一起」的數字變得「相距很遠」，因此饋送非均勻 - 分配給函數的值不應該是個問題

誰是正確的？

它是在C＃中，以防答案是特定於語言的。

來源

2011-06-08 Xodarap

什麼是你同事的原因是什麼？ – 2011-06-08 22:01:12

是。

只是假設Prop1，Prop2等是int類型。通常只使用較低範圍的整數。你的總和方法會比必要的更頻繁地碰撞。

7的HasCode是7，當它自己散列int時，它是非常有意義的。但是用你的代碼，元組<7, 3>,<3, 7>和<8, 2>都將具有相同的哈希值。簡單XOR而不是Addition也是如此。

的常見的方法是加入一些（素數）的數字和變速：

public int GetHashCode(MyType obj) 
{ 
    int hash = 0; 
    unchecked 
    {   
    hash += 19 * obj.Prop1.GetHashCode(); 
    hash += 31 * obj.Prop2.GetHashCode(); 
    hash += 37 * obj.Prop3.GetHashCode(); 
    } 
    return hash; 
}

中的數字19，31，37是不是太關鍵的。如果你喜歡，你可以使用OR或XOR而不是+。

來源

2011-06-08 22:01:54

素數很好，並且優於移位，因爲簡單的分箱算法可能只需要HashCode的較低N位;如果屬性發生偏移，它們可能會完全被忽略。 – 2011-06-08 22:33:38

XORing會更好：

public int GetHashCode(MyType obj) 
{ 
    return obj.Prop1.GetHashCode()^
      obj.Prop2.GetHashCode()^
      obj.Prop3.GetHashCode(); 
}

來源

2011-06-08 22:01:03

查看Henk Holterman的推理。如果某些屬性的GetHashCode不使用整個範圍，則使用移位混合應該提供更好的分佈... – 2011-06-08 22:14:46

您可以使用修改FNV的hashCode發生器，一個非常類似的問題已經回答了（由我） here

來源

2011-06-28 02:24:43

這個散列函數會異常頻繁地碰撞嗎？

回答

相關問題