Java中的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);
    }
});

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

我需要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树更好的替代品）

哦天啊，我知道建模数学集合抽象很酷，这里的每个人都喜欢它。

结论：使用优先队列。

- SedriX

---

@Anon，我刚刚误解了问题。将相同的值放入集合中是不可能的。因为它是一个集合。集合只包含不同的值。也许Guava中的Multiset可以帮助解决问题。 - dehasi

@dehasi请查看java.util.TreeMap源代码中的final Entry<K,V> getEntry(Object key)方法...我相信在Map和Set实现方面，equals和hashCode只对HashMap和HashSet至关重要。 - SedriX

如果你需要查询最小值，你需要使用堆而不是集合，可以尝试使用MinMaxPriorityQueue。@CedricSun - dehasi

@dehasi 哦，堆内存... 我想我完全忘了它... 那将是我的问题的答案，谢谢你的提示！ - SedriX

@CedricSun 不用谢 :) - dehasi

Answer 1

这就是我想说的......为什么不使用一个队列，特别是文档中建议使用的优先队列（PriorityQueue）：

实现注释：此实现提供了O(log(n))时间的入队和出队方法：offer、poll、remove和add；线性时间的remove(Object)和contains(Object)方法；以及检索方法peek和size的常数时间。

与Tree相比，PriorityQueue的区别在于它更轻量级，因为它使用二叉堆而不是红黑树；所以PriorityQueue将使用一个数组来存储它的数据，这并不难理解。

还要注意，如果你经常用高优先级任务填充你的PriorityQueue，那么低优先级任务可能会等待很长时间才能被处理。

- Eugene

---

是的...我已经很久没有练习关于数据结构和算法的题目了，而且这还是我第一次使用Java。实际上，我正在解决这个问题。希望这篇文章能帮助到有同样困惑的人 :) - SedriX

Answer 2

我想你希望不同的A实例即使它们共享相同的val也能在你的集合中共存，并且不会重复添加相同的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）将给出负结果，尽管第一个数字更大。这将导致所有基于Comparator的结构表现奇怪。

- Ralf Kleberhoff

---

溢出并不是OP方法的唯一问题 - 如果集合的大小足够大，插入和删除的性能也会受到哈希冲突的影响。 - Hulk

@ Hulk：你说得对。有一个方面，我的32位Java经验在64位Java中已经不再有效了 :-(。在32位Java中，标准JRE的Object.hashCode()返回内部地址（“这通常是通过将对象的内部地址转换为整数来实现的[...]”），因此，Object.hashCode()永远不会发生冲突，因为地址和整数具有相同的大小。但是，由于64位地址和32位整数，这已经不再可能，即使Object.hashCode()也可能会产生冲突。 - Ralf Kleberhoff