したがって、ハッシュテーブルまたはプレフィックスツリーのどちらかを選択する必要がある場合、どちらかを選択するように導く識別要因は何ですか. 私自身の素朴な観点からは、トライを使用すると、配列として保存されないため、余分なオーバーヘッドがあるように見えますが、実行時間の観点からは（最長のキーが最長の英単語であると仮定して）、本質的に O になる可能性があります(1) (上限に関して)。たぶん、最も長い英単語は50文字ですか？
ハッシュ テーブルは、インデックスを取得するとすぐに検索されます。ただし、インデックスを取得するためにキーをハッシュすると、50 近くの手順を簡単に実行できるように思えます。
誰かがこれについてより経験豊富な視点を提供できますか? ありがとう！
試行の利点:
基礎：
新しい操作:
リンク構造の利点:
ハッシュテーブルの利点:
それはすべて、解決しようとしている問題によって異なります。挿入と検索だけが必要な場合は、ハッシュ テーブルを使用します。接頭辞関連のクエリなど、より複雑な問題を解決する必要がある場合は、トライの方が適している可能性があります。
ツリーを使用する：
心に留めておくことが重要だと思うことを、誰も明示的に言及していないのを見たことがあります。通常、さまざまな種類のハッシュ テーブルと試行の両方にO(k)操作がありkます。
これは、適切なハッシュ関数があることを前提としています。「農場」と「農場の動物」を同じ値にハッシュしたくない場合、ハッシュ関数はキーのすべてのビットを使用する必要があるため、「農場の動物」のハッシュには約 2 倍の時間がかかります。 「ファーム」（何らかのローリング ハッシュ シナリオを使用している場合を除きますが、試行を伴う操作を節約する類似のシナリオもあります）。そして、バニラ トライでは、「農場の動物」を挿入すると、「農場」だけの場合の約 2 倍の時間がかかる理由は明らかです。長い目で見れば、圧縮された試行でも同様です。
一部の (通常は組み込みのリアルタイム) アプリケーションでは、処理時間がデータとは無関係である必要があります。その場合、ハッシュ テーブルは既知の実行時間を保証できますが、トライはデータに基づいて変化します。