.NET Dictionary实现如何与可变对象一起使用

Question

我理解不建议使用"可变"对象(GetHashCode()方法在将它们用作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,我无法理解为什么.显然我在这里遗漏了一些东西......

Answer 1

.NET Dictionary实现如何与可变对象一起使用

它没有.字典的文档说明:

只要将对象用作其中的键Dictionary<TKey, TValue>,就不得以任何影响其哈希值的方式进行更改.

由于您正在更改对象,因此Dictionary它不起作用.

至于为什么,这并不难看出来.我们放了一个对象.我们假设哈希码是1.我们将对象放在1哈希表的桶中.现在,对象从Dictionary外部变异,以便它的值(和哈希码)是2.现在当有人将该对象提供给字典的索引器时,它会获取哈希码,看看它是什么2,然后查看2存储桶.那个桶是空的,所以它说,"对不起,没有元素".

现在让我们假设一个新的对象是用值和哈希值创建的1.它传递给字典,后者看到哈希是1.它看起来在1桶中,发现该索引确实有一个项目.它现在用于Equals确定对象实际上是否相等(或者这只是一个哈希冲突).

现在,在你的情况下,它将在这里失败,因为你没有覆盖Equals,你正在使用比较引用的默认实现,因为这是一个不同的对象,它将没有相同的引用.但是,即使您更改它以比较值,*第一个对象被突变为具有值2,而不是1,因此它无论如何都不会匹配.其他人建议修复这种Equals方法,你真的应该这样做,但它仍然无法解决你的问题.

一旦对象发生变异,找到它的唯一方法就是如果恰好发生了变异值是一个哈希冲突(这是可能的,但不太可能).如果不是,那么任何相同的东西Equals都不会知道检查正确的桶,任何检查正确桶的东西都不会相等Equals.

我在开始时提到的引用不仅仅是最佳实践.改变词典中的项目并不仅仅是出乎意料或奇怪或无法执行. 它只是不起作用.

现在,如果对象是可变的但是在字典中没有变异那么那就没问题了.它可能是一个有点古怪,而这就是人们可以说是不好的做法的情况下,即使它的工作原理.