Hack: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 以及我们如何实现它，那么有没有一种黑客方式允许具有相同值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 树更好的替代品(

而且，哦，天哪，我知道对数学集合抽象进行建模很酷，这里的每个人都喜欢它。

结论：使用优先级队列。

Answer 1

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

： 实现

说明：此实现为排队和出列方法提供 O(log(n(( 时间：提供、轮询、删除和添加;删除(对象(和包含(对象(方法的线性时间;以及检索方法、速览和大小的恒定时间。

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

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

Answer 2

我想您希望不同的 A 实例在您的集合中共存，即使它们共享相同的值，并且不要多次添加相同的 A 实例。

A a = new A(1);
A b = new A(1);
A c = new A(2);
A d = c;
ss.add(a);
ss.add(b);
ss.add(c);
ss.add(d);

之后，您希望ss包含三个实例：两个 1 值和一个 2 值(因为 a 和 b 是不同的实例，c 和 d 包含相同的实例(。这就是你的代码将要做的(如果你不覆盖 Object 中的 hashCode(( 方法(。

只有一个改进：o1.hashCode() - o2.hashCode()可能会产生算术溢出，最好也为该部分使用Integer.compare()。 例如 2000000000 - (-2000000000( 将给出负结果，尽管第一个数字更大。这将导致所有基于比较器的结构行为异常。