Object Ordering

List l的排序如下。

Collections.sort(l);

如果ListString个元素组成,则会按字母 Sequences 排序。如果它包含Date个元素,则将按时间 Sequences 排序。这是怎么发生的? StringDate都实现Comparableinterface。 Comparable实现为类提供了自然排序,这允许该类的对象自动排序。下表总结了一些实现Comparable的更重要的 Java 平台类。

*类实现可比 *

ClassNatural Ordering
ByteSigned numerical
CharacterUnsigned numerical
LongSigned numerical
IntegerSigned numerical
ShortSigned numerical
DoubleSigned numerical
FloatSigned numerical
BigIntegerSigned numerical
BigDecimalSigned numerical
BooleanBoolean.FALSE < Boolean.TRUE
File路径名依赖于系统的词典
StringLexicographic
DateChronological
CollationKeyLocale-specific lexicographic

如果您try对列表进行排序(其元素未实现Comparable),则Collections.sort(list)将抛出ClassCastException。同样,如果您try对不能使用comparator进行元素比较的列表进行排序,则Collections.sort(list, comparator)将引发ClassCastException。可以相互比较的元素称为相互可比较。尽管不同类型的元素可以相互比较,但此处列出的所有类均不允许进行类间比较。

如果您只想对可比较元素的列表进行排序或创建它们的排序集合,那么您 true 需要了解的Comparableinterface。如果您想实现自己的Comparable类型,那么下一部分将是您感兴趣的。

编写自己的可比较类型

Comparableinterface包含以下方法。

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方法。

由于本节是关于元素排序的,所以让我们进一步谈谈NamecompareTo方法。它实现了标准的名称排序算法,其中姓氏优先于名字。这正是您想要的自然 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-一个封装订单的对象。像Comparableinterface一样,Comparatorinterface也包含一个方法。

public interface Comparator<T> {
    int compare(T o1, T o2);
}

compare方法比较其两个参数,根据第一个参数是否小于,等于或大于第二个参数,返回负整数,0 或正整数。如果两个参数中的任何一个都不适合Comparator,则compare方法将抛出ClassCastException

关于Comparable的大部分说法也适用于Comparator。编写compare方法与编写compareTo方法几乎相同,除了前者将两个对象都作为参数传入。出于相同的原因,compare方法必须遵守与ComparablecompareTo方法相同的四个技术限制-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排序时,这无关紧要;但是当您使用ComparatorOrder 已排序的集合时,这是致命的。如果您使用此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违反了我们一直在谈论的四个技术限制(传递性)之一,并产生了可怕的,微妙的错误。这不是纯粹的理论问题;人们被它烧死了。