algorithm - マルチセットまたはバッグは、キーの数を保持する単純なハッシュよりも時間計算量が優れていますか？

Question

Javaにはマルチセットがあり、SmallTalkにはBagクラスがあり、それらは同じ関数であると言われています。値のセットを保持しますが、複数の値を許可します（それぞれにカウントがあります）。

しかし、マルチセットは、キーのカウントを保持するハッシュテーブルによって実装できるようです（または他の可能な実装があるかもしれません）。

マルチセットまたはバッグの一部の実装は、上記のハッシュよりも時間計算量が優れていますか？必要な操作は

1. アイテムを挿入
2. アイテムを削除
3. セット内の最小値を取得します
4. セット内の最大値を取得します

特に、上記の4つの操作のそれぞれについて、それがより良くO(n)、おそらくすべてO(log n)またはより良く行われることを望んでいます。O(log n)（上記の3と4は、値が追加または削除されるたびにマルチセットが何らかのソートされた方法で維持される場合にのみ発生すると予想されます。）

Answer 1

Multiset が hastable または sorted set によって実装されているかどうかによって異なります。

ハッシュテーブルの場合、挿入/更新操作は O(1) (最小値と最大値は O(n)) ですが、ハッシュテーブルでは要素が順番に保持されないという欠点があります。さらに、これには、格納される各要素に対して、一貫したハッシュ値を計算できることが必要です。

ソートされたセットの場合、すべての操作は O(log n) ですが、要素がソートされた順序で保持されるという利点があります (したがって、要素の範囲を報告するのに効率的です)。これには、格納される各要素が比較可能であることが必要です (つまり、要素に順序が存在します)。