深入理解Collections API(转)

一个 List l 可能被做如下排序:

Collections.sort(l);
如果这个 list 由 String 元素所组成, 那么它将按词典排序法(按字母顺序)进行排序; 如果它是由 Date 元素所组成, 那么它将按年代顺序来排序。 Java 怎么会知道该怎么做呢? 这一定是个魔术! 其实不然。实际上, String 和 Date 均实现了Comparable接口。 Comparable 接口为一个类提供一个 自然排序( natural ordering), 它允许那个类的对象被自动排序。下表列出了实现了Comparable 的JDK类:

类 自然排序

Byte 带符号的数字排序

Character 不带符号的数字排序

Long 带符号的数字排序

Integer 带符号的数字排序

Short 带符号的数字排序

Double 带符号的数字排序

Float 带符号的数字排序

BigInteger 带符号的数字排序

BigDecimal 带符号的数字排序

File 依赖系统的按路径名字母顺序排序

String 按字母顺序排序

Date 按年代顺序排序

CollationKey 特定字符集按字母顺序排序



如果你要为一个其元素没有实现 Comparable的列表排序，Collections.sort(list) 将扔出一个 ClassCastException。类似的，如果你要为一个其元素没有作相互比较的列表进行排序， Collections.sort 将扔出一个 ClassCastException. 能够被相互比较的元素被称作 mutually comparable（可相互比较的）。 虽然不同类型的元素有可能被相互比较，但以上列出的任何JDK类型都不允许在类之间的比较 （inter-class comparison）。


如果你只是要为可比较的元素的列表进行排序，或为它们创建排序的对象集, 则这就是你实际需要了解的全部有关 Comparable 接口的内容。如果你要实现你自己的 Comparable 类型，则下一节将会引起你的兴趣。

编写你自己的 Comparable 类型

Comparable 接口由一个单一的方法构成:

public interface Comparable {

public int compareTo(Object o);

}

compareTo 方法将接收对象与特定对象进行比较，并在接收对象小于、等于或大于特定对象时分别返回负整数、空或一个正整数。如果特定对象不能与接收对象相比较，该方法扔出一个ClassCastException. 这是一个表示某人姓名的类(a class representing a person´s name), 它实现了 Comparable:

import java.util.*;



public class Name implements Comparable {

private 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(Object o) {

Name n = (Name)o;

int lastCmp = lastName.compareTo(n.lastName);

return (lastCmp!=0 ? lastCmp :

firstName.compareTo(n.firstName));

}

}



为了使这个例子短一些，该类受到了一点限制：它不支持中间名，它要求必须同时具有first name 和 last name, 而这不是在全世界都通用的。尽管如此，这个例子仍有几个重要之处:
Name 对象是不变的（ immutable）。作为相等、不变类型的所有其它事情就是如何做的问题，特别是对那些将被用来作为 Sets 中的元素或 Maps 中的键的对象来说，更是如此。如果你对这些 对象集 中的元素或键做了更改，这些 对象集 将中断。


构造函数可检查它的参数是否为 null。 这可以保证所有的Name 对象都能很好地形成。因而没有其它方法会扔出NullPointerException.


hashCode 方法被重新定义。对重新定义 equals 方法的任意类来说，这是必需的（essential）。 一般约定（general contract）需要 Object.equals. (Equal 对象必须具有相等的哈希代码) 。


如果特定对象为 null，或一个不适当的类型， equals 方法则返回 false。 在这种情况下， compareTo 方法扔出一个运行时异常。这两个行为都是各自方法的一般约定所必需的。


toString 方法已被重新定义，从而可以以人们能够读懂的形式打印 Name 。这总是一个好主意，特别是对要被放入对象集 中的对象来说，更有益处。各种 对象集 类型的 toString 方法依赖它们的元素、键和值的 toString 方法。
由于这一节介绍的是有关元素排序的问题，因而让我们稍微多谈一点 Name 的 compareTo 方法。它实现标准的姓名-排序算法，在该算法中，last name 优先于 first name。这恰恰是你在一个natural ordering（自然排序）中所想要的。 如果自然排序不自然，那才容易引起混乱呢!


请看 compareTo 是如何被实现的，因为它是相当典型的。首先，你将 Object 参数转换为适当类型； 如果参数类型是不适当的，则会扔出一个适当的异常(ClassCastException)；那么你应该比较对象的最重要部分（在此案例中为 last name)。通常，你可以使用该部分的类型的自然排序。 在次案例中，该部分是一个 String, 并且自然的（按词典顺序的）排序正是所要求的。如果比较的结果是空（它表示等同性）之外的其它东西，你就做完了：你可以返回结果。 如果最重要的部分是相等的，你就应该继续比较次重要部分。在此案例中，只有两个部分 (first name and last name)。 如果有更多的部分，你就应该以显而易见的方式继续进行，直到发现两个不相等的部分（否则你就应该比较最不重要的部分），这时，你就可以返回比较结果了。 这是 一个建立 Name 对象列表并对它们进行排序的小程序:

import java.util.*;



class NameSort {

public static void main(String args[]) {

Name n[] = {

new Name("John", "Lennon"),

new Name("Karl", "Marx"),

new Name("Groucho", "Marx"),

new Name("Oscar", "Grouch")

};

List l = Arrays.asList(n);

Collections.sort(l);

System.out.println(l);

}

}



如果你运行这个程序，以下是它所打印的结果:

