ハッシュテーブルはいつ使用しますか？

Question

ハッシュテーブルを使用するとパフォーマンスが向上する場合とそうでない場合はどうなりますか？ハッシュテーブルを使用する場合はどのようなケースがありますか？

Answer 1

ハッシュテーブルを使用すると、パフォーマンス、そしてそれがないときは？

あなたが気にする理由がある場合は、ハッシュテーブルなどを考慮して実装し、実際のデータを入力してより良い結果を得ます。

つまり、ハッシュテーブルに必要な操作がある場合（ソートされた順序で繰り返し処理したり、別のハッシュテーブルとすばやく比較することを期待していない場合）、数百万以上（数十億、 ..））、おそらくあなたの最良の選択ですが、多くは、ハッシュテーブルの実装（特に、オープンハッシュとクローズの選択）、オブジェクトサイズ、ハッシュ関数の品質と計算コスト/ランタイムに依存します。比較コスト、さまざまなキャッシュレベルでのコンピュータのメモリパフォーマンスの奇妙さ...要するに：教育的な推測さえも測定よりも良い選択肢にするには、あまりにも多くのことが重要です。

ハッシュテーブルを使用しない場合はどうなりますか？あなたがバイナリ・ブロブを与えているし、重要であるそこにどのビットを知っているが、あなたはint cmp(const T&, const T&)機能を持っていないん

• が入力ハッシュ化することができません（例：主に

あなたは）std::mapのために使用することができ、または

可能/利用可能なハッシュ関数は非常に衝突しやすい、またはあなたがワットを避けたい

です

ハッシュテーブルのサイズを変更するハッシュ衝突要素（おそらくあなたのソフトウェアをクラッシュさせたり遅くしようとしている誰かによって「操作」）

の多くを扱う

• ：にプレサイジングしない限りためorstの場合のパフォーマンスヒット（大量のメモリを使用すると無駄になり、速度が遅くなる可能性があります）、大部分の実装ではハッシュテーブルに使用する配列が毎回大きくなり、次に大きな配列を割り当ててコンテンツをコピーします。平均がまだO（1）であっても、この再ハッシングを通常のO（1）の動作よりもはるかに遅くする特定の挿入。すべてのケースでより一貫した動作が必要な場合は、残高2分木のようなものが表示されます。

アクセスパターンは非常に特殊です（例：特定のソート順で「近く」のキーを持つ要素で頻繁に操作される）、キャッシュ効率は、メモリに近い場所に保管されている他のストレージモデル（バケットソートされた要素など）例えばソート順反復

Answer 2

ハッシュテーブルを使用してO（1）のアクセス時間を取得します。辞書を想像してみてください。あなたが言葉を探しているとき、例えば「幸せ」、あなたはまっすぐに「H」に飛びます。ここでハッシュ関数は開始アルファベットによって決定されます。あなたが探しているのは

データが注文されたときやソートされた数字のような注文が必要なときにハッシュテーブルを使用するのは意味がありません。 （アルファベットはABCD .... XYZの順ですが、AとZを切り替えた場合は、辞書に入れ替えられていることを前提にしても問題ありません）