.NET字典如何解決衝突？

我有一個自定義對象需要鍵入表的問題。我需要生成一個唯一的數字鍵。我遇到碰撞問題，我想知道我是否可以利用字典來幫助我。假設我有這樣一個對象：.NET字典如何解決衝突？

class Thingy 
{ 
    public string Foo; 
    public string Bar; 
    public string Others; 
}

等等更多領域。假設Foo和Bar是我的關鍵字段 - 如果它們在兩個Thingys之間相等，那麼這兩個對象應該被認爲是相等的（一個可能代表另一個的更新，其他字段被更新。）所以我有這些：

public override bool Equals(object obj) 
{ 
    Thingy thing = (Thingy)obj; // yes I do type check first 
    return (this.Foo == thing.Foo && this.Bar == thing.Bar); 
} 

public override int GetHashCode() 
{ 
    return (this.Foo + this.Bar).GetHashCode(); // using default string impl 
}

所以這個工作的大部分，但有兩個實際上不同的兩個Thingys具有相同的哈希碼的罕見場合。

我的問題是這樣的：我可以使用字典<Thingy, int>在哪裏放入我的Thingys，並使用字典中出現的順序值作爲我的實際密鑰？我在想，如果字典在檢測到罕見的哈希碼衝突時會調用我的Equals方法，確定這些對象實際上是不同的，並以不同的方式存儲它們。然後，當我查看圖像時，它會看到該散列的存儲桶並搜索正確的Thingy，再次使用Equals進行比較。

這是字典的情況，還是它只解決散列碼不同的衝突，但（散列％大小）是相同的？如果這不起作用，可能會發生什麼？

來源

2010-02-10 Tesserex

散列衝突隻影響性能，不影響完整性。

一個簡單的測試是將GetHashCode（）更改爲簡單返回1 ;.你會注意到字典仍然正常工作，但是對於任何合理的數據集，它將表現得非常糟糕。

來源

2010-02-10 20:52:39 Bob

很好的方式來說明這一點。 – itowlson

散列衝突將主要影響性能 - 不正確。只要Equals()行爲正確。

Dictionary使用散列碼作爲將項目組織到單獨的「桶」中的一種方式。如果太多項共享相同的散列碼，則可能會遇到性能問題。不過，只要Equals()可以正確區分實例，你應該得到正確的結果。

散列碼可能導致問題的地方是可變對象。如果您的Thingy類允許Foo或Bar針對字典中的項目進行更改，則可能無法在隨後的訪問嘗試中找到它。這是因爲現在生成的散列碼與用於在字典中存儲值的散列碼不同。

來源

2010-02-10 20:53:03 LBushkin

任何字典都是如此。所有字典類型都假定爲常量密鑰 – Joel

對於可變對象，由於它返回引用相等性，通常只需要單獨保留基本object.Equals（）方法。您通常需要==重載來測試值相等。因此，如果您單獨保留默認的object.Equals（），則可以使用可變對象作爲字典鍵，而不會產生副作用。 – Bob

通常不建議在非不可變類型中重寫操作符==。 MSDN文檔實際上討論了您可能想要重寫Object.Equals（）和「==」運算符的情況。 http://msdn.microsoft.com/en-us/library/ms173147%28VS.80%29.aspx – LBushkin

GetHashCode被設計用於散列表，其中碰撞需要被最小化但是不被消除。如果您需要生成一個真正唯一的密鑰，GetHashCode是一個合理的起點（並且不像guid那麼長），但是您需要將密鑰存儲爲對象的一部分並單獨維護已用密鑰的列表。

儘管您可能能夠從Dictionary的內部檢索一些看起來可用的東西，但它可能無法可靠地工作 - 例如，如果添加的內容多於字典最初分配處理的內容，則底層數據結構將會重建和個別項目可能會在字典的完全不同的部分。

來源

2010-02-11 00:50:58

實際上，我的意思是使用字典的意思是我將對象存儲爲字典的關鍵字，然後將新的最高int存儲爲值，並將該值用作我的表的關鍵字。所以在字典中的值將是連續的，如果我查找一個對象，我會得到表的唯一數字鍵。所以內部字典結構是不相關的。 – Tesserex

如此有效地使用字典向對象添加附加屬性 - 如果您正在使用可以控制的自定義對象進行工作，則幾乎不是最有效的方法。 –

.NET字典如何解決衝突？

回答

相關問題