セットとハッシュマップに一定の検索時間がありませんか？

Question

は私が試みについて読んでいたし、このトップコーダーの記事（https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/）は言う：

試みが挿入し、（Lは、単一の単語の長さを表す）O（L）時間内の文字列を見つけることができます。これは設定よりはるかに高速ですが、ハッシュテーブルよりも少し速いです。

私はいつもセットとハッシュテーブルが本当に素早く検索していて、ルックアップ時間が一定であることを知っていました。これは本当ですか？なぜそれはセットよりもずっと速いのですか？また、ハッシュテーブルにはセットとは異なるルックアップ時間があることを暗示しているようです。私はいつも、セットとハッシュテーブルは、あるオブジェクトを格納することを除いてほぼ同じ方法で実装されていると考えました。

Answer 1

参照された記事は、トライと抽象的な「セット」データ構造とを比較していません。トライとC++標準ライブラリstd::setを比較しています。これは検索ツリーで、通常は赤黒のツリーで、内容をソート順に反復することができます。 （C++にはstd::unordered_setもありますが、これはハッシュテーブルに基づいていますが、その前に標準ライブラリの一部であったかもしれません）。

ハッシュテーブルは（平均して）O任意のルックアップが行われる前にキーのハッシュを計算しなければならないため、O（1）で計算できます。文字列キーの場合、ほとんどのハッシュ関数はキー内のすべての文字を調べる必要があるため、文字列の長さはO（L）です。 （この明らかな事実は何らかの理由でハッシュテーブルの計算上の複雑さを議論する際にスキップされることが多い）。トライとハッシュテーブルの両方が、提供されたキーがコンテナ内の候補キーと等しいことを最終的に検証する必要があるので、 ）要因の両方の場合に要因。

しかし、試行にはまだ利点があります。例えば、それらは、std::setのような辞書順で反復することができるが、通常は高速であるのに対し、ハッシュテーブルはいくつかの非決定的な順序でしか反復することができない。したがって、プレフィックス検索を行う必要がある場合、ハッシュテーブルは適切なデータ構造ではありません。