Trail: Collections
Lesson: Interfaces

对象排序

可以如下对 List l 进行排序。

Collections.sort(l);

如果 List 由 String 元素组成，它将按字母顺序排序。如果它由 Date 元素组成，它将按时间顺序排序。这是怎么发生的？String 和 Date 都实现 Comparable 接口。Comparable 实现为类提供 natural ordering (自然排序)，允许自动对该类的对象进行排序。following table 总结了一些实现 Comparable 的更重要的 Java 平台类。

**实现 Comparable 的类**
Class	自然排序
`Byte`	有符号数字
`Character`	无符号数字
`Long`	有符号数字
`Integer`	有符号数字
`Short`	有符号数字
`Double`	有符号数字
`Float`	有符号数字
`BigInteger`	有符号数字
`BigDecimal`	有符号数字
`Boolean`	`Boolean.FALSE < Boolean.TRUE`
`File`	路径名称上依赖于系统的词典
`String`	词典顺序
`Date`	时间顺序
`CollationKey`	特定于语言环境的词典

如果你尝试对列表进行排序，其中的元素未实现 Comparable，Collections.sort(list) 将抛出 ClassCastException。类似地，如果你尝试使用 comparator 对其元素无法相互比较的列表进行排序，Collections.sort(list, comparator) 将抛出 ClassCastException。可以相互比较的元素被称为 mutually comparable (相互比较)。虽然不同类型的元素可以相互比较，但这里没有列出允许进行类之间比较的类。

如果你只想对可比较元素的列表进行排序或创建它们的有序集合，那么你真正需要了解 Comparable 接口。如果要实现自己的 Comparable 类型，下一部分将是你感兴趣的。

编写自己的可比类型

Comparable 接口包含以下方法。

public interface Comparable<T> {
    public int compareTo(T o);
}

compareTo 方法将接收对象与指定对象进行比较，并返回负整数 0 或正整数，具体取决于接收对象是否小于，等于或大于指定对象。如果无法将指定的对象与接收对象进行比较，则该方法将抛出 ClassCastException。

下面的类表示一个人的姓名 ，该类实现 Comparable。

import java.util.*;

public class Name implements Comparable<Name> {
    private final String firstName, lastName;

    public Name(String firstName, String lastName) {
        if (firstName == null || lastName == null)
            throw new NullPointerException();
        this.firstName = firstName;
        this.lastName = lastName;
    }

    public String firstName() { return firstName; }
    public String lastName()  { return lastName;  }

    public boolean equals(Object o) {
        if (!(o instanceof Name))
            return false;
        Name n = (Name) o;
        return n.firstName.equals(firstName) && n.lastName.equals(lastName);
    }

    public int hashCode() {
        return 31*firstName.hashCode() + lastName.hashCode();
    }

    public String toString() {
	return firstName + " " + lastName;
    }

    public int compareTo(Name n) {
        int lastCmp = lastName.compareTo(n.lastName);
        return (lastCmp != 0 ? lastCmp : firstName.compareTo(n.firstName));
    }
}

为了保持前面的例子简短，这个类有点受限：它不支持中间名，它既需要名字也要求姓，并且不以任何方式国际化。尽管如此，它还说明了以下要点：

Name 对象是 immutable (不可变)。在所有其他条件相同的情况下，不可变类型是可行的方法，特别是对于将用作 Set 中的元素或 Map 中的键的对象。如果你在集合中修改元素或键，这些集合将会中断。
构造函数检查 null 的参数。这可以确保所有 Name 对象格式正确，这样其他任何方法都不会抛出 NullPointerException。
重新定义 hashCode 方法。这对于重新定义 equals 方法的任何类都是必不可少的。(相等的对象必须具有相等的哈希码。)
如果指定的对象是 null 或类型不合适，equals 方法将返回 false。在这些情况下，compareTo 方法会抛出运行时异常。这些行为都是各方法的一般合同所要求的。
toString 方法已重新定义，因此它以人类可读的形式打印 Name。这总是一个好主意，特别是对于要放入集合的对象。各种集合类型的 toString 方法依赖于其元素，键和值的 toString 方法。

由于本节涉及元素排序，让我们再谈谈 Name 的 compareTo 方法。它实现了标准的名称排序算法，其中姓氏优先于名字。这正是你想要的自然顺序。如果自然顺序不自然，那将会非常混乱！

看看如何实现 compareTo，因为它非常典型。首先，比较对象的最重要部分(在本例中为姓氏)。通常，你可以使用零件类型的自然顺序。在这种情况下，该部分是 String，自然(词典)排序正是所要求的。如果比较结果不是表示相等的零，那么你就完成了：你只需返回结果。如果最重要的部分相同，则继续比较下一个最重要的部分。在这种情况下，只有两个部分名字和姓氏。如果有更多的零件，你会以明显的方式进行，比较零件，直到你发现两个不相等或你正在比较最不重要的零件，此时你将返回比较的结果。

只是为了表明一切正常，这里是 一个构建名称列表并对其排序的程序。

import java.util.*;

public class NameSort {
    public static void main(String[] args) {
        Name nameArray[] = {
            new Name("John", "Smith"),
            new Name("Karl", "Ng"),
            new Name("Jeff", "Smith"),
            new Name("Tom", "Rich")
        };

        List<Name> names = Arrays.asList(nameArray);
        Collections.sort(names);
        System.out.println(names);
    }
}

