8

我知道不建议使用“可变”对象（其 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，我不明白为什么。显然我在这里遗漏了一些东西......

4

3 回答 3

8

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

它没有。Dictionary的文档指出：

只要一个对象被用作 中的键Dictionary<TKey, TValue>，它就不能以任何影响其哈希值的方式发生变化。

由于您在对象中更改对象时Dictionary将无法正常工作。

至于为什么，不难看出。我们放入一个对象。假设哈希码是1. 我们将对象放1入哈希表的桶中。现在该对象从 Dictionary 外部发生变异，因此它的值（和哈希码）是2. 现在，当有人将该对象提供给字典的索引器时，它会获取哈希码，看看它是2，然后在2桶中查找。那个桶是空的，所以它说，“对不起，没有元素”。

现在让我们假设创建了一个新对象，其值和散列为1. 它被传递给 Dictionary，它看到哈希是1. 它在1存储桶中查找，发现该索引处确实有一个项目。它现在用于Equals确定对象是否实际上相等（或者这是否只是哈希冲突）。

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

一旦对象发生变异，找到它的唯一方法就是如果发生变异值是哈希冲突（这是可能的，但不太可能）。如果不是，那么根据 相等的任何东西Equals都不会知道检查正确的桶，并且检查正确的桶的任何东西都不会根据 相等Equals。

我一开始提到的引用不仅仅是一个最佳实践。对字典中的项目进行变异不仅是出乎意料的、奇怪的或表现不佳的。 它只是行不通。

现在，如果对象是可变的，但在字典中没有发生突变，那很好。这可能有点奇怪，人们可能会说这是不好的做法，即使它有效。

于 2013-03-12T19:24:53.340 回答
1

进行字典查找以具有相同的哈希码是不够的。由于哈希冲突是可能的，因此键也必须与正在查找的索引相同。

于 2013-03-12T19:16:45.983 回答
1

您的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-12T19:18:12.083 回答