java - 破解 : Duplicates in java. util.TreeSet？

Question

我有一个简单的类

public class A {
    int val;
    public A(int val) {this.val = val;}
}

我将 A 实例存储在 java.util.TreeSet 中，例如:

SortedSet<A> ss = new TreeSet<A>(new Comparator<A>() {
    @Override
    public int compare(A o1, A o2) {
        return Integer.compare(o1.val, o2.val);
    }
});

后来才发现，具有相同val值的A实例不能在TreeSet中共存。

我需要 TreeSet 因为我想要:

• 快速插入
• 快速删除
• 快速查询具有最小val的元素

既然相等性完全取决于compare()的返回值0以及我们如何实现它，有没有一种hacking方式允许实例具有相同的val值> 共存于TreeSet？

我的解决方法是在 val 相等时返回一个稳定的非零值，但它被证明是不稳定的。

SortedSet<ListNode> ss = new TreeSet<ListNode>(new Comparator<ListNode>() {
    @Override
    public int compare(ListNode o1, ListNode o2) {
        if (o1.val != o2.val) return Integer.compare(o1.val, o2.val);
        return o1.hashCode() - o2.hashCode(); // not to return 0
    }
});

或者我应该切换到另一种数据结构？ (如果存在比R-B树更好的替代品)

而且，天哪，我知道 modeling the mathematical set abstraction很酷，这里的每个人都喜欢它。

结论:使用priority queue .

Answer 1

这就是我想说的...为什么不使用 Queue 尤其是文档中说的 PriorityQueue :

Implementation note: this implementation provides O(log(n)) time for the enqueuing and dequeuing methods: offer, poll, remove and add; linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods, peek, and size.

PriorityQueue 与 Tree 的区别还在于第一个更轻量级，因为它使用 binary heap 而不是红黑树;所以 PriorityQueue 将使用一个数组来存储它的数据，这并不难理解。

另请注意，如果您经常使用高优先级任务填充 PriorityQueue - 您的低优先级任务可能会等待很长时间才能被处理。