TreeSet(有序集合)对Comparable元素的排序（或使用Comparator）与元素equals方法的关系

转

这是一个非常基础的问题，但是实际编程中还是比较容易被忽视而导致一些看似奇怪的bug，本文对该问题进行一个小结。

我们知道，Set集合的维护的元素是唯一的，不会出现两个一样的元素，这是通过元素的equals和hashCode方法来判定的。而对于TreeSet来说，它本身除了是一个Set集合，同时还会依据一个Comparator或是Comparable接口对元素进行排序。我们就以Comparable的compareTo方法为例，当这个方法返回0是表示的也是“两个元素相等”，那么这就有可能与equals方法产生冲突，那么TreeSet是如何处理compareTo和equals方法两者之间的关系呢？

先不管两者发生冲突时的处理方法，作为良好的编程实践，我们应该首先保证equals，hashCode和compareTo三者的行为是一致的，这样才不会出现怪异的问题。接下来我们看一下当equals和compareTo行为不一致时TreeSet是如何处理的。从TreeSet文档上我们可以找到以下一段描述：

假定使用 Comparator c 将满足 (a.equals(b) && c.compare(a, b) != 0) 的两个元素 a 和 b 添加到一个空 TreeSet 中，则第二个 add 操作将返回 true（树 set 的大小将会增加），因为从树 set 的角度来看，a 和 b 是不相等的，即使这与 Set.add 方法的规范相反。

在Comparable的文档上我们可以找到另一种描述：

如果将两个键 a 和 b 添加到没有使用显式比较器的有序集合中，使 (!a.equals(b) && a.compareTo(b) == 0)，那么第二个 add 操作将返回 false（有序集合的大小没有增加），因为从有序集合的角度来看，a 和 b 是相等的。

很明确，两段说明从一正一反两个方向描述了一个一致的原则：是否能加入一个有序集合是由equals方法决定的，但是equals为true，compare不为0的元素加入到集合中后，在排序上会显得怪异。

让我们有一段程序来验证这个问题：

import java.util.PriorityQueue;
import java.util.TreeSet;

public class Test2 {
    public static void main(String[] args) {
        TreeSet<Obj> s1 = new TreeSet<Obj>();
        s1.add(new Obj(1, 1));
        s1.add(new Obj(1, 2));
        for (Obj obj : s1) {
            System.out.println(obj);
        }
        System.out.println("--------------------------");
        TreeSet<Obj> s2 = new TreeSet<Obj>();
        s2.add(new Obj(1, 1));
        s2.add(new Obj(2, 1));
        for (Obj obj : s2) {
            System.out.println(obj);
        }
    }
    public static class Obj implements Comparable<Obj> {
        int a;
        int b;
        public Obj(int a, int b) {
            this.a = a;
            this.b = b;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Obj obj = (Obj) o;

            if (a != obj.a) return false;

            return true;
        }

        @Override
        public int hashCode() {
            return a;
        }

        @Override
        public String toString() {
            return "Obj{" +
                    "a=" + a +
                    ", b=" + b +
                    '}';
        }
        @Override
        public int compareTo(Obj o) {
            return b - o.getB();
        }
        public int getA() {
            return a;
        }
        public void setA(int a) {
            this.a = a;
        }
        public int getB() {
            return b;
        }
        public void setB(int b) {
            this.b = b;
        }
    }
}

Obj{a=1, b=1}
Obj{a=1, b=2}
--------------------------
Obj{a=1, b=1}

不用再多说明，s1印证了第一段描述，s2印证了第二段描述。