multiset或bag提供的時間複雜度是否比保持密鑰計數的簡單哈希好？

Question

Java有multiset，SmallTalk有一個Bag類，它們被認爲是相同的函數：保留一組值，但允許多個值（每個值都有一個值）。

但似乎multiset可以通過一個哈希表來實現，該哈希表可以對鍵進行計數（或者可能還有其他可能的實現）。

做一些multisets或bag的實現提供比上面的散列更好的時間複雜性嗎？所需的操作可能是

1. 插入項目
2. 刪除項
3. 得到一組
4. 在集合

尤其得到最大值最小值，我希望對於上述4個操作中的每一個，都可以比O(n)更好，可能全部是O(log n)或更好。 （只有在多個數據集按照某種排序的方式維護時，上面的3和4預期爲O(log n)）

Answer 1

這取決於Multiset是由hastable還是有序集合實現的。插入/更新操作是O（1）（最小和最大是O（n）），但不利之處在於散列表不保留元素的順序。此外，這要求對於要存儲的每個元素，可以計算一致的散列值。

對於一個有序集合，所有的操作都是O（log n），但有利的是元素保持排序順序（因此，報告元素範圍是有效的）。這要求每個要存儲的元素是可比的（即存在於元素上的排序）。