Object Ordering
List
l
的排序如下。
Collections.sort(l);
如果List
由String
个元素组成,则会按字母 Sequences 排序。如果它包含Date
个元素,则将按时间 Sequences 排序。这是怎么发生的? String
和Date
都实现Comparable
interface。 Comparable
实现为类提供了自然排序,这允许该类的对象自动排序。下表总结了一些实现Comparable
的更重要的 Java 平台类。
*类实现可比 *
Class | Natural Ordering |
---|---|
Byte | Signed numerical |
Character | Unsigned numerical |
Long | Signed numerical |
Integer | Signed numerical |
Short | Signed numerical |
Double | Signed numerical |
Float | Signed numerical |
BigInteger | Signed numerical |
BigDecimal | Signed numerical |
Boolean | Boolean.FALSE < Boolean.TRUE |
File | 路径名依赖于系统的词典 |
String | Lexicographic |
Date | Chronological |
CollationKey | Locale-specific lexicographic |
如果您try对列表进行排序(其元素未实现Comparable
),则Collections.sort(list)
将抛出ClassCastException。同样,如果您try对不能使用comparator
进行元素比较的列表进行排序,则Collections.sort(list, comparator)
将引发ClassCastException
。可以相互比较的元素称为相互可比较。尽管不同类型的元素可以相互比较,但此处列出的所有类均不允许进行类间比较。
如果您只想对可比较元素的列表进行排序或创建它们的排序集合,那么您 true 需要了解的Comparable
interface。如果您想实现自己的Comparable
类型,那么下一部分将是您感兴趣的。
编写自己的可比较类型
Comparable
interface包含以下方法。
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
个对象是不可变的。在所有其他条件相同的情况下,不变类型是必经之路,特别是对于将在Set
s 中用作元素或在Map
s 中用作键的对象。如果您在集合中修改其元素或键,则这些集合将中断。 -
构造函数检查其参数
null
。这样可以确保所有Name
对象的格式正确,以便其他任何方法都不会抛出NullPointerException
。 -
重新定义了
hashCode
方法。这对于重新定义equals
方法的任何类都是必不可少的。 (相等的对象必须具有相等的哈希码.) -
如果指定的对象是
null
或类型不合适,则equals
方法将返回false
。在这种情况下,compareTo
方法将引发运行时异常。这两种行为都是相应方法的一般 Contract 所要求的。 -
重新定义了
toString
方法,因此它以人类可读的形式打印Name
。这总是一个好主意,特别是对于将要放入集合中的对象。各种集合类型的toString
方法取决于其元素,键和值的toString
方法。
由于本节是关于元素排序的,所以让我们进一步谈谈Name
的compareTo
方法。它实现了标准的名称排序算法,其中姓氏优先于名字。这正是您想要的自然 Sequences。如果自然排序不自然,那确实会造成混乱!
看一下compareTo
的实现方式,因为它很典型。首先,您比较对象的最高有效部分(在本例中为姓)。通常,您可以只使用 Component 类型的自然 Sequences。在这种情况下,该部分是String
,而自然(词典 Sequences)正是所需要的。如果比较结果得出零以外的任何值(表示相等),则说明您已经完成:您只需返回结果即可。如果最重要的部分相等,则 continue 比较下一个最重要的部分。在这种情况下,只有两个部分-名和姓。如果有更 Multipart,则以明显的方式进行操作,比较各部分,直到找到两个不相等的部分,或者您正在比较最低有效部分,此时将返回比较结果。
为了证明一切正常,这里是一个程序,该程序生成名称列表并对其进行排序。
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
的文档。try对违反限制的对象列表进行排序具有未定义的行为。从技术上讲,这些限制可确保自然 Sequences 是实现该 Sequences 的类的对象的总 Sequences;这是确保正确定义排序所必需的。
Comparators
如果要按自然 Sequences 以外的 Sequences 对某些对象进行排序怎么办?或者,如果您想对一些未实现Comparable
的对象进行排序,该怎么办?要执行上述任一操作,您需要提供一个Comparator-一个封装订单的对象。像Comparable
interface一样,Comparator
interface也包含一个方法。
public interface Comparator<T> {
int compare(T o1, T o2);
}
compare
方法比较其两个参数,根据第一个参数是否小于,等于或大于第二个参数,返回负整数,0 或正整数。如果两个参数中的任何一个都不适合Comparator
,则compare
方法将抛出ClassCastException
。
关于Comparable
的大部分说法也适用于Comparator
。编写compare
方法与编写compareTo
方法几乎相同,除了前者将两个对象都作为参数传入。出于相同的原因,compare
方法必须遵守与Comparable
的compareTo
方法相同的四个技术限制-Comparator
必须在其比较的对象上产生总 Sequences。
假设您有一个名为Employee
的类,如下所示。
public class Employee implements Comparable<Employee> {
public Name name() { ... }
public int number() { ... }
public Date hireDate() { ... }
...
}
假设Employee
个实例的自然排序是对雇员姓名的Name
排序(如上例所示)。不幸的是,老板要求按照资历 Sequences 列出员工名单。这意味着我们必须做一些工作,但不多做。以下程序将生成所需的列表。
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
将第二个参数的雇用日期传递给第一个参数,而不是相反。原因是最近雇用的雇员的最低年龄;按雇用日期的 Sequences 进行排序将使列表按相反的年资 Sequences 排列。人们有时用来实现此效果的另一种技术是保持参数 Sequences,但否定比较结果。
// Don't do this!!
return -r1.hireDate().compareTo(r2.hireDate());
您应该始终使用前一种技术来支持后者,因为不能保证后者可以工作。这样做的原因是,如果compareTo
方法的参数小于调用它的对象,则compareTo
方法可以返回任何负数int
。有一个负数int
取反后仍然为负数,看起来很奇怪。
-Integer.MIN_VALUE == Integer.MIN_VALUE
上一程序中的Comparator
可以很好地对List
进行排序,但是它确实有一个不足:它不能用于对已排序的集合(例如TreeSet
)进行排序,因为它会生成与 equals 不兼容的排序。这意味着此Comparator
等同于equals
方法没有的对象。特别是,在同一日期雇用的任何两名雇员将进行平等比较。当您对List
排序时,这无关紧要;但是当您使用Comparator
Order 已排序的集合时,这是致命的。如果您使用此Comparator
将同一日期雇用的多名员工插入TreeSet
,则只会将第一个雇员添加到集合中;第二个将被视为重复元素,将被忽略。
要解决此问题,只需调整Comparator
,使其产生与equals
兼容的 Sequences。换句话说,对其进行调整,以使使用compare
时被视为相等的唯一元素是使用equals
进行比较时也被视为相等的元素。这样做的方法是执行两部分比较(针对Name
),其中第一部分是我们感兴趣的部分(在本例中为雇用日期),第二部分是唯一标识的属性object。在这里,员 Worker 数是显而易见的属性。这就是结果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
中的finalreturn
语句替换为以下更简单的代码:
return e1.number() - e2.number();
除非您完全确定没有人会有负号的员工,否则请不要这样做!此技巧通常不起作用,因为有符号整数类型不足以表示两个任意有符号整数的差。如果i
是一个较大的正整数,而j
是一个较大的负整数,则i - j
将溢出并返回一个负整数。结果comparator
违反了我们一直在谈论的四个技术限制(传递性)之一,并产生了可怕的,微妙的错误。这不是纯粹的理论问题;人们被它烧死了。