私はこの良い質問に出くわしました。これは似ていますが、同期されたアクセサー/ミューテーターを持つことにより、ハッシュテーブルの実装が異なる Java について話しているため、まったく同じではありません: HashMap と Hashtable の違いは何ですか?ジャワ？
setでは、との C++ 実装の違いは何unordered_setですか? もちろん、この質問は他の C++ コンテナーのmapvsなどにも拡張できます。unordered_map
これが私の最初の評価です。
set: 標準では、ツリーとして実装することを明示的に要求していませんが、時間の複雑さの制約により、検索/挿入の操作が要求され、常にツリーとして実装されることを意味します。通常、高さのバランスが取れた RB ツリー (GCC 4.8 で見られる) として。高さのバランスが取れているため、予測可能な時間の複雑さがあります。find()
長所：コンパクト（他のDSとの比較で）
短所: アクセス時間の複雑さは O(lg n) です
unordered_set: 標準では、ツリーとして実装することを明示的に要求していませんが、時間の複雑さの制約により、検索/挿入の操作が要求され、常にハッシュ テーブルとして実装されることを意味します。
長所：
- 高速 (検索用に償却 O(1) を約束)
- tree-DS と比較して、基本的なプリミティブをスレッドセーフに変換するのは簡単
短所：
- O(1) であるとは限りません。理論上の最悪のケースは O(n) です。
- ツリーほどコンパクトではありません (実用的な目的のため、負荷係数は決して 1 にはなりません)。
注: ハッシュテーブルの O(1) は、衝突がないという仮定に基づいています。負荷係数が .5 の場合でも、1 秒おきに変数を挿入すると衝突が発生します。ハッシュテーブルの負荷係数は、その中の要素にアクセスするために必要な操作の数に反比例することがわかります。さらに#操作を減らし、ハッシュテーブルをより疎にします。格納された要素のサイズがポインターに匹敵する場合、オーバーヘッドは非常に大きくなります。
知っておくべきパフォーマンス分析用のマップ/セットの違いを見落としていませんか?