読み取り専用ディクショナリアクセスで最も効率的なメモリ内データ構造

Question

C＃では、Dictionary<int, T>に入れることができる静的なデータがあります。Tは参照型です。 Webアプリケーションは静的に1回だけ初期化する必要があります（変更されません）。

パフォーマンスの挿入や削除について心配する必要はないので、使用するのに最適なデータ構造は何ですか？私はおそらく、かなり均等に間隔を置いて〜100,000のエントリのようなものを見ています。

私はこのデータを取得するための最適なアルゴリズムを探しています。 Dictionary<>は悪くありませんが、読み取り専用のデータ用に最適化されたものがなければならないと思います。

これらのキーの範囲が0〜400,000であるとは思われますが、確認していません。そのような場合は、推奨事項はどのように変更されますか？ （私は可能な答えとして投稿すると思っています）。

---

は、たぶん私は可能性があります。1回のデータによる

1. スキャンとは、第二のパスを取る最高のキー
2. が最高のキー+ 1
3. の大きさを持つ配列を割り当てつかみますデータを配列に格納します。

これは、合理的な負荷係数を持つHas​​hTable/Dictionaryよりも優れているか悪いですか？

Answer 1

Dicrionaryに行くための正しい方法で、ここMSDNからの引用です：

（TKEY、TValueの）辞書ジェネリッククラスの値のセットに キーのセットからマッピングを提供します。辞書 への各追加は、値とそれに関連するキーで構成されます。 Dictionary（Of TKey、TValue）クラスがハッシュテーブルとして実装されているため、キーを使用して で値を取得すると、O（1）に近い非常に高速です。です。

辞書を構築中（ハッシュと計算木を計算する）には時間がかかりますが、キーでデータを読み込むには速やかに吹き飛ばされます。

編集

それはキーがアイテムインデックスになり、簡単なarrray、一緒に行くことは理にかなって0-400kあなたは範囲から現在の50％以上のキーを持つことになります場合。これはあなたにO（1）の複雑さを与えます。 しかし、あなたによれば、鍵の25％しか存在しません。だから私はこの場合の辞書に行くだろう、私はそれが単純な配列に比べて各キーと値のペアを格納するメモリの75％のオーバーヘッドを持っているとは思わない。

Answer 2

実際に辞書であれば、トライは合理的にうまく動作します。 Dictionary（ハッシュテーブル）は、微調整している限り、別の可能性があります。どちらが速いだろう...私は知らない、あなたはそれをプロファイルする必要があるだろうと思う。スペース的には、トライが手を下ろします。私は.NETが標準ライブラリにトライを持っているとは思っていませんが、実装されている実装がいくつかあるはずです。