.Netディクショナリのエントリが追加順になっているのはなぜですか？

StackOverflow https://stackoverflow.com/questions/154307

質問

この動作を見たばかりで、少し驚いています...

辞書に3つまたは4つの要素を追加してから、<！> quot; For Each <！> quot;を実行した場合すべてのキーを取得するには、追加した順序と同じ順序で表示されます。

これが私を驚かせる理由は、Dictionaryが内部的にHashTableであることになっているためです。

ここで何が欠けていますか？ これは私が信頼できる行動ですか？

編集：OK、この might が発生する多くの理由（エントリへの別のリスト、これが偶然かどうかなど）をすでに考えていました。 私の質問は、これが実際にどのように機能するか知っているですか？

役に立ちましたか？

解決

3.5クラスライブラリで.NET Reflectorを使用すると、Dictionaryの実装が実際に項目を配列（必要に応じてサイズ変更される）に格納し、その配列にインデックスをハッシュすることがわかります。キーを取得すると、ハッシュテーブルを完全に無視し、アイテムの配列を反復処理します。このため、新しいアイテムが配列の最後に追加されるため、説明した動作が表示されます。次のことを行うと次のようになります。

add 1
add 2
add 3
add 4
remove 2
add 5

空のスロットを再利用するため、1 5 3 4が返されます。

他の多くの人がそうであるように、将来の（または過去の）リリースではこの動作を期待できないことに注意することが重要です。辞書をソートする場合は、 SortedDictionary クラスがあります。この目的。

他のヒント

辞書は、ハッシュされた順序でアイテムを取得します。それらが挿入順序で出てきたという事実は完全に偶然でした。

MSDNのドキュメントによると：

  

KeyCollection内のキーの順序は指定されていませんが、Valuesプロパティによって返されるValueCollection内の関連する値と同じ順序です。

この動作を当てにすることはできませんが、驚くことではありません。

単純なハッシュテーブルのキー反復を実装する方法を検討してください。ハッシュバケットに含まれているかどうかに関係なく、すべてのハッシュバケットを反復処理する必要があります。大きなハッシュテーブルから小さなデータセットを取得するのは非効率的です。

したがって、別個の重複したキーのリストを保持することは適切な最適化である可能性があります。二重リンクリストを使用しても、一定時間の挿入/削除が可能です。 （ハッシュテーブルバケットからこのリストに戻るポインターを保持します。）そのようにキーのリストを反復処理することは、バケットの数ではなく、エントリの数のみに依存します。

これは、2種類の辞書<！> quot; ListDictionary <！> quot;があった古い.NET 1.1の時代から来ていると思います。および<！> quot; HybridDictionary <！> quot;。 ListDictionary は、順序付きリストで、<！> quot;エントリの小さなセット<！> quot;に推奨されました。その後、 HybridDictionary がありました。内部的にリストとして編成されていますが、構成可能なしきい値より大きくなるとハッシュテーブルになります。これは、歴史的に適切なハッシュベースの辞書が高価であると考えられていたために行われました。今ではあまり意味がありませんが、.NETは古いHybridDictionaryの新しいDictionaryジェネリッククラスに基づいているだけだと思います。

注：とにかく、他の誰かがすでに指摘しているように、辞書の順序に頼らないでください

MSDN からの引用：

  

のキーの順序   辞書<！> lt;（Of <！> lt;（TKey、   TValue <！> gt;）<！> gt;）。KeyCollectionは   不特定ですが、同じ順序です   の関連する値として   辞書<！> lt;（Of <！> lt;（TKey、   TValue <！> gt;）<！> gt;）。ValueCollection   Dictionary <！> lt;（Of <！> lt;（TKey、   TValue <！> gt;）<！> gt;）。Valuesプロパティ。

テストで追加したキーとその順序は何ですか？

エントリはすべて、辞書の同じハッシュバケットにある可能性があります。各バケットは、おそらくバケット内のエントリのリストです。これは、順番に戻ってくるエントリを説明します。

私が知っていることから、これは依存する振る舞いではないはずです。すばやく確認するには、同じ要素を使用し、辞書に追加する順序を変更します。追加された順序でそれらを戻すか、それは単なる偶然であるかがわかります。

特定のリストサイズまでは、ハッシュする代わりにすべてのエントリをチェックする方が安価です。それがおそらく起こっていることです。

100個または1000個のアイテムを追加し、それらが同じ順序であるかどうかを確認します。

この種の<！> quot;仕様による<！> quot;は嫌いです。機能。クラスに<！> quot; Dictionary <！> quot;のような一般的な名前を付ける場合、<！> quot;一般的に期待される<！> quot;のように振る舞うべきだと思います。たとえば、std :: mapは常にキーと値のソートを保持します。

編集：明らかに解決策は、StededDictionaryを使用することです。これはstd :: mapと同様に動作します。

質問と回答の多くは、ハッシュテーブルまたは辞書の目的を誤解しているようです。これらのデータ構造には、データ構造に含まれるアイテムの値（または実際にはキー）の列挙に関して指定された動作はありません。

辞書またはハッシュテーブルの目的は、既知のキーが与えられた特定の値を効率的に検索できるようにすることです。辞書またはハッシュテーブルの内部実装は、ルックアップでこの効率を提供する必要がありますが、列挙または<！> quot; for << >> quot;に関して特定の動作を提供する必要はありません。値またはキーの繰り返しを入力します。

要するに、内部データ構造は、これらの値を、それらが挿入された順序を含む、希望する方法で格納および列挙できます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top