別のデータ構造の要素を追跡するためのハッシュマップを持つ

Question

時々、キュー、スタック、ヒープなどのO（N）時間の複雑さを持つ特定の機能を持つ特定のdsがあります。ある要素がこれらのdsの1つに含まれているかどうかをチェックするだけのプログラムでこれらのdsの1つですが、O（N）の複雑さがあるので、それは私のアルゴリズムの落とし穴です。

メモリが私の心配ではない場合、制限されたデータ構造内の要素を追跡するハッシュマップを持つことは貧弱な設計ですか？これを行うと、基本的にO（N）制限が削除され、O（1）になることが許可されます。

Answer 1

多くの場合、補足ハッシュテーブルが必要です。しかし、 "パラレルハッシュ"を維持することは負担になりかねません。

メンバーシップをすばやく確認する必要がある場合は、ハッシュベースのセット（言語によってはHashSet<T>、std::unordered_set<T>など）でモデル化することがよくあります。これらの構造の欠点は、要素の順序が指定されておらず、重複を持つことができないことです。

ライブラリによっては、これらの欠点を修正するデータ構造にアクセスすることができます。例えば、JavaはLinkedHashSet<T>を提供し、列挙の順序は予測可能で、C++はstd::unordered_multiset<T>を提供し、複製を許可します。