如果你运行这个程序，这是它打印的内容。

[Karl Ng, Tom Rich, Jeff Smith, John Smith]

compareTo 方法的行为有四个限制，我们现在不会讨论它们，因为它们技术性很差，很无聊，最好留在 API 文档中。实现 Comparable 的所有类都遵守这些限制非常重要，因此如果你正在编写实现它的类，请阅读 Comparable 的文档。尝试对违反限制的对象列表进行排序具有未定义的行为。从技术上讲，这些限制确保了自然排序是实现它的类的对象的 total order (总顺序);这对于确保明确定义排序是必要的。

比较器

如果你想按照一些对象的自然顺序以外的顺序对它们排序呢？或者，如果要对某些未实现 Comparable 的对象进行排序，该怎么办？要做这些事情中的任何一个，你需要提供一个 Comparator 封装排序的对象。与 Comparable 接口类似，Comparator 接口由单个方法组成。

public interface Comparator<T> {
    int compare(T o1, T o2);
}

compare 方法比较其两个参数，返回负整数，0 或正整数，具体取决于第一个参数是小于，等于还是大于第二个参数。如果任一参数的 Comparator 类型不合适，compare 方法将抛出 ClassCastException。

关于 Comparable 的大部分内容也适用于 Comparator。编写 compare 方法与编写 compareTo 方法几乎相同，只是前者将两个对象作为参数传入。由于同样的原因，compare 方法必须遵守与 Comparable 的 compareTo 方法相同的四个技术限制 Comparator 必须对它所比较的对象产生总排序。

假设你有一个名为 Employee 的类，如下所示。

public class Employee implements Comparable<Employee> {
    public Name name()     { ... }
    public int number()    { ... }
    public Date hireDate() { ... }
       ...
}

假设 Employee 实例的自然顺序是员工姓名上的 Name 排序(如上例所定义)。不幸的是，老板要求按照资历顺序列出员工名单。这意味着我们必须做一些工作，但并不多。以下程序将生成所需的列表。

import java.util.*;
public class EmpSort {
    static final Comparator<Employee> SENIORITY_ORDER = 
                                        new Comparator<Employee>() {
            public int compare(Employee e1, Employee e2) {
                return e2.hireDate().compareTo(e1.hireDate());
            }
    };

    // Employee database
    static final Collection<Employee> employees = ... ;

    public static void main(String[] args) {
        List<Employee> e = new ArrayList<Employee>(employees);
        Collections.sort(e, SENIORITY_ORDER);
        System.out.println(e);
    }
}

程序中的 Comparator 相当简单。它依赖于应用于 hireDate 访问器方法返回的值的 Date 的自然顺序。请注意，Comparator 将其第二个参数的雇用日期传递给第一个参数，而不是相反。原因是最近雇用的员工是最不高级的；按雇用日期顺序排序会使列表按反向资历顺序排列。人们有时用来实现这种效果的另一种技术是维持参数顺序但是否定比较的结果。

// Don't do this!!
return -r1.hireDate().compareTo(r2.hireDate());

你应该总是使用前一种技术来支持后者，因为后者不能保证工作。原因是 compareTo 方法可以返回任何负 int，如果它的参数小于调用它的对象。有一个负的 int 在被否定时仍然是负的，看起来很奇怪。

-Integer.MIN_VALUE == Integer.MIN_VALUE

前面程序中的 Comparator 可以很好地排序 List，但它有一个缺陷：它不能用于排序已排序的集合，例如 TreeSet，因为它生成的排序是与 equals 不兼容的。这意味着此 Comparator 认为对象相等但 equals 方法却不。特别是，在同一天雇佣的任何两名员工将相同。当你对 List 进行排序时，这无关紧要；但是当你使用 Comparator 排序一个有序的集合时，它是致命的。如果你使用此 Comparator 将在同一日期雇用的多名员工插入 TreeSet，则只会将第一个员工添加到该集合中；第二个将被视为重复元素，将被忽略。

要解决此问题，只需调整 Comparator，使其生成 兼容于 equals 的排序。换句话说，调整它以便在使用 compare 时看到相同的唯一元素是那些在使用 equals 进行比较时也被视为相等的元素。执行此操作的方法是执行两部分比较(对于 Name)，其中第一部分是我们感兴趣的部分在这种情况下，雇用日期第二部分是唯一标识对象的属性。员工编号在这里是明显的属性。这是 Comparator 的结果。

static final Comparator<Employee> SENIORITY_ORDER = 
                                        new Comparator<Employee>() {
    public int compare(Employee e1, Employee e2) {
        int dateCmp = e2.hireDate().compareTo(e1.hireDate());
        if (dateCmp != 0)
            return dateCmp;

        return (e1.number() < e2.number() ? -1 :
               (e1.number() == e2.number() ? 0 : 1));
    }
};

最后一点：你可能想要用更简单的方法替换 Comparator 中的最终 return 语句：

return e1.number() - e2.number();

不要这样做，除非你 absolutely sure (绝对确定) 没有人会有负的员工编号！这个技巧一般不起作用，因为有符号整数类型不足以表示两个任意有符号整数的差异。如果 i 是一个大的正整数且 j 是一个大的负整数，i - j 将溢出并返回一个负整数。由此产生的 comparator 违反了我们一直在谈论的四个技术限制之一(传递性)并产生可怕的，微妙的错误。这不是纯粹的理论问题；人们吃过它的苦头。