algorithm - 多重集或袋子是否比保持键计数的简单哈希提供更好的时间复杂度？

Question

Java 有 multiset，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)，但好处是元素保持有序（因此，它在报告元素范围方面很有效）。这要求要存储的每个元素都是可比较的（即元素上存在排序）。