47

ここでの多くの質問への回答としてこれを読みました。しかし、それは正確にはどういう意味ですか？

var test = new Dictionary<int, string>();
test.Add(0, "zero");
test.Add(1, "one");
test.Add(2, "two");
test.Add(3, "three");

Assert(test.ElementAt(2).Value == "two");

上記のコードは期待どおりに動作するようです。では、どのように辞書は順不同とみなされるのでしょうか? 上記のコードはどのような状況で失敗する可能性がありますか?

4

7 に答える 7

77

1 つには、これがinsert-orderとkey-orderのどちらであると予想されるかが明確ではありません。たとえば、次のように書いた場合、結果はどうなるでしょうか。

var test = new Dictionary<int, string>();
test.Add(3, "three");
test.Add(2, "two");
test.Add(1, "one");
test.Add(0, "zero");

Console.WriteLine(test.ElementAt(0).Value);

「3」と「0」のどちらを期待しますか?

たまたま、現在の実装では、何も削除しない限り挿入順序が保持されていると思いますが、これに頼ってはいけません。これは実装の詳細であり、将来変更される可能性があります。

削除もこれに影響します。たとえば、このプログラムの結果はどうなると思いますか?

using System;
using System.Collections.Generic;

class Test
{ 
    static void Main() 
    {
        var test = new Dictionary<int, string>();
        test.Add(3, "three");
        test.Add(2, "two");
        test.Add(1, "one");
        test.Add(0, "zero");

        test.Remove(2);
        test.Add(5, "five");

        foreach (var pair in test)
        {
            Console.WriteLine(pair.Key);
        }
    }     
}

実際には (私のボックスでは) 3、5、1、0 です。5 の新しいエントリは、以前に 2 によって使用された空になったエントリを使用しています。ただし、これも保証されません。

再ハッシュ (辞書の基になるストレージを拡張する必要がある場合) は、影響を与える可能性があります...あらゆる種類のことが影響します。

順序付きコレクションとして扱わないでください。そのために設計されたものではありません。たまたま機能するようになったとしても、クラスの目的に反する文書化されていない動作に依存しています。

于 2011-06-17T10:58:56.970 に答える
26

Aはハッシュ テーブルをDictionary<TKey, TValue>表し、ハッシュテーブルには順序の概念はありません。

ドキュメントはそれをかなりよく説明しています：

列挙のために、ディクショナリ内の各項目は、値とそのキーを表す KeyValuePair 構造体として扱われます。アイテムが返される順序は定義されていません。

于 2011-06-17T10:58:03.227 に答える
10

ここには良いアイデアがたくさんありますが、散らばっているので、問題が解決されたとしても、より良いレイアウトの答えを作成しようと思います。

まず、辞書には順序が保証されていないため、キーをすばやく検索して対応する値を見つけるためにのみ使用するか、順序を気にせずにすべてのキーと値のペアを列挙します。

注文が必要な場合はOrderedDictionaryを使用しますが、トレードオフとしてルックアップが遅くなるため、注文が必要ない場合は要求しないでください。

辞書（およびJavaのHashMap）はハッシュを使用します。これは、テーブルのサイズに関係なく、O（1）時間です。順序付けられた辞書は通常、O（log2（n））であるある種のバランスの取れたツリーを使用するため、データが大きくなるにつれてアクセスが遅くなります。比較するには、100万個の要素の場合、これは2 ^ 20のオーダーであるため、ツリーのルックアップは20のオーダーで行う必要がありますが、ハッシュマップのルックアップは1です。それはかなり速いです。

ハッシュは決定論的です。非決定論とは、最初にhash（5）を実行し、次にhash（5）を実行すると、別の場所を取得することを意味します。それは完全に役に立たないでしょう。

人々が言うことは、辞書に物事を追加する場合、順序は複雑であり、要素を追加する（または削除する可能性がある）たびに変更される可能性があるということです。たとえば、ハッシュテーブルに500kの要素があり、400kの値があるとします。もう1つ追加すると、効率を上げるために約20％の空きスペースが必要になるため、重要なしきい値に到達します。そのため、より大きなテーブル（たとえば、100万エントリ）が割り当てられ、すべての値が再ハッシュされます。今では、それらはすべて以前とは異なる場所にあります。

同じ辞書を2回作成すると（私のステートメントを注意深く読んでください、同じです）、同じ順序になります。しかし、ジョンが正しく言っているように、それを当てにしないでください。最初に割り当てられたサイズであっても、物が多すぎると同じではなくなる可能性があります。

これは優れた点をもたらします。ハッシュマップのサイズを変更しなければならないのは、本当に本当に費用がかかります。つまり、より大きなテーブルを割り当て、すべてのキーと値のペアを再挿入する必要があります。したがって、1回の拡張でも発生するのではなく、必要なメモリの10倍を割り当てる価値があります。ハッシュマップのサイズを把握し、可能な場合は十分に事前に割り当てておくと、パフォーマンスが大幅に向上します。また、サイズ変更されない不適切な実装がある場合、小さすぎるサイズを選択すると、問題が発生する可能性があります。

ジョンが彼の答えの私のコメントで私と議論したのは、2つの異なる実行で辞書にオブジェクトを追加すると、2つの異なる順序が得られるということでした。本当ですが、それは辞書のせいではありません。

