比较 returns 0 时了解 TreeSet

Question

我创建了一个这样的学生 class：

public class Student implements Comparable<Student> {

    private String firstName;
    private String lastName;

    public Student(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }

    // Getters & Setters follow here...

    @Override
    public int compareTo(Student student) {
        int hash = this.firstName.compareTo(student.firstName);
        return hash;
    }

    @Override
    public String toString() {
        return "Student [firstName=" + firstName + ", lastName=" + lastName
                + "]";
    }

}

这是我的测试 class，我只是将元素添加到我的 TreeSet 中：

public class SortedSetExample1 {
    public static void main(String[] args) {
        SortedSet<Student> set = new TreeSet<Student>();
        set.add(new Student("A1","A2"));
        set.add(new Student("B1","B2"));
        set.add(new Student("A1","B2"));
        set.add(new Student("A2","B2"));
        System.out.println(set);
    }
}

根据我的程序，输出是：

[Student [firstName=A1, lastName=A2], Student [firstName=A2, lastName=B2], Student [firstName=B1, lastName=B2]]

在我的测试 class 中，我将 Student 个对象添加到 TreeSet，而且我没有覆盖 hashCode 和 equals 方法。所以我期待 TreeSet 将包含所有 4 个对象，但我也可以看到它包含 3 个对象。你能解释一下为什么 new Student("A1","B2") 不是我的 TreeSet 的一部分吗？

此外，根据此处的 Java docs for TreeSet，它表示：

Adds the specified element to this set if it is not already present. More formally, adds the specified element e to this set if the set contains no element e2 such that (e==null ? e2==null : e.equals(e2)). If this set already contains the element, the call leaves the set unchanged and returns false.

因为我没有覆盖 equals 方法，那么为什么集合没有包含所有四个元素？

Answer 1

正如java.util.TreeSet所说：

a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal

感谢@Jon Skeet。

Answer 2

那么，您的树集键值是 "A1"、"B1"、"A1"、"A2"。即使您没有覆盖 equals 和哈希码，"A1" 的默认哈希码仍然相同，因此树集会将此键视为重复键，因此您将无法输入 "A1"、"B2"

Answer 3

那是因为TreeSet使用compareTo（或Comparator.compare）来测试两个元素是否相等。这就是文档所说的。

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

Answer 4

由于您在 compareTo 方法中只比较了名字，因此您需要

 @Override
public int compareTo(Student student) {
    int comp = this.firstName.compareTo(student.firstName);
    if(comp==0) return this.lastName.compareTo(student.lastName);
    return comp;
}

当 compareTo returns 0 时，treeSet 假定它是重复的。

Answer 5

虽然问题很老，但这是一个非常重要的理解点，大多数人在实施时都忽略了这一点。

TreeSet 不会将新元素与 Set 中的所有现有元素进行比较。它使用二进制搜索技术。因此，如果您的输入元素等于现有元素（根据 compareTo 合同）并且相同位于 tree 的左侧，并且您的 compareTo 方法是这样实现的强制您的新元素位于 tree 的右侧，您的 TreeSet 不会拒绝新元素，即使其中已经存在相同的元素（根据 compareTo 合同）。让我们看下面的简单例子。

我需要对具有 key 和 priority 属性的 Item 进行排序。

package com.manish;
import java.util.TreeSet;
public class Main {
    static class Item implements Comparable<Item> {
        private long key;
        private int priority;
        public Item(long key, int priority) {
            super();
            this.key = key;
            this.priority = priority;
        }

        /*
         * Items should be treated equal if Keys are equal.
         * Higher priority item should be treated as greater item.
         * If priorities are same, lower key value item should be
         * treated as greater item.
         */
        @Override
        public int compareTo(Item o) {
            if (this.key == o.key) {
                return 0;
            }
            if (this.priority != o.priority) {
                return this.priority - o.priority;
            } else {
                return this.key < o.key ? 1 : -1;
            }
        }
        @Override
        public String toString() {
            return "Item [key=" + key + ", priority=" + priority + "]";
        }
    }
    public static void main(String[] args) {
        TreeSet<Item> set = new TreeSet<>();
        set.add(new Item(2, 1));
        set.add(new Item(4, 3));
        set.add(new Item(3, 1)); //line 1
        set.add(new Item(3, 2)); //line 2. Same item as Item(3,1)
        while (!set.isEmpty())
            System.out.println(set.pollFirst());
    }
}

输出：

Item [key=3, priority=1]
Item [key=2, priority=1]
Item [key=3, priority=2]
Item [key=4, priority=3]

但是，如果交换 line 1 和 line 2 代码，输出将发生如下变化。

Item [key=2, priority=1]
Item [key=3, priority=2]
Item [key=4, priority=3]

比较 returns 0 时了解 TreeSet

Understanding TreeSet when compareto returns 0

java

collections

compareto

sortedset

treeset