スタック操作のカップル（ポップ+プッシュ）とハッシュテーブルの代替との比較

Question

私はプロセスがあり、それはstackと定義されています。今すぐアイテムをstackにプッシュしている間、同じ/類似のアイテムが既に存在するかどうかを確認する必要があります。そうでない場合は、新しい項目を押します。 これは

を押された項目として その同じ次に、最新を押した場合に比較し、類似のタイプのアイテムをポップ2つのスタック操作

1. を含みます。

私の質問は、それに値する費用ですか、この決定を簡単にするためにスタックエントリのハッシュテーブルを維持する必要がありますか？ それ以外の場合は、スタック操作のコストはいくらですか？

LINUXのようなフラットなメモリモデルでもう1つ、必要に応じて事前割り当てスタックサイズを増やすことは間違いでしょうか（reallocなど）？

Answer 1

明らかに、スタックオプションは不要な処理に多くの無駄な時間を費やしているので、有料です。ハッシュテーブルは何かを検索する最速の方法であるため、ハッシュベースのアプローチが優れています（ここでは、メモリに追加する予定の新しいレコードに似たレコードになります）。ハッシュは、最適なパフォーマンスを提供するためにハッシュテーブルを使用する人々を設計するオペレーティングシステムにおいてさえ、常に最良の方法です。