あなたが言う時：

new Foo();

メモリ内の新しい場所に新しいオブジェクトを作成しています。

値Fooを辞書のキーとして使用し、他の情報がない場合、それらが実行できるのは、オブジェクトのアドレスをキーとして使用することだけです。

つまり、

var f1 = new Foo(1);
var f2 = new Foo(1);

f1とf2は、同じ値であっても同じオブジェクトではありません。

したがって、それらを辞書に入れる場合：

var test = new Dictionary<Foo, string>();
test.Add(f1, "zero");

それが次のものと同じであると期待しないでください：

var test = new Dictionary<Foo, string>();
test.Add(f2, "zero");

f1とf2の両方が同じ値であっても。これは、辞書の決定論的な動作とは何の関係もありません。

ハッシュはコンピュータサイエンスの素晴らしいトピックであり、データ構造で教えるのが私のお気に入りです。

赤黒木とハッシュに関するハイエンドの本については、Cormen and Leisersonをチェックしてください。Bobという名前のこの男は、ハッシュと最適なハッシュに関するすばらしいサイトを持っています：http: //burtleburtle.net/bob

于 2011-06-17T18:21:38.390 に答える
4

順序は非決定論的です。

ここから

列挙のために、ディクショナリ内の各項目は、値とそのキーを表す KeyValuePair 構造体として扱われます。アイテムが返される順序は定義されていません。

おそらくあなたのニーズにはOrderedDictionaryが必要です。

于 2011-06-17T10:59:23.770 に答える
0

C＃や.NETのいずれかはわかりませんが、ディクショナリの一般的な概念は、キーと値のペアのコレクションであるということです。
たとえば、リストや配列を反復処理する場合のように、辞書に順番にアクセスすることはありません。
キーを持ってアクセスし、辞書にそのキーの値があるかどうか、そしてそれが何であるかを見つけます。
あなたの例では、たまたま連続していて、ギャップがなく、挿入の昇順である数字キーを含む辞書を投稿しました。
ただし、キー「2」の値を挿入する順序に関係なく、キー「2」を照会するときに常に同じ値を取得します。
C＃で数字以外のキーの種類が許可されているかどうかはわかりませんが、その場合は同じで、キーに明示的な順序はありません。
実際の辞書との類似性は混乱を招く可能性があります。単語であるキーはアルファベット順に並べられているため、すばやく見つけることができますが、そうでない場合でも、「Aardvark」という単語の定義により、辞書は機能します。 「ゼブラ」の後に来たとしても、「同じ意味になります。一方、小説を考えてみてください。ページの順序を変更しても、本質的に順序付けられたコレクションであるため、意味がありません。

于 2011-06-17T12:19:44.710 に答える
0

このクラスDictionary<TKey,TValue>は、配列に基づくインデックス リンク リストを使用して実装されます。アイテムが削除されない場合、バッキング ストアはアイテムを順番に保持します。ただし、アイテムが削除されると、配列が展開される前に、スペースが再利用のためにマークされます。結果として、たとえば新しい辞書に 10 項目が追加され、4 番目の項目が削除され、新しい項目が追加され、辞書が列挙された場合、新しい項目は 10 番目ではなく 4 番目に表示される可能性がありますが、その保証はありません。の異なるバージョンでDictionaryも同じように処理されます。

IMHO、アイテムが削除されていない辞書は元の順序でアイテムを列挙することをMicrosoftが文書化するのに役立ちましたが、アイテムが削除されると、辞書への将来の変更はその中のアイテムを任意に並べ替える可能性があります。アイテムが削除されない限り、そのような保証を維持することは、ほとんどの合理的な辞書の実装にとって比較的安価です。アイテムが削除された後も保証を維持し続けると、はるかに費用がかかります。

AddOnlyDictionaryまたは、任意の数のリーダーと同時に単一のライターに対してスレッドセーフであり、アイテムを順番に保持することを保証するが役立つ場合があります(アイテムが追加されるだけで、決して削除または変更されないことに注意してください)。 -現在含まれているアイテムの数を記録するだけで「スナップショット」を取得できます)。汎用ディクショナリをスレッド セーフにするのはコストがかかりますが、上記のレベルのスレッド セーフを追加するのは安価です。複数のライターと複数のリーダーを効率的に使用するには、リーダーとライターのロックを使用する必要はありませんが、ライターをロックし、リーダーが気にしないようにすることで簡単に処理できることに注意してください。

もちろん、 Microsoft はAddOnlyDictionary上記のように を実装していませんが、スレッド セーフConditionalWeakTableに追加専用のセマンティクスがあることに注目するのは興味深いことです。削除を許可するコレクション。

于 2014-07-12T17:51:45.690 に答える
0

Dictionary< string, Obj> は、SortedDictionary< string, Obj > ではなく、デフォルトで挿入順で並べられます。奇妙なことに、キー文字列の順序でソートされた辞書を持つために、SortedDictionary を具体的に宣言する必要があります。

public SortedDictionary<string, Row> forecastMTX = new SortedDictionary<string, Row>();
于 2016-08-30T19:53:53.033 に答える