compareto返回0时的java理解树集

Question

我创建了一个学生类，如下所示：

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
                + "]";
    }

}

这是我的测试类，我只是在树集中添加元素：

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]]

在我的测试类中，我正在向TreeSet添加Student对象，而且我还没有覆盖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

虽然这个问题已经很老了，但这里有一个非常重要的一点需要理解，大多数人在实现时忽略了这一点

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]

Answer 2

由于在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返回0时，treeSet假定其重复

Answer 3

你的树集键值是“A1”，“B1”，“A1”，“A2”。即使你不重写等号和哈希代码，但“A1”的默认哈希代码将是相同的，因此树集将把这个密钥视为重复密钥，这样你就不能进入“A1”、“B2”

Answer 4

这是因为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 5

正如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