performance - 高速な辞書検索に最適なデータ構造は何ですか?

Question

私の知る限り、ハッシュ テーブルと double 配列の試行は、辞書を検索するための最速のデータ構造の 2 つです。それらを打ち負かすことができる他のデータ構造またはアルゴリズムはありますか?

Answer 1

ハッシュテーブルは、必ずしも高速検索のデータ構造である必要はありません。それは本当にあなたのハッシュ関数がどれだけ優れているかに依存します。ハッシュ関数があまり良くない場合は、複数のキーを解決して同様のインデックスにマップし、衝突を引き起こして、ハッシュテーブルをO（n）実行時に縮退させる可能性があります。

自己平衡ツリーは、O（log n）を保証するだけでなく、高速なデータ構造であると見なされます。