深入理解Collections API(轉(zhuǎn))

一個(gè) List l 可能被做如下排序:

Collections.sort(l);
如果這個(gè) list 由 String 元素所組成, 那么它將按詞典排序法(按字母順序)進(jìn)行排序; 如果它是由 Date 元素所組成, 那么它將按年代順序來(lái)排序。 Java 怎么會(huì)知道該怎么做呢? 這一定是個(gè)魔術(shù)! 其實(shí)不然。實(shí)際上, String 和 Date 均實(shí)現(xiàn)了Comparable接口。 Comparable 接口為一個(gè)類提供一個(gè) 自然排序( natural ordering), 它允許那個(gè)類的對(duì)象被自動(dòng)排序。下表列出了實(shí)現(xiàn)了Comparable 的JDK類:

類 自然排序

Byte 帶符號(hào)的數(shù)字排序

Character 不帶符號(hào)的數(shù)字排序

Long 帶符號(hào)的數(shù)字排序

Integer 帶符號(hào)的數(shù)字排序

Short 帶符號(hào)的數(shù)字排序

Double 帶符號(hào)的數(shù)字排序

Float 帶符號(hào)的數(shù)字排序

BigInteger 帶符號(hào)的數(shù)字排序

BigDecimal 帶符號(hào)的數(shù)字排序

File 依賴系統(tǒng)的按路徑名字母順序排序

String 按字母順序排序

Date 按年代順序排序

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



如果你要為一個(gè)其元素沒(méi)有實(shí)現(xiàn) Comparable的列表排序，Collections.sort(list) 將扔出一個(gè) ClassCastException。類似的，如果你要為一個(gè)其元素沒(méi)有作相互比較的列表進(jìn)行排序， Collections.sort 將扔出一個(gè) ClassCastException. 能夠被相互比較的元素被稱作 mutually comparable（可相互比較的）。 雖然不同類型的元素有可能被相互比較，但以上列出的任何JDK類型都不允許在類之間的比較 （inter-class comparison）。


如果你只是要為可比較的元素的列表進(jìn)行排序，或?yàn)樗鼈儎?chuàng)建排序的對(duì)象集, 則這就是你實(shí)際需要了解的全部有關(guān) Comparable 接口的內(nèi)容。如果你要實(shí)現(xiàn)你自己的 Comparable 類型，則下一節(jié)將會(huì)引起你的興趣。

編寫(xiě)你自己的 Comparable 類型

Comparable 接口由一個(gè)單一的方法構(gòu)成:

public interface Comparable {

public int compareTo(Object o);

}

compareTo 方法將接收對(duì)象與特定對(duì)象進(jìn)行比較，并在接收對(duì)象小于、等于或大于特定對(duì)象時(shí)分別返回負(fù)整數(shù)、空或一個(gè)正整數(shù)。如果特定對(duì)象不能與接收對(duì)象相比較，該方法扔出一個(gè)ClassCastException. 這是一個(gè)表示某人姓名的類(a class representing a person´s name), 它實(shí)現(xiàn)了 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));

}

}



為了使這個(gè)例子短一些，該類受到了一點(diǎn)限制：它不支持中間名，它要求必須同時(shí)具有first name 和 last name, 而這不是在全世界都通用的。盡管如此，這個(gè)例子仍有幾個(gè)重要之處:
Name 對(duì)象是不變的（ immutable）。作為相等、不變類型的所有其它事情就是如何做的問(wèn)題，特別是對(duì)那些將被用來(lái)作為 Sets 中的元素或 Maps 中的鍵的對(duì)象來(lái)說(shuō)，更是如此。如果你對(duì)這些 對(duì)象集 中的元素或鍵做了更改，這些 對(duì)象集 將中斷。


構(gòu)造函數(shù)可檢查它的參數(shù)是否為 null。 這可以保證所有的Name 對(duì)象都能很好地形成。因而沒(méi)有其它方法會(huì)扔出NullPointerException.


hashCode 方法被重新定義。對(duì)重新定義 equals 方法的任意類來(lái)說(shuō)，這是必需的（essential）。 一般約定（general contract）需要 Object.equals. (Equal 對(duì)象必須具有相等的哈希代碼) 。


如果特定對(duì)象為 null，或一個(gè)不適當(dāng)?shù)念愋停? equals 方法則返回 false。 在這種情況下， compareTo 方法扔出一個(gè)運(yùn)行時(shí)異常。這兩個(gè)行為都是各自方法的一般約定所必需的。


