平均プログラミング言語がハッシュテーブルを実装するには大きすぎますか？ハッシュテーブルの最大サイズはどのくらいですか？
ゲームShiritoriを再生するプログラムを作成したいとします。ユーザが単語を入力した後、その単語が存在すれば、プログラムは辞書を検索する必要がある。一定のフラットファイルの読み込みを防止するには、プログラムでハッシュテーブルに100,000以上の単語を読み込んで、賢明なソリューションを開始しますか？
この種類のデータに特化したデータ構造とアルゴリズムがあります。 たとえば、文字列のハッシュテーブルよりもはるかにスペース効率のよいPatricia TrieまたはRadix Treeは、木であるため、ルックアップの計算量はO（log n）であり、構築はO（n log n） 。ファイルからファイルを読み込むので、O（n）で読み込むことができます。
Hashtable（Dictionary）はC＃で実装されていますが、内部32ビット整数アドレッシングを使用する以外は上限がありません（確かに2億を超えるアイテムはありません）。
100000個のアイテムは辞書にはあまり多くありません。 ガベージコレクタを使用している言語では、100,000個の文字列が割り当てられ、GCにいくらかのプレッシャーがかかることがあります。 実際のアプリケーションメモリフットプリントの詳細については、それを実行するだけです。
メモリが本当に懸念される場合は、単語辞書を格納するのに最適なPatricia TrieとRadix Treeを探してください。 しかし、辞書の使用を開始して、アプリケーションにどれだけのメモリがあるかを確認することができます。
文字列をユニコードと見なし、英語の平均単語が5.1文字（私はウェブ上で読む）であり、各文字列の32バイト（オブジェクトと長さ）を考慮すると、 4200000バイトの文字列の最小メモリ量（100000 *（32 + 5 * 2））。
応答と提案をありがとう。私は物理的な限界があるかどうか、またはハッシュテーブルが一般的に使用したくない程度に劣化しているかどうかはわかりませんでした。私はそれが言語の実装に依存している可能性が最も高いことを知っています。 –
10万の文字列しか詰まらないようになったのはごめんね。 –
「大きすぎますか？それは、「最高の食べ物は何ですか？」と尋ねるようなものです。
ハッシュテーブルが大きければ大きいほど、それ以上のメモリが必要ですが、実行速度は向上します。あなたは、より多くのスペースや時間が必要なものを決めなければなりません。
物理的制限（RAM）と実装の制限（Javaハッシュマップvs C＃ハッシュマップvs STLまたはブーストなど）私は、ハッシュマップが "すべき"もののハッシュテーブルのサイズの上限がハッシュアルゴリズムに依存すると考えています。ハッシュマップの元の意図は、コレクションのサイズが大きくなるにつれて一定のルックアップ時間を達成することです。良いハッシュアルゴリズムがあれば、大量の値に対して一意の鍵を生成することができます。しかし、悪いハッシュアルゴリズムを使用している場合、ルックアップ時間は、衝突を起こし始めたとき（ハッシュアルゴリズムに2つの固有の入力が同じ値を生成するようになる）に間に合うようになります。
しかし、それはあなたが探しているものではありません。私はまだ議論に別のポイントを追加するためにそこにこれを投げているだけで、私はまだ対処されていないと思う。あなたは@サルヴァトーレプレヴィチの答えを調べるべきだと思います。問題を考えると、彼が言いました解決策がよりよくフィットするように思えます。
一般に、ハッシュテーブルは、必要な大きさです。しかし、キャッシュ用に1つを使用している場合は、メモリの占有量を考慮する必要があります。 （辞書については、単一のオブジェクトとしてストレージに読み込まれ、読み込み時に処理する必要がない単一の連続したデータ構造として構築することができます）。 –