辞書の順序はまったく同じ内容であれば同じですか？

Question

I辞書の順序が不定であることを知っているが、MSDNはそう言う：列挙の目的のため

、辞書の各項目は、値とそのキーを表すKeyValuePair構造として扱われます。アイテムが返される順序は未定義です。

これは問題ありませんが、同じ内容の辞書が2つある場合は同じですか？

私が理解しているように、その順序はキーのハッシュによって決まり、2つの辞書が同じキーを持っていれば、同じハッシュを持つので同じ順序になります。

...右ですか？

ありがとうございます！

アンディ。

Answer 1

いいえ同じ注文であることが保証されていません。同じハッシュコードを持つDictionary<TKey, TValue>にいくつかのアイテムがあるシナリオを想像してみてください。それらが異なる順序で2つの辞書に追加されると、列挙の順序が異なることになります。 MSDNは、あなたがそれに依存する必要がその未定義を言う場合

は、例えば、以下の（準拠平等）のコードを考えてみましょう

class Example 
{ 
    public char Value; 
    public override int GetHashCode() 
    { 
     return 1; 
    } 
    public override bool Equals(object obj) 
    { 
     return obj is Example && ((Example)obj).Value == Value; 
    } 
    public override string ToString() 
    { 
     return Value.ToString(); 
    } 
} 

class Program 
{ 
    static void Main(string[] args) 
    { 
     var e1 = new Example() { Value = 'a' }; 
     var e2 = new Example() { Value = 'b' }; 
     var map1 = new Dictionary<Example, string>(); 
     map1.Add(e1, "1"); 
     map1.Add(e2, "2"); 

     var map2 = new Dictionary<Example, string>(); 
     map2.Add(e2, "2"); 
     map2.Add(e1, "1"); 

     Console.WriteLine(map1.Values.Aggregate((x, y) => x + y)); 
     Console.WriteLine(map2.Values.Aggregate((x, y) => x + y)); 
    } 
} 

このプログラムを実行しているの出力が

12 
21 

Answer 2

マイクロソフトの実装の詳細はわかりませんが、一般的には、辞書に同じ値にハッシュする項目が2つもない場合や、衝突する項目が同じ順序で追加されている。

Answer 3

です。定義されていないことは、辞書の実装が望む順序どおりに辞書を実装できることを意味します。つまり、プログラマは順序について何も仮定しないでください。辞書の中の要素の順序は入れた順序に依存するが、私は間違っている可能性があるとは考えずに個人的に考えているだろう。答えが何であっても、両方の注文が同じであるというふるまいを望むなら、それは間違っている。

Answer 4

「2つの辞書が同じ のキーを持っている場合、彼らは同じハッシュを持っているので、 同じ順序...」

私はこれが事実であるとは思いません。たとえそれが真実であっても、私はこれに頼らないでしょう。それが本当であれば、それは実装の詳細です。CLRまたはBCLのさまざまな実装では、変更されるか、または異なる可能性があります（Monoが気になる）。

マイクロソフトディクショナリの実装は少し複雑ですが、コードを5分見てから、列挙シーケンスはに基づいています。辞書は現在の状態になっていますサイズ変更の数と挿入順序。

Answer 5

ショートバージョン：いいえ

ロングバージョン：

[TestMethod] 
    public void TestDictionary() 
    { 
     Dictionary<String, Int32> d1 = new Dictionary<string, int>(); 
     Dictionary<String, Int32> d2 = new Dictionary<string, int>(); 

     d1.Add("555", 1); 
     d1.Add("abc2", 2); 
     d1.Add("abc3", 3); 
     d1.Remove("abc2"); 
     d1.Add("abc2", 2); 
     d1.Add("556", 1); 

     d2.Add("555", 1); 
     d2.Add("556", 1); 
     d2.Add("abc2", 2); 
     d2.Add("abc3", 3); 

     foreach (var i in d1) 
     { 
      Console.WriteLine(i); 
     } 
     Console.WriteLine(); 
     foreach (var i in d2) 
     { 
      Console.WriteLine(i); 
     } 
    } 

出力：

[555, 1] 
[abc2, 2] 
[abc3, 3] 
[556, 1] 

[555, 1] 
[556, 1] 
[abc2, 2] 
[abc3, 3] 

Answer 6

仕様は順序が「未定義」であると言うならば、あなたは明示的にそれを発注することなく、順序に依存することはできません。基礎となる実装は、新しいリリースまたはサービスパックを使用していつでも変更することができます。あなたの辞書は、任意の数の具体的な実装からアップキャストされるかもしれません。

基本的な実装は、適用される操作の順序に敏感です。この順序でキー 'a'、 'b'、 'c'を追加すると、異なる順序で同じキーセットを追加するよりも異なるデータ構造になります（ 'b'、 'c'、 'a' ）。削除も同様にデータ構造に影響する可能性があります。

たとえば、辞書の背後にあるデータ構造として使用すると、キーが順番に追加された場合、ネット結果は本質的にリンクされたリストである非常に不均衡なツリーになります。ノードがランダムな順序で挿入されていると、ツリーのバランスがよりよくなります。

操作としていくつかのデータ構造morphが実行されます。例えば、基礎となるデータ構造が赤/黒のツリーである辞書が実装されている場合、挿入および削除が発生するとツリーのバランスを保つために、ツリーノードは分割/回転されます。実際のデータ構造は、たとえ最終的な内容が同じであっても、操作の順序に大きく依存します。