toString 方法已被重新定義，從而可以以人們能夠讀懂的形式打印 Name 。這總是一個(gè)好主意，特別是對(duì)要被放入對(duì)象集 中的對(duì)象來(lái)說(shuō)，更有益處。各種 對(duì)象集 類型的 toString 方法依賴它們的元素、鍵和值的 toString 方法。
由于這一節(jié)介紹的是有關(guān)元素排序的問(wèn)題，因而讓我們稍微多談一點(diǎn) Name 的 compareTo 方法。它實(shí)現(xiàn)標(biāo)準(zhǔn)的姓名-排序算法，在該算法中，last name 優(yōu)先于 first name。這恰恰是你在一個(gè)natural ordering（自然排序）中所想要的。 如果自然排序不自然，那才容易引起混亂呢!


請(qǐng)看 compareTo 是如何被實(shí)現(xiàn)的，因?yàn)樗窍喈?dāng)?shù)湫偷?。首先，你?Object 參數(shù)轉(zhuǎn)換為適當(dāng)類型； 如果參數(shù)類型是不適當(dāng)?shù)模瑒t會(huì)扔出一個(gè)適當(dāng)?shù)漠惓?ClassCastException)；那么你應(yīng)該比較對(duì)象的最重要部分（在此案例中為 last name)。通常，你可以使用該部分的類型的自然排序。 在次案例中，該部分是一個(gè) String, 并且自然的（按詞典順序的）排序正是所要求的。如果比較的結(jié)果是空（它表示等同性）之外的其它東西，你就做完了：你可以返回結(jié)果。 如果最重要的部分是相等的，你就應(yīng)該繼續(xù)比較次重要部分。在此案例中，只有兩個(gè)部分 (first name and last name)。 如果有更多的部分，你就應(yīng)該以顯而易見(jiàn)的方式繼續(xù)進(jìn)行，直到發(fā)現(xiàn)兩個(gè)不相等的部分（否則你就應(yīng)該比較最不重要的部分），這時(shí)，你就可以返回比較結(jié)果了。 這是 一個(gè)建立 Name 對(duì)象列表并對(duì)它們進(jìn)行排序的小程序:

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);

}

}



如果你運(yùn)行這個(gè)程序，以下是它所打印的結(jié)果:

[Oscar Grouch, John Lennon, Groucho Marx, Karl Marx]對(duì) compareTo 方法的行為有四個(gè)限制，我們現(xiàn)在不作一一討論，因?yàn)樗鼈兊募夹g(shù)性太強(qiáng)，并且十分枯燥，我們最好將其留在API文本中。但是，所有實(shí)現(xiàn) Comparable 的類都必須接受這些限制的約束，這一點(diǎn)是確實(shí)重要的。因此，如果你要編寫(xiě)一個(gè)實(shí)現(xiàn)Comparable 的類，請(qǐng)讀那些有關(guān) Comparable 的文本吧。要試圖為違反了那些限制的對(duì)象的列表進(jìn)行排序可能引發(fā)不可預(yù)知的行為。從技術(shù)上講，這些限制保證了自然排序是實(shí)現(xiàn)它的類的對(duì)象的部分順序（partial order）。保證排序被很好地定義是十分必要的。

比較器（Comparators）

好，到目前為止，你已經(jīng)了解了自然排序。那么，如果要對(duì)某些對(duì)象不按自然順序進(jìn)行排序，又會(huì)怎么樣呢？或者，如果你要為某些不實(shí)現(xiàn) Comparable 的對(duì)象進(jìn)行排序呢？為做這些事情，你需要提供一個(gè)Comparator。 Comparator 實(shí)際就是一個(gè)封裝了排序的對(duì)象。與 Comparable 接口類似，Comparator 接口由一個(gè)的方法構(gòu)成:


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


compare 方法比較它的兩個(gè)參數(shù)，當(dāng)?shù)谝粋€(gè)參數(shù)小于、等于或大于第二個(gè)參數(shù)時(shí)，分別返回一個(gè)負(fù)整數(shù)、空或正整數(shù)。如果其中一個(gè)參數(shù)具有對(duì) Comparator 不適合的類型，compare 方法則扔出一個(gè) ClassCastException。


