hash高いルックアップ速度を要求するアプリケーションを作成したい場合は、最初にこれに頼る必要があり、他のデータ構造ではそれが保証されないことを覚えておいてください。
しかし、いくつか例を挙げると、接尾辞ツリーなど、異なると言っている多くの投稿を見たとき、私は混乱しました。
hashでは、高速ルックアップには常に最適なのだろうか？高速なルックアップと少ないスペース コストの両方が必要な場合はどうすればよいですか?
高速ルックアップとスペース効率に関するデータ構造またはアルゴリズム ** について講義している資料 (書籍または論文) はありますか? このようなものはどれも高く評価されています。
それで、ハッシュは常に高速ルックアップに最適なのだろうか？
いいえ。コメントで述べたように：
[いくつかの一般的な問題] に最適なデータ構造というものは決してありません。すべてがケース依存です。とにかく文字列を読み取る必要があるため、トライと基数ツリーは文字列に最適です。配列は単純さと優れたキャッシュ効率を可能にし、通常は小規模な静的情報に最適です。
私はかつて、ツリーがハッシュ テーブルよりも優れている可能性がある場合の関連する質問に答えました:ハッシュ テーブル v/s ツリー
高速なルックアップと少ないスペース コストの両方が必要な場合はどうすればよいですか?
両者は矛盾しているかもしれません。Xsizeのハッシュテーブルと size のハッシュ テーブルの単純な例でも2*X。ハッシュ テーブルが大きいほど衝突が発生する可能性が低くなるため、小さいテーブルよりも高速であることが期待されます。
高速ルックアップとスペース効率に関するデータ構造またはアルゴリズムについて講義している資料 (書籍または論文) はありますか?
アルゴリズムの紹介では、使用される主要なデータ構造について詳しく説明しています。開発されたアルゴリズムはすべて、優れたスペースと時間の効率を提供しようとしますが、前述のようにトレードオフがあり、特定のケースでは他のアルゴリズムよりも優れているアルゴリズムもあります。
特定の問題に対して適切なアルゴリズム/データ構造/設計を選択することがエンジニアリングの目的ですよね?
ここで文字列について話していると思いますが、答えは「いいえ」です。ハッシュは文字列を検索するための最速または最もスペース効率の良い方法ではありません。もちろん、ハッシュアルゴリズムを作成することは、トライを作成するよりもはるかに簡単です。
ウィキペディアや試行に関する本で見つけられないことの1つは、文字ごとに1つのノードで単純に実装すると、非効率的な1つの子のノードが多数発生することです。CPUを実際に消費するトライを作成するには、ノードを実装して、ノードが可変数の文字を持つことができるようにする必要があります。もちろん、これは単純なトライを書くよりもさらに難しいです。
私は10億を超えるエントリを処理するトライの実装を作成しましたが、適切に実行された場合、それはめちゃくちゃ高速であり、他に比べるものはありません。
試行に関するもう1つの問題は、カスタムヒープを作成する必要があることです。これは、ある種の汎用メモリ管理を使用するだけでは速度が低下するためです。したがって、トライを実装することに加えて、トライが実行されるヒープを実装する必要があります。かなり複雑ですが、それを行うと、クレイジーフォースピードになります。
ハッシュの適切な実装のみが、優れたパフォーマンスを提供します。また、すべての状況でハッシュとトライを比較することはできません。Trie が適用される状況は高速ですが、メモリの点でコストがかかる可能性があります (これも実装に依存します)。
しかし、パフォーマンスを測定しましたか? または、探しているのは不要な最適化です。マップは失敗しましたか？
これは、実際の要素数にも依存する場合があります。複雑性理論では、ハッシュは悪くありませんが、複雑性理論は、実際の要素数があるしきい値よりも大きい場合にのみ有効です。
つまり、要素が 2 つしかない場合は、ハッシュよりも高速な方法があります ;-)
ハッシュ テーブルは汎用目的の優れた構造ですが、ハッシュ関数が入力データに適合しない場合、見事に失敗する可能性があります。最悪の場合のルックアップは O(n) です。あなたが言ったように、彼らはまたいくらかのスペースを無駄にします。バランスの取れた二分探索木のような他の汎用構造は、ハッシュ テーブルよりも平均的なケースでは劣りますが、最悪のケースではパフォーマンスが向上します。これは、リアルタイム アプリケーションにとって重要です。トライは、文字列ルックアップに合わせた、より特殊な目的の構造です。