編寫你自己的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() $#@60; r2.employeeNumber() ? -1 :
(r1.employeeNumber() == r2.employeeNumber() ? 0 : 1));
}
};
最後注意一點，你可能被引誘用更簡單的程序來替代 Comparator 中最後的 return 語句:
return r1.employeeNumber() - r2.employeeNumber();
不要這樣做，除非你能絕對保證不出現一個負的雇員數！這個技巧不可普遍使用，因為一個帶正負號的整數類型，即使再大，也不足以表示兩個任意的帶正負號的整數的差值。如果 i 是一個大的正整數，j 是一個大的負整數，i-j 將溢出並返回一個負整數。 Comparator 的結果違反了我們一直在講的四個技術限制之中的一個限制（傳遞性），並導致可怕而玄妙的故障。 這並不是一個純技術問題；搞不好，它會傷著你。
SortedSet 接口
SortedSet是一個使其元素維持上升順序的Set, 它按照元素的自然順序進行排序，或按照在SortedSet 創建時提供的 Comparator 進行排序（自然順序和 Comparators 已在前面的有關 Object Ordering 的章節中做過討論）。除了正常的 Set 操作之外， 該 Set 接口還提供下列操作：
局域視圖: 對 sorted set 執行任意局域操作。
端點：返回在 sorted set 中的第一個或最後一個元素。
比較器存取: 返回對 set 進行排序的Comparator 。
SortedSet 接口如下所示:
public interface SortedSet extends Set {
// Range-view
SortedSet subSet(Object fromElement, Object toElement);
SortedSet headSet(Object toElement);
SortedSet tailSet(Object fromElement);
// Endpoints
Object first();
Object last();
// Comparator access
Comparator comparator();
}
Set 操作
從 Set 繼承的 SortedSet 操作在 sorted sets 和正常 sets 上的表現完全相同，只有兩個例外:
由 iterator 操作返回的 Iterator 按順序遍歷 sorted set。
由 toArray 返回的數組按順序包括 sorted set 的元素。
盡管該接口不保證這一點，但 JDK 的 SortedSet 實現的 toString 方法返回一個按順序包含所有 sorted set 元素的串。
標准構造函數
按慣例，所有 Collection 實現都提供一個采用一種 Collection 的標准構造函數。SortedSet 實現也不例外。該構造函數創建了一個SortedSet 對象，它可按自然順序為它的元素排序。除此之外，按慣例，SortedSet 實現還提供另外兩個標准構造函數:
一個構造函數采用 Comparator 並返回一個新的（空的）按特定Comparator 排序的 SortedSet。
另一個構造函數采用 SortedSet 並返回一個新的包含與給定 SortedSet 相同的元素的 SortedSet, 它按照相同的Comparator進行排序 (或是用元素的自然順序，如果給定的 SortedSet 也這樣做過的話)。 請注意，決定該構造函數是否比普通 Set 構造函數可優先調用的是參數的編譯時類型，而不是運行時類型!
第一個標准構造函數是用顯式Comparator 創建一個空的 SortedSet 的一般方法。第二個標准構造函數在本質上與標准Collection 構造函數相似：它用同樣的排序創建一個 SortedSet 的拷貝，但使用的是一個程序員指定的實現類型。
局域視圖操作
這裡的局域視圖操作與 List 接口 提供的局域視圖操作有些相似，但有一個大的區別。一個 sorted set 的局域視圖將保持有效，即使後備 sorted set 被直接更改也不例外。這是可行的，因為一個 sorted set 的一個局域視圖的端點是元素空間中的絕對點，而不是在後備 對象集 中的特定元素(如列表中的情況)。一個 sorted set 的局域視圖實際恰恰是一個位於元素空間的指定部位的 set 的某個位置上的視窗。局域視圖的變化寫回到後備sorted set ，反之亦然。 因此，完全可以在 sorted sets 上長期使用局域視圖 (與在列表上的局域視圖不同)。
Sorted sets 提供三個局域視圖操作。第一個是subSet，subSet 采用兩個端點 (就象 subList中的操作一樣)。該端點是對象，而不是索引。它們必須與 sorted set 中的元素是可比較的(使用 set 的 Comparator 或它的元素的自然排序，只要是 set 用來為自己排序的那一個)。就象 subList 一樣，局域是半開放的（half-open）, 它包括它的低端點，但不包括它的高端點。
於是，下面的一行程序將告知你在"doorbell" 和 "pickle"之間有多少個詞（包括 "doorbell" 但不包括 "pickle"）被包括在稱作詞典的串的 SortedSet 之中:
int count = dictionary.subSet("doorbell", "pickle").size();
類似的，下面的一行程序將刪除所有以"f" 開始的元素(是不是一個很嚴厲的審查制度?):
dictionary.subSet("f", "g").clear();
你可以使用相似的技巧打印表格，並告知你以每個字母開始的詞有多少:
for (char ch="a"; ch$#@60;="z"; ch++) {
String from = new String(new char[] {ch});
String to = new String(new char[] {(char)(ch+1)});
System.out.println(from + ": " +
dictionary.subSet(from, to).size());
}
假設你要視圖一個封閉的區間（closed interval） (兩個端點都被包括)而不是一個開放的區間。如果該元素類型允許對一個給定值進行後繼符（successor） 計算（在該元素空間）， 那麼， subSet 只要從 lowEndpoint 至 successor(highEndpoint) 發出請求。盡管這不是顯而易見的，但是，在 String 的自然排序中的一個串 s 的後繼符是 s+"\0" (即，s 加上一個空字符)。
於是，下面的一行程序將告知你在"doorbell" 和 "pickle"之間（包括 "doorbell" 和 "pickle"）有多少詞被包括在詞典裡:
dd$#@60;$#@62; int count = dictionary.subSet("doorbell", "pickle\0").size();
類似的技術也可被用來視圖一個開放的區間（open interval） (兩個端點都不被包括)。從lowEndpoint 至 highEndpoint 的開放區間視圖是從 successor(lowEndpoint) 至 highEndpoint 的半開放區間。下列程序計算在"doorbell" 和 "pickle"之間的詞匯數（不包括上述兩個詞）:
int count = dictionary.subSet("doorbell\0", "pickle").size();
SortedSet 接口還包括另外兩個局域視圖操作, headSet 和 tailSet, 這兩個操作均采用一個單一的 Object 參數。前者返回對後備 SortedSet 的初始部分的一個視圖，一直到該特定對象，但不包括該特定對象；後者返回這個後備SortedSet 的最後部分的一個視圖，它從這個特定對象開始，直到該後備 SortedSet 的結束。於是，下列代碼允許你把該詞典作為分開的兩"卷"來視圖(a-m 和 n-z):
SortedSet volume1 = dictionary.headSet("n");
SortedSet volume2 = dictionary.tailSet("n");
端點操作
SortedSet 接口返回 sorted set 中的第一個和最後一個元素的操作，稱作 (不必驚訝) first 和 last。除了它們顯而易見的用處外，last 還為 SortedSet 接口中的缺陷准備了一個工作區。 你在 SortedSet 上所要做的一件事情就是進入 set 的內部並向前或向後迭代。從內部向前迭代是非常容易的：只要采用tailSet 並在它上面迭代就可以了。不幸的是，沒有向後迭代的簡單途徑。
下列慣用程序可獲取在一個 sorted set中的第一個元素，在元素空間中它小於一個特定對象 o :
Object predecessor = ss.headSet(o).last();
這是從一個 sorted set 內部的一點向後"走過"一個元素的好辦法。它可重復地應用於向後迭代。但不幸的是，它的效率太低，它要求查找返回的每一個元素。
比較器存取操作（Comparator Accessor）
SortedSet 接口包含一個被稱作 comparator 的存取操作方法，它返回用來對 set 進行排序的Comparator，如果該 set 是按照它的元素的自然順序排序的，則返回 null 。提供這個方法的目的是為了使 sorted sets 能被拷貝為一個新的排序相同的 sorted sets 。它被 以上 描述的標准 SortedSet 構造函數所采用。
SortedMap接口
SortedMap是一個將它的項保持為上升順序的Map, 它按照鍵的自然順序進行排序，或按照在SortedMap 創建時提供的 Comparator 進行排序（自然順序和 Comparators 已在前面的有關 Object Ordering 的章節中做過討論）。除了正常的 Map 操作之外，該 Map 接口還提供下列操作：
局域視圖: 對 sorted Map 執行任意局域操作。
端點：返回在 sorted Map 中的第一個或最後一個鍵。
比較器存取: 返回對 map 進行排序的Comparator 。 public interface SortedMap extends Map { Comparator comparator(); SortedMap subMap(Object fromKey, Object toKey); SortedMap headMap(Object toKey); SortedMap tailMap(Object fromKey); Object first(); Object last(); } 這個接口是SortedSet的 Map等價物
Map操作
SortedMap 從 Map 繼承的操作在 sorted maps 和正常 maps 上的行為是等同的，只有兩個例外：
由對任意 sorted map 的 對象集視圖的 iterator 操作所返回的 Iterator 按順序遍歷對象集。
由 Collection視圖的 toArray 操作所返回的數組按順序包括鍵、值或項。
盡管該接口不保證這一點，但在 JDK 的 SortedMap 實現中的Collection視圖的 toString 方法返回一個按順序包含視圖的所有元素的串。
標准構造函數（Standard Constructors）
按慣例，所有的 Map 實現都提供一個采用一個 Map 的標准構造函數，SortedMap 實現也不例外。該構造函數創建了一個 SortedMap 對象，它按照它們的鍵的自然順序對它的項進行排序。除此之外 ，按慣例，SortedMap 實現還提供另外兩個標准構造函數:
一個構造函數采用一個 Comparator 並返回一個新的（空的）按特定 Comparator 排序的SortedMap。
另一個構造函數采用一個 SortedMap 並返回一個新的包含與給定的 SortedMap 的映射相同的 SortedMap,
它按照同樣的 Comparator進行排序 (或是用元素的自然順序，如果特定的 SortedMap 也這樣做過的話)。
請注意，決定該構造函數是否比普通 Map 構造函數優先調用的是參數的編譯時類型，而不是它的運行時類型! 第一個標准構造函數是用顯式 Comparator 創建一個空的 SortedSet 的一般方法。第二個標准構造函數在本質上與標准 Map 構造函數相似：它用同樣的排序創建一個 SortedMap 的拷貝，但使用的是一個程序員指定的實現類型。
與SortedSet的比較
因為這個接口是 SortedSet 的一個精確的 Map 對等物，所以，在 SortedSet章節 中的所有的慣用程序和代碼舉例均適用於 SortedMap, 只需一些小的更改。