在上一節(jié)中的有關(guān) Comparable 的許多內(nèi)容也適用Comparator。編寫(xiě)一個(gè) compare 方法幾乎等同于編寫(xiě)一個(gè)compareTo 方法，除前者是把兩個(gè)參數(shù)都當(dāng)作參數(shù)之外。compare 方法必須象Comparable 的 compareTo 方法一樣，服從同樣的四個(gè)"技術(shù)限制"。出于同樣的原因， Comparator 必須對(duì)它所比較的對(duì)象誘發(fā)一個(gè) partial order（部分順序）。



假設(shè)你有一個(gè)稱作 EmployeeRecord 的類：


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


我們假設(shè) EmployeeRecord 對(duì)象的自然排序是對(duì)雇員姓名的排序 (就象上一個(gè)例子中所定義的)。不幸的是，老板要求我們提出一個(gè)按雇員資歷排序的列表。這就意味著我們必須做些額外的工作，但是不多。以下是一個(gè)將生成所需列表的程序：



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 相當(dāng)簡(jiǎn)單。它將它的參數(shù)轉(zhuǎn)換為EmployeeRecord, 并依賴適用于 hireDate()方法的 Date 的自然排序。請(qǐng)注意：Comparator 將它的第二個(gè)參數(shù)的雇用-日期傳遞給第一個(gè)參數(shù)，而不是按反方向傳遞。 這是因?yàn)?，最新雇用的雇員資歷最淺：按照雇用-日期排序?qū)⑹沽斜沓蔀榉聪蛸Y歷-順序。另一個(gè)獲得相同結(jié)果的方法是：保持參數(shù)順序，但對(duì)比較結(jié)果求反。


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


兩種方法同樣可取。使用哪一種，全由你自己。


以上程序中的 Comparator ，在對(duì) List 進(jìn)行排序時(shí)，效果很好。但有一個(gè)小的缺陷：它不能被用來(lái)對(duì)一個(gè)排序的 對(duì)象集 (如TreeSetM) 進(jìn)行排序，因?yàn)樗梢粋€(gè)嚴(yán)格的部分（strictly partial） 排序。這意味著這個(gè)comparator 使不相等的對(duì)象相等。特別的，它會(huì)使任意兩個(gè)雇用日期相同的雇員成為相等。當(dāng)你為一個(gè) List 排序時(shí)，這沒(méi)關(guān)系，但當(dāng)你使用 Comparator 為一個(gè)sort排序的對(duì)象集 排序時(shí)， 這就是致命的了。如果你將多個(gè)雇用日期相同的雇員用Comparator插入到一個(gè)TreeSet之中，那么只有第一個(gè)將被添加到 set，第二個(gè)將被作為一個(gè)復(fù)制元素而忽略。


為解決這個(gè)問(wèn)題，你必須做的一切就是修整 Comparator 使之生成一個(gè) total ordering（完整排序）。 換句話說(shuō)，修整 Comparator 是為了使在使用compare 時(shí)被認(rèn)為相等的唯一元素即是那些在使用equals 時(shí)被認(rèn)為相等的元素。 實(shí)現(xiàn)這個(gè)目的的途徑是做一個(gè)兩部分（two-part）比較 (就象我們?yōu)?Name 做的那樣)，這里的第一部分是我們真正感興趣的（此案例中為雇用-日期），而第二部分是可唯一識(shí)別的對(duì)象屬性。在此案例中，雇員號(hào)是作為第二部分使用的明顯的屬性。請(qǐng)看下面的 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)); }};


最后注意一點(diǎn)，你可能被引誘用更簡(jiǎn)單的程序來(lái)替代 Comparator 中最后的 return 語(yǔ)句:

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


不要這樣做，除非你能絕對(duì)保證不出現(xiàn)一個(gè)負(fù)的雇員數(shù)！這個(gè)技巧不可普遍使用，因?yàn)橐粋€(gè)帶正負(fù)號(hào)的整數(shù)類型，即使再大，也不足以表示兩個(gè)任意的帶正負(fù)號(hào)的整數(shù)的差值。如果 i 是一個(gè)大的正整數(shù)，j 是一個(gè)大的負(fù)整數(shù)，i-j 將溢出并返回一個(gè)負(fù)整數(shù)。 Comparator 的結(jié)果違反了我們一直在講的四個(gè)技術(shù)限制之中的一個(gè)限制（傳遞性），并導(dǎo)致可怕而玄妙的故障。 這并不是一個(gè)純技術(shù)問(wèn)題；搞不好，它會(huì)傷著你。 　[@more@]