Java TreeSet<int[]>：重复元素？

Question

我希望在TreeSet中拥有一些int对，并按照第一个数字排序。

代码测试请见此链接：

public static void main (String[] args) throws java.lang.Exception
{
    SortedSet<int[]> s = new TreeSet<int[]>(new Comparator<int[]>(){
        public int compare(int[] a, int[] b) {
            return b[0] - a[0];
        }
    });
    int[] a = new int[]{1, 2};
    int[] b = new int[]{1, 3};
    s.add(a);
    s.add(b);
    System.out.println(s.size());
}

我不知道为什么TreeSet的大小会变成1。看起来a和b的hashCode相同，但为什么呢？

感谢任何帮助。

顺便说一下：实际上，我试图将重复的数字放入一个集合中，这是不可能的。然后我尝试在一个集合中放置int对。第一个数字是我想要的实际数字，第二个数字是为了防止重复出现。但我遇到了这个问题。

- Meng Wang

---

兄弟，你在做这个 return b[0] - a[0]; 的时候，你在想什么啊？ - Nir Alfasi

基于树的映射只使用 Comparable 或 Comparator 的 compareTo 和 compare 方法。在树数据结构中，哈希码没有任何相关性。 - Kumar Abhinav

@Meng Wang，请查看我在答案中包含的Javadocs。 - Kumar Abhinav

我看到了。谢谢！@KumarAbhinav - Meng Wang

@alfasin，我在“顺便说一下”部分解释了我想做什么。这就是为什么我使用b[0] - a[0]作为compare()的结果。现在我知道这是不可行的。谢谢！ - Meng Wang

将重复的数字放入一个集合中不仅是“不可能的” - 这违背了集合的目的。看起来像是 XY 问题 的另一种表现。 - Nir Alfasi

Answer 1

结果是1，因为您的compare方法只使用数组中的第一个数字，而您拥有的两个数组都以1开头。因此，从TreeSet的角度来看，这两个数组是相同的。TreeSet.add返回

如果此集合先前未包含指定元素，则为true

由于两个值被认为是相等的（compare返回0），因此不会添加第二个值，并且add()返回false

- Paul Boddington

---

可能需要指出的是，TreeSet.add() 返回“如果此集合先前未包含指定元素，则为true”，并且由于这两个值被视为相等（compare返回0），因此不会添加第二个值，而add()将返回false。 - Andreas

@Andreas 很好的想法。如果我直接复制粘贴你的话，你会反对吗？ - Paul Boddington

完整的答案：Set 的定义是“一个不包含重复元素的集合”。如果你不想消除重复项，就不要使用 Set。你可以选择一个有序的“Bag”，在 Java 中指的是一个 PriorityQueue。 - Andreas

谢谢！现在我知道TreeSet使用compare方法而不是hashCode()来判断元素的相等性。还要感谢您对PriorityQueue的建议。非常感谢您的帮助。 - Meng Wang

@MengWang 并非所有的Set都是如此。 HashSet使用了hashCode()和equals()方法。你需要在使用任何类之前仔细阅读其文档。 - Paul Boddington

Answer 2

这是一个常见的错误，认为哈希码在基于树的数据结构中起到作用，实际上并不是这样。基于哈希的集合(HashSet,LinkedHashSet,HashMap,LinkedHashMap 和其他几个)使用哈希和equals来区分对象。

在您的情况下，TreeSet使用比较器来处理对象相等性，该比较器根据数组大小的长度进行相等性判断。如果两个数组具有相同的大小，则被视为相等。因此，在您的情况下，数组b替换了数组a成为头节点，因为两个数组的长度都为1。即使您覆盖hashcode，也没有任何用处。

从JavaDocs中可以看到：

请注意，集合维护的排序(无论是否提供了显式的比较器)必须与equals一致，如果它要正确地实现Set接口。(有关一致与equals的精确定义，请参见Comparable或Comparator。)这是因为Set接口是根据equals操作定义的，但TreeSet实例使用其compareTo(或compare)方法执行所有元素比较，因此通过该方法被视为相等的两个元素从集合的角度来看是相等的。即使其排序与equals不一致，集合的行为也是明确无误的；它只是未遵守Set接口的通用契约。

- Kumar Abhinav

---

谢谢！现在我知道Set/Map使用compare()而不是hashCode()来判断元素/键的相等性。感谢您的帮助。 - Meng Wang