[解決済み] ハッシュテーブルとトライ（プレフィックスツリー）のどちらを選べばいいですか？

質問

ハッシュテーブルとプレフィックスツリーのどちらかを選ばなければならない場合、どちらを選ぶべきかの判断材料は何でしょうか。私の素朴な考えでは、トライを使うと配列として保存されないので余計なオーバーヘッドがあるように思えますが、実行時間（最長キーが最長英単語と仮定した場合）については（上限との関係で）本質的に O(1) で済むと思われます。たぶん、最長の英単語は50文字くらい？

ハッシュテーブルは瞬時にルックアップできる インデックスを取得すれば . しかし、キーをハッシュ化してインデックスを取得するのは、50ステップ近くかかると思われます。

どなたか、もっと経験豊富な方の見解をお聞かせください。ありがとうございます。

どのように解決するのですか？

トライのメリット

基本中の基本です。

• 予測可能なO(k)のルックアップ時間（kはキーのサイズ）。
• ルックアップは、それがない場合はk時間未満で可能
• 順序付きトラバーサルをサポート
• ハッシュ関数が不要
• 削除が簡単

新しい操作方法です。

• キーの接頭辞を素早く調べたり、指定した接頭辞を持つすべてのエントリーを列挙したりすることができます。

リンク構造のメリット

• 共通の接頭辞が多数ある場合、それらが必要とするスペースを共有することができる。
• Immutableトライは構造を共有することができます。トライをその場で更新する代わりに、1つのブランチに沿ってのみ異なる新しいトライを構築し、他の場所では古いトライを指すようにすることができます。これは、並行処理や複数バージョンのテーブルを同時に使用する場合などに便利です。
• 不変の三角形は圧縮可能です。つまり サフィックス もハッシュコンシングすることで実現する。

ハッシュテーブルのメリット

• ハッシュテーブルってみんな知ってるよね？あなたのシステムにはすでに最適化された実装があり、ほとんどの用途でtriesより高速に動作します。
• キーは特別な構造を持つ必要はありません。
• 明らかなリンクトライ構造よりもスペース効率が良い( 下記のコメント参照 )