[Oscar Grouch, John Lennon, Groucho Marx, Karl Marx]对 compareTo 方法的行为有四个限制，我们现在不作一一讨论，因为它们的技术性太强，并且十分枯燥，我们最好将其留在API文本中。但是，所有实现 Comparable 的类都必须接受这些限制的约束，这一点是确实重要的。因此，如果你要编写一个实现Comparable 的类，请读那些有关 Comparable 的文本吧。要试图为违反了那些限制的对象的列表进行排序可能引发不可预知的行为。从技术上讲，这些限制保证了自然排序是实现它的类的对象的部分顺序（partial order）。保证排序被很好地定义是十分必要的。

比较器（Comparators）

好，到目前为止，你已经了解了自然排序。那么，如果要对某些对象不按自然顺序进行排序，又会怎么样呢？或者，如果你要为某些不实现 Comparable 的对象进行排序呢？为做这些事情，你需要提供一个Comparator。 Comparator 实际就是一个封装了排序的对象。与 Comparable 接口类似，Comparator 接口由一个的方法构成:


public interface Comparator { int compare(Object o1, Object o2);}


compare 方法比较它的两个参数，当第一个参数小于、等于或大于第二个参数时，分别返回一个负整数、空或正整数。如果其中一个参数具有对 Comparator 不适合的类型，compare 方法则扔出一个 ClassCastException。


在上一节中的有关 Comparable 的许多内容也适用Comparator。编写一个 compare 方法几乎等同于编写一个compareTo 方法，除前者是把两个参数都当作参数之外。compare 方法必须象Comparable 的 compareTo 方法一样，服从同样的四个"技术限制"。出于同样的原因， Comparator 必须对它所比较的对象诱发一个 partial order（部分顺序）。



假设你有一个称作 EmployeeRecord 的类：


public class EmployeeRecord implements Comparable { public Name name(); public int employeeNumber(); public Date hireDate(); ...}


我们假设 EmployeeRecord 对象的自然排序是对雇员姓名的排序 (就象上一个例子中所定义的)。不幸的是，老板要求我们提出一个按雇员资历排序的列表。这就意味着我们必须做些额外的工作，但是不多。以下是一个将生成所需列表的程序：



import java.util.*;class EmpSort { static final Comparator SENIORITY_ORDER = new Comparator() { public int compare(Object o1, Object o2) { EmployeeRecord r1 = (EmployeeRecord) o1; EmployeeRecord r2 = (EmployeeRecord) o2; return r2.hireDate().compareTo(r1.hireDate()); } }; static final Collection employees = ... ; // Employee Database public static void main(String args[]) { List emp = new ArrayList(employees); Collections.sort(emp, SENIORITY_ORDER); System.out.println(emp); }}


以上程序中的 Comparator 相当简单。它将它的参数转换为EmployeeRecord, 并依赖适用于 hireDate()方法的 Date 的自然排序。请注意：Comparator 将它的第二个参数的雇用-日期传递给第一个参数，而不是按反方向传递。 这是因为，最新雇用的雇员资历最浅：按照雇用-日期排序将使列表成为反向资历-顺序。另一个获得相同结果的方法是：保持参数顺序，但对比较结果求反。


return -r1.hireDate().compareTo(r2.hireDate());


两种方法同样可取。使用哪一种，全由你自己。


以上程序中的 Comparator ，在对 List 进行排序时，效果很好。但有一个小的缺陷：它不能被用来对一个排序的 对象集 (如TreeSetM) 进行排序，因为它生成一个严格的部分（strictly partial） 排序。这意味着这个comparator 使不相等的对象相等。特别的，它会使任意两个雇用日期相同的雇员成为相等。当你为一个 List 排序时，这没关系，但当你使用 Comparator 为一个sort排序的对象集 排序时， 这就是致命的了。如果你将多个雇用日期相同的雇员用Comparator插入到一个TreeSet之中，那么只有第一个将被添加到 set，第二个将被作为一个复制元素而忽略。


为解决这个问题，你必须做的一切就是修整 Comparator 使之生成一个 total ordering（完整排序）。 换句话说，修整 Comparator 是为了使在使用compare 时被认为相等的唯一元素即是那些在使用equals 时被认为相等的元素。 实现这个目的的途径是做一个两部分（two-part）比较 (就象我们为 Name 做的那样)，这里的第一部分是我们真正感兴趣的（此案例中为雇用-日期），而第二部分是可唯一识别的对象属性。在此案例中，雇员号是作为第二部分使用的明显的属性。请看下面的 Comparator :



static final Comparator SENIORITY_ORDER = new Comparator() { public int compare(Object o1, Object o2) { EmployeeRecord r1 = (EmployeeRecord) o1; EmployeeRecord r2 = (EmployeeRecord) o2; int dateCmp = r2.hireDate().compareTo(r1.hireDate()); if (dateCmp != 0) return dateCmp; return (r1.employeeNumber() < r2.employeeNumber() ? -1 : (r1.employeeNumber() == r2.employeeNumber() ? 0 : 1)); }};


最后注意一点，你可能被引诱用更简单的程序来替代 Comparator 中最后的 return 语句:

return r1.employeeNumber() - r2.employeeNumber();


不要这样做，除非你能绝对保证不出现一个负的雇员数！这个技巧不可普遍使用，因为一个带正负号的整数类型，即使再大，也不足以表示两个任意的带正负号的整数的差值。如果 i 是一个大的正整数，j 是一个大的负整数，i-j 将溢出并返回一个负整数。 Comparator 的结果违反了我们一直在讲的四个技术限制之中的一个限制（传递性），并导致可怕而玄妙的故障。 这并不是一个纯技术问题；搞不好，它会伤着你。 　[@more@]