.NET Dictionary實現如何與可變對象一起工作

我知道使用「可變」對象是不可取的（對象的GetHashCode（）方法可以在Dictionary中用作鍵時返回不同的結果）。.NET Dictionary實現如何與可變對象一起工作

下面是我的字典，這是作爲一個哈希表來實現，如何工作的理解：

當我添加新鍵，例如dict.Add(m1, "initially here was m1 object");，dict計算m1使用GetHashCode()方法的哈希碼。然後它進行一些內部計算並最終將該對象放入其內部數組的某個位置。

當我使用密鑰索引獲取值時，例如dict[m1],dict再次計算哈希碼。然後它進行了一些內部計算，它給了我一個位於其內部數組內部的計算位置的對象。

但我認爲有一個我找不到的錯誤。

所以讓我們假設我有這樣的代碼：

class MutableObject 
    { 
     Int32 m_value; 

     public MutableObject(Int32 value) 
     { 
      m_value = value; 
     } 

     public void Mutate(Int32 value) 
     { 
      m_value = value; 
     } 

     public override int GetHashCode() 
     { 
      return m_value; 
     } 
    } 

    static void Main(string[] args) 
    { 
     MutableObject m1 = new MutableObject(1); 
     MutableObject m2 = new MutableObject(2); 

     var dict = new Dictionary<MutableObject, String>(); 
     dict.Add(m1, "initially here was m1 object"); 
     dict.Add(m2, "initially here was m2 object"); 

     Console.WriteLine("Before mutation:"); 
     Console.WriteLine("dict[m1] = " + dict[m1]); 
     Console.WriteLine("dict[m2] = " + dict[m2]); 

     m1.Mutate(2); 
     m2.Mutate(1); 

     Console.WriteLine("After mutation:"); 
     Console.WriteLine("dict[m1] = " + dict[m1]); 
     Console.WriteLine("dict[m2] = " + dict[m2]); 

     Console.ReadKey(true); 
    }

當我打電話Mutate方法，密鑰交換。所以我認爲它會給交換結果。但實際上這條線：Console.WriteLine("dict[m1] = " + dict[m1]);拋出KeyNotFoundException，我不明白爲什麼。很明顯，我在這裏丟失了一些東西......

來源

2013-03-12 acrilige

只有40億個可能的散列碼。假設運氣不好，在同一個散列表中有兩個不相同的對象，它們使用相同的散列碼。 *字典如何區分他們*？當你回答這個問題時，你會明白你的計劃爲什麼會給你看到的結果。 – 2013-03-12 19:16:40

我知道hasttable可以實現鏈接，或者打開alghoritms來處理碰撞。所以當我打電話給'dict [m1]'時，他得到了散列碼，在交換後等於2，然後...他做了什麼？他試圖弄清楚，使用這個哈希碼的對象是正確的，他應該返回哪個對象...... – acrilige 2013-03-12 19:27:23

你在1 Elm Street購買房子，然後在2 Elm Street買房子並搬到那裏。您將第二間房屋的地址標誌更改爲1 Elm Street。去榆樹街1號的郵件到達哪裏？ – 2013-03-12 19:31:40

如何。NET Dictionary實現可變對象

它不。該documentation for Dictionary狀態：

只要一個對象被用作Dictionary<TKey, TValue>的關鍵，它必須在不影響其散列值任何方式更改。

由於您在Dictionary中更改對象，所以無法使用。

至於爲什麼，這並不難看出。我們放入一個物體。我們假設哈希碼是1。我們把對象放在哈希表的1桶中。現在，該對象從Dictionary外部發生變化，因此它的值（和散列碼）爲2。現在，當某人將該對象賦予字典的索引器時，它將獲取哈希碼，請參閱它的結果爲2，並查看2存儲桶。那個桶是空的，所以它說，「對不起，沒有元素」。

現在讓我們假設一個新的對象是用值和散列值爲1創建的。它傳遞給字典，他看到散列是1。它在1存儲桶中查找，發現該索引確實存在一個項目。它現在使用Equals來確定對象是否實際上相等（或者如果這只是散列衝突）。

現在，在你的情況下，它會在這裏失敗，因爲你不覆蓋Equals，你使用的默認實現比較引用，因爲這是一個不同的對象，它不會有相同的引用。但是，即使您將其更改爲比較值，*第一個對象的突變值爲2，而不是1，因此它無法匹配。其他人建議修復這個Equals的方法，你真的應該這樣做，但它仍然不會解決你的問題。

一旦對象發生變異，找到它的唯一方法就是如果恰好發生變異值是散列衝突（這是可能的，但不太可能）。如果不是，那麼根據Equals，任何等於根據Equals都不會知道檢查正確的存儲桶，而檢查正確存儲桶的任何東西都不會相同。

我在開始時提到的引用不僅僅是一種最佳實踐。這不僅僅意外或怪異，也不會讓字典中的項目變異。 它只是不起作用。

現在，如果對象是可變的但它沒有在字典中發生變異，那就沒問題了。這可能有點奇怪，而即一個人可能會說的案例是壞習慣，即使它有效。

來源

2013-03-12 19:24:53 Servy

這是一個很好的解釋。感謝您的支持 – acrilige 2013-03-12 19:43:46

有趣的是：您提到的「散列衝突」只有在突變值與原始值具有相同的散列碼時纔會發生，如果兩者落入同一個存儲桶中，這是不夠的（因爲「Dictionary」會將完整散列代碼在比較相等之前）。 – svick 2013-03-12 21:34:13

@svick這就是我所指的，但我沒有深入探索這個例子，因爲它似乎不值得解釋。 – Servy 2013-03-13 03:53:09

僅僅使用字典查找來獲得相同的哈希碼是不夠的。由於散列衝突是可能的，因此密鑰也必須與查找的索引相等。

來源

2013-03-12 19:16:45 recursive

即使有了這種變化，它也無法工作。 'Dictionary'假定添加到它的項目在字典中不會改變它們的哈希碼。 – Servy 2013-03-12 19:23:17

您的MutableObject類不覆蓋Equals(object)。因此使用引用相等（從基類System.Object繼承）。

Dictionary<,>先（快速地）找到具有正確哈希碼的任何密鑰。然後它檢查每個候選密鑰，以檢查它們中的一個是否正在搜索它的密鑰Equals。因此Equals(object)和GetHashCode()應該被覆蓋在一起。如果您只覆蓋其中的一個，則會從編譯器獲得警告。

只要密鑰的哈希碼在Dictionary<,>中的密鑰發生變化，該密鑰將（可能）錯位在Dictionary<,>內部，處於錯誤的「桶」中，從而丟失。它不會被發現，因爲它的搜索將始終發生在它不在的存儲桶中。

在這個例子中，關鍵的丟失，因此可以再次補充：

var dict = new Dictionary<MutableObject, string>(); 

var m = new MutableObject(1); 

dict.Add(m, "Hello"); 

m.Mutate(2); 

dict.Add(m, "world"); 

foreach (var p in dict) 
    Console.WriteLine(p); 

var otherDict = new Dictionary<MutableObject, string>(dict); // throws

其實我已經見過這樣的一個例外，從現有Dictionary<,>一個Dictionary<,>與項目的初始化（無論是在使用密鑰類型的默認EqualityComparer<>）。

來源

2013-03-12 19:18:12

有人低估我沒有解釋？ – 2013-03-12 20:15:24

.NET Dictionary實現如何與可變對象一起工作

回答

相關問題