8

「可変」オブジェクト（GetHashCode（）メソッドがディクショナリでキーとして使用されているときに異なる結果を返す可能性があるオブジェクト）を使用することはお勧めできないことを理解しています。

以下は、ハッシュテーブルとして実装されているディクショナリがどのように機能するかについての私の理解です。

たとえばdict.Add(m1, "initially here was m1 object");、新しいキーを追加する場合、メソッドを使用するdictハッシュコードを計算します。次に、いくつかの内部計算を実行し、最後にこのオブジェクトを内部配列のある位置に配置します。m1GetHashCode()

たとえば、キーインデックスを使用して値を取得している場合、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<TKey, TValue>そのハッシュ値に影響を与えるような方法でオブジェクトを変更してはなりません。

オブジェクトが入っている間にオブジェクトを変更しているので、オブジェクトDictionaryは機能しません。

理由は、それほど難しくはありません。オブジェクトを入れます。ハッシュコードがであると仮定しましょう1。オブジェクトを1ハッシュテーブルのバケットに入れます。これで、オブジェクトはディクショナリの外部から変更され、その値（およびハッシュコード）はになり2ます。これで、誰かがそのオブジェクトを辞書のインデクサーに渡すと、ハッシュコードを取得し、それがであることがわかり2、2バケットを調べます。そのバケットは空なので、「申し訳ありませんが、要素はありません」と表示されます。

ここで、値とハッシュが。の新しいオブジェクトが作成されたと仮定します1。ディクショナリに渡され、ハッシュがであることがわかります1。1バケットを調べて、そのインデックスに実際にアイテムがあることを確認します。これはEquals、オブジェクトが実際に等しいかどうか（または、これが単なるハッシュ衝突であるかどうか）を判断するために使用されます。

さて、あなたの場合、オーバーライドしないため、ここでは失敗し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の1つが検索しているキーであるかどうかを確認します。

したがってEquals(object)、GetHashCode()一緒にオーバーライドする必要があります。それらの1つだけをオーバーライドすると、コンパイラから警告が表示されます。

キーがにある間にキーのハッシュコードが変化するとすぐに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<,>私は実際に、既存のアイテムを使用して1つを初期化するときに、そのような例外を確認しました（両方ともキータイプDictionary<,>のデフォルトを使用します）。EqualityComparer<>

于 2013-03-12T19:18:12.083 に答える