15.7 比较函数
TreeSet和TreeMap都按排序顺序存储元素。然而，精确定义采用何种“排序顺序”的是比较函数。通常在默认的情况下，这些类通过使用被Java称之为“自然顺序”的顺序存储它们的元素，而这种顺序通常也是你所需要的（A在B的前面，1在2的前面，等等）。假如需要用不同的方法对元素进行排序，可以在构造集合或映射时，指定一个Comparator对象。这样做为你提供了一种精确控制如何将元素储存到排序类集和映射中的能力。
Comparator接口定义了两个方法：compare（ ）和equals（ ）。这里给出的compare（ ）方法按顺序比较了两个元素：
int compare(Object obj1, Object obj2)
obj1和obj2是被比较的两个对象。当两个对象相等时，该方法返回0；当obj1大于obj2时，返回一个正值；否则，返回一个负值。假如用于比较的对象的类型不兼容的话，该方法引发一个ClassCastException异常。通过覆盖compare（ ），可以改变对象排序的方式。例如，通过创建一个颠倒比较输出的比较函数，可以实现按逆向排序。
这里给出的equals( )方法，测试一个对象是否与调用比较函数相等：
boolean equals(Object obj)
obj是被用来进行相等测试的对象。假如obj和调用对象都是Comparator的对象并且使用相同的排序。该方法返回true.否则返回false.重载equals（ ）方法是没有必要的，大多数简单的比较函数都不这样做。
15.7.1 使用比较函数
下面是一个说明定制的比较函数能力的例子。该例子实现compare（ ）方法以便它按正常顺序的逆向进行操作。因此，它使得一个树集合按逆向的顺序进行存储。
// Use a custom comparator.
import java.util.*;
// A reverse comparator for strings.
class MyComp implements Comparator {
public int compare(Object a, Object b) {
String aStr, bStr;
aStr = (String) a;
bStr = (String) b;
// reverse the comparison
return bStr.compareTo(aStr);
}
// no need to override equals
}
class CompDemo {
public static void main(String args[]) {
// Create a tree set
TreeSet ts = new TreeSet(new MyComp());
// Add elements to the tree set
ts.add("C");
ts.add("A");
ts.add("B");
ts.add("E");
ts.add("F");
ts.add("D");
// Get an iterator
Iterator i = ts.iterator();
// Display elements
while(i.hasNext()) {
Object element = i.next();
System.out.print(element + " ");
}
System.out.println();
}
}
正如下面的输出所示，树按照逆向顺序进行存储：
F E D C B A
仔细观察实现Comparator并覆盖compare（ ）方法的MyComp类（正如前面所解释的那样，覆盖equals（ ）方法既不是必须的，也不是常用的）。在compare（ ）方法内部，String方法compareTo（ ）比较两个字符串。然而由bStr？？不是aStr？？调用compareTo（ ）方法，这导致比较的结果被逆向。
对应一个更实际的例子，下面的例子是用TreeMap程序实现前面介绍的存储账目资产平衡表例子的程序。在前面介绍的程序中，账目是按名进行排序的，但程序是以按照名字进行排序开始的。下面的程序按姓对账目进行排序。为了实现这种功能，程序使用了比较函数来比较每一个账目下姓的排序。得到的映射是按姓进行排序的。
// Use a comparator to sort accounts by last name.
import java.util.*;
// Compare last whole Words in two strings.
class TComp implements Comparator {
public int compare(Object a, Object b) {
int i, j, k;
String aStr, bStr;
aStr = (String) a;
bStr = (String) b;
// find index of beginning of last name
i = aStr.lastIndexOf(' ');
j = bStr.lastIndexOf(' ');
k = aStr.substring(i).compareTo(bStr.substring(j));
if(k==0) // last names match, check entire name
return aStr.compareTo(bStr);
else
return k;
}
// no need to override equals
}
class TreeMapDemo2 {
public static void main(String args[]) {
// Create a tree map
TreeMap tm = new TreeMap(new TComp());
// Put elements to the map
tm.put("John Doe", new Double(3434.34));
tm.put("Tom Smith", new Double(123.22));
tm.put("Jane Baker", new Double(1378.00));
tm.put("Todd Hall", new Double(99.22));
tm.put("Ralph Smith", new Double(-19.08));
// Get a set of the entries
Set set = tm.entrySet();
// Get an iterator
Iterator itr = set.iterator();
// Display elements
while(itr.hasNext()) {
Map.Entry me = (Map.Entry)itr.next();
System.out.print(me.getKey() + ": ");
System.out.println(me.getValue());
}
System.out.println();
// Deposit 1000 into John Doe's account
double balance = ((Double)tm.get("John Doe")).doubleValue();
tm.put("John Doe", new Double(balance + 1000));
System.out.println("John Doe's new balance: " +
tm.get("John Doe"));
}
}
这里是程序的输出结果，注重此时的账目是按姓进行排序的：
Jane Baker: 1378.0
John Doe: 3434.34
Todd Hall: 99.22
Ralph Smith: -19.08
Tom Smith: 123.22
John Doe’s new balance: 4434.34
比较函数类TComp比较两个包含姓和名的字符串。它首先比较姓。具体是这样做的，它首先寻找每一个字符串中最后一个空格的下标，然后比较从这个位置开始的每一个元素的子字符串。当两个字符串中姓完全相等时，它再比较两个名。这样就形成了一个先按姓进行排序，在姓相同的情况下，再按名字进行排序的树型映射。通过程序的输出中RalphSmith出现在Tom Smith之前的结果可以看到这一点。
15.8 类集算法
类集框架定义了几种能用于类集和映射的算法。在Collections类中，这些算法被定义为静态方法。表15-9中列出了这些算法。当试图比较不兼容的类型时，其中的一些算法引发一个ClassCastException 异常； 而当试图改变一个不可改变的类集时， 则引发一个UnsupportedOperationException异常。
表15-9 由Collections 定义的算法
方法描述
static int binarySearch（List list， Objectvalue，Comparator c）按照c的次序在list中搜寻value.假如value在list内，则返回value在list的位置。假如在list中没有发现value，则返回-1
static int binarySearch（List list， Object value） 在list中搜寻value，列表（list）必须被排序。假如value在list内，则返回value的位置。假如在list中没有发现value，则返回-1
static void copy(List list1, List list2) 将list2中的元素复制给list1
续表
方法描述
static Enumeration enumeration(Collection c) 返回c的一个枚举（参看本章后面的“枚举接口”）。
static void fill(List list, Object obj) 将obj赋给list中的每一个元素
Static Object max(Collection c,Comparator comp) 返回由comp确定的c中的最大元素
static Object max(Collection c) 返回按自然顺序确定的c中的最大元素。类集不必被排序
static Object min(Collection c,Comparator comp) 返回由comp确定的c中的最小元素。类集不必被排序
static Object min(Collection c) 返回按自然顺序确定的c中的最小元素
static List nCopies(int num, Object obj) 返回包含在不可改变的列表中的obj的num个拷贝。
num必须大于等于0
static void reverse(List list) 将list中的序列逆向
static Comparator reverseOrder( ) 返回一个逆向比较函数（即将两个元素比较的结果进行逆向的比较函数）
static void shuffle(List list, Random r) 用r作为随机数的源，对list中的元素进行混淆（也即随机化）
