Object Ordering
List l은 다음과 같이 정렬될 수 있습니다.
Collections.sort(l);List이 String 요소로 구성된 경우 알파벳순(alphabetical)으로 정렬됩니다. Date 요소로 구성된 경우 시간순(chronological)으로 정렬됩니다. 어떻게 이런 일이 발생하나요? String과 Date는 모두 Comparable 인터페이스를 구현합니다. Comparable 구현은 클래스에 대한 자연스러운 순서(natural ordering)를 제공하여 해당 클래스의 객체가 자동으로 정렬되도록 합니다. 다음 표에는 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 |
System-dependent lexicographic on path name |
String |
Lexicographic |
Date |
Chronological |
CollationKey |
Locale-specific lexicographic |
Comparable을 구현하지 않는 요소가 있는 list을 정렬하려고 하면 Collections.sort(list)가 ClassCastException을 발생시킵니다. 마찬가지로, comparator를 사용하여 요소를 서로 비교할 수 없는 list을 정렬하려고 하면 Collections.sort(list, comparator)는 ClassCastException을 발생시킵니다. 서로 비교할 수 있는 요소를 상호 비교 가능(mutually comparable)이라고 합니다. 다양한 유형의 요소는 서로 비교할 수 있지만 여기에 나열된 클래스 중 클래스 간 비교(interclass comparison)를 허용하는 클래스는 없습니다.
이것은 비교 가능한 요소 목록을 정렬하거나 정렬된 컬렉션을 생성하려는 경우 Comparable 인터페이스에 대해 알아야 할 모든 것입니다. 자신만의 Comparable 유형을 구현하려는 경우 다음 섹션이 흥미로울 것입니다.
Writing Your Own Comparable Types
Comparable 인터페이스는 다음과 같은 메소드로 구성됩니다.
public interface Comparable<T> {
public int compareTo(T o);
}compareTo 메서드는 수신 개체(receiving object)를 지정된 개체(specified object)와 비교하고 수신 개체가 지정된 개체보다 작거나 같은지 또는 큰지에 따라 음의 정수, 0 또는 양의 정수를 반환합니다. 지정된 개체를 수신 개체와 비교할 수 없는 경우 메서드는 ClassCastException을 발생시킵니다.
사람의 이름을 나타내는 다음 클래스는 Comparable을 구현합니다.
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));
}
}equals는 Object의 메소드를, compareTo는 String의 메소드를 오버라이드 함.
앞의 예를 짧게 유지하기 위해 클래스는 다소 제한적입니다. 중간 이름을 지원하지 않고 이름과 성을 모두 요구하며 어떤 식으로든 국제화(internationalized)되지 않습니다. 그럼에도 불구하고 다음과 같은 중요한 사항을 보여줍니다.
Name객체는 변경할 수 없습니다(immutable). 다른 모든 것이 동일하고(equal) 불변(immutable) 유형인 경우, 특히Set의 요소 또는Map의 키로 사용되는 객체의 경우 더욱 그렇습니다. 이러한 컬렉션은 컬렉션에 있는 동안 해당 요소나 키를 수정하면 중단됩니다.- 생성자는 인수가
null인지 확인합니다. 이렇게 하면 다른 메소드 중 어느 것도NullPointerException을 발생시키지 않도록 모든Name객체가 올바르게 구성됩니다. hashCode메소드가 재정의되었습니다. 이는equals메소드를 재정의하는 모든 클래스에 필수적입니다. (동일한 객체에는 동일한 해시 코드가 있어야 합니다.)- 지정된 객체가
null이거나 부적절한 유형인 경우equals메서드는false를 반환합니다. 이러한 상황에서compareTo메서드는 런타임 예외를 발생시킵니다. 이 두 가지 동작은 해당 메서드의 일반 계약(contracts)에 필요합니다. toString메소드가 재정의되어Name을 사람이 읽을 수 있는(human-readable) 형식으로 인쇄합니다. 이는 항상 좋은 생각이며, 특히 컬렉션에 포함될 개체의 경우 더욱 그렇습니다. 다양한 컬렉션 유형의toString메서드는 해당 요소, 키 및 값의toString메서드에 따라 달라집니다.
이 섹션은 요소 순서에 관한 것이므로 Name의 compareTo 메서드에 대해 좀 더 이야기해 보겠습니다. 이는 성이 이름보다 우선하는(take precedence on over) 표준 이름 정렬 알고리즘을 구현합니다. 이것이 바로 자연스러운 순서로 원하는 것입니다. 자연스러운 순서가 부자연스럽다면 정말 혼란스러울 것입니다!
compareTo가 어떻게 구현되는지 살펴보세요. 매우 일반적(typical)이기 때문입니다. 먼저 개체의 가장 중요한 부분(이 경우, last name)을 비교합니다. 종종 부품 유형의 자연스러운 순서(natural ordering)를 사용할 수 있습니다. 이 경우 부분은 String이고 자연스러운(natural)(사전식 lexicographic) 순서가 정확히 요구(called for)됩니다. 비교 결과가 동일함을 나타내는 0이 아닌 다른 결과가 나오면 완료된 것입니다. 결과를 반환하기만 하면 됩니다. 가장 중요한 부분이 동일(equal)하면 계속해서 다음으로 중요한 부분을 비교합니다. 이 경우 이름과 성, 두 부분만 있습니다. 더 많은 부품(parts)이 있는 경우 동일하지 않은 두 개를 찾을 때까지 부품을 비교하거나 가장 중요하지 않은 부품을 비교하는 시점에서 비교 결과를 반환하는 명백한 방식으로 진행합니다.
모든 것이 작동한다는 것을 보여주기 위해 여기에 이름 목록을 작성하고 정렬하는 프로그램이 있습니다.
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
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("Tome", "Rich")
};
List<Name> names = Arrays.asList(nameArray);
Collections.sort(names);
System.out.println(names);
}
}이 프로그램을 실행하면 다음과 같이 인쇄됩니다.
[Karl Ng, Tome Rich, Jeff Smith, John Smith]compareTo 메서드의 동작에는 네 가지 제한 사항이 있는데, 이는 상당히 기술적이고 지루하며 API 문서에 남겨 두는 것이 더 나으므로 지금은 다루지 않겠습니다. Comparable을 구현하는 모든 클래스가 이러한 제한 사항을 준수하는 것이 매우 중요하므로 Comparable을 구현하는 클래스를 작성하는 경우 Comparable에 대한 설명서를 읽어보세요. 제한 사항을 위반하는 개체 목록을 정렬하려고 하면 정의되지 않은 동작이 발생합니다. 기술적으로 말하면, 이러한 제한은 이를 구현하는 클래스의 객체에 대한 자연스러운 순서(natural ordering)가 전체 순서(total order)임을 보장합니다. 이는 정렬이 잘 정의되었는지 확인(ensure)하는 데 필요합니다.
Comparators
일부 개체를 자연 순서(natrual ordering)가 아닌 다른 순서로 정렬하려면 어떻게 해야 합니까? 아니면 Comparable을 구현하지 않은 일부 개체를 정렬하려면 어떻게 해야 합니까? 이러한 작업 중 하나를 수행하려면 순서를 캡슐화하는 개체인 Comparator를 제공해야 합니다. Comparable 인터페이스와 마찬가지로 Comparator 인터페이스도 단일 메소드로 구성됩니다.
public interface Comparator<T> {
int compare(T o1, T o2);
}compare 메서드는 두 인수를 비교하여 첫 번째 인수가 두 번째 인수보다 작거나 같은지, 큰지 여부에 따라 음의 정수, 0 또는 양의 정수를 반환합니다. 인수 중 하나에 Comparator에 대한 부적절한 유형이 있는 경우 compare 메소드는 ClassCastException을 발생시킵니다.
Comparable에 대해 언급된 내용의 대부분은 Comparator에도 적용됩니다. compare 메서드를 작성하는 것은 compareTo 메서드를 작성하는 것과 거의 동일합니다. 전자의 경우 두 개체가 모두 인수로 전달된다는 점만 다릅니다. compare 메서드는 같은 이유로 Comparable의 compareTo 메서드와 동일한 네 가지 기술적 제한 사항을 준수해야 합니다. Comparator는 비교하는 개체에 전체 순서(total order)를 유도해야 합니다.
다음과 같이 Employee라는 클래스가 있다고 가정합니다.
public class Employee implements Comparable<Employee> {
public Name name() { ... }
public int number() { ... }
public Date hireDate() { ... }
...
}Employee 인스턴스의 자연스러운 순서(natural order)가 직원 이름의 이름 순서(이전 예에서 정의된 대로)라고 가정해 보겠습니다. 불행하게도 상사는 직원들의 명단을 서열순(seniority)으로 요구했습니다. 이는 우리가 약간의 작업을 수행해야 하지만 많이는 수행하지 않음을 의미합니다. 다음 프로그램은 필요한 목록을 생성합니다.
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는 상당히(reasonably) 간단합니다(straightforward). hireDate 접근자(accessor) 메서드에서 반환된 값에 적용되는 Date의 자연 순서(natural ordering)에 의존(relies on)합니다. Comparator는 두 번째 인수의 고용 날짜를 첫 번째 인수로, 즉 그 반대가 아닌(rather than vice versa) 방향으로 전달합니다. 그 이유는 가장 최근에 입사한 직원이 가장 서열이 낮기 때문입니다(least senior). 채용 날짜 순서대로 정렬하면 목록이 역순으로 배치됩니다. 사람들이 이 효과를 얻기 위해 때때로 사용하는 또 다른 기술은 인수 순서를 유지하면서 비교 결과를 부정(negate)하는 것입니다.
// Don't do this!!
return -r1.hireDate().compareTo(r2.hireDate());후자는 작동이 보장되지 않으므로 항상 후자보다 전자 기술을 사용해야 합니다. 그 이유는 compareTo 메서드의 인수가 호출된 개체보다 작을 경우 모든 음수 int를 반환할 수 있기 때문입니다. 이상하게 보일 수도 있지만, 부정되었을 때 음수로 남아 있는 음수 int가 하나 있습니다.
-Integer.MIN_VALUE == Integer.MIN_VALUE이전 프로그램의 Comparator는 List 정렬에 적합하지만 한 가지 결함(deficiency)이 있습니다. 즉, 같음(equals)과 호환되지 않는(not compatible with) 순서를 생성하기 때문에 TreeSet과 같은 정렬된 컬렉션을 정렬하는 데 사용할 수 없습니다. 이는 이 Comparator가 equals 메소드와 동일하지 않은 객체를 동일시(equates)한다는 것을 의미합니다. 특히 같은 날짜에 고용된 두 명의 직원은 동일하게 비교됩니다. List을 정렬할 때 이는 중요하지 않습니다. 그러나 정렬된 컬렉션을 order하기 위해 Comparator를 사용하는 경우 이는 치명적입니다. 이 Comparator를 사용하여 동일한 날짜에 고용된 여러 직원을 TreeSet에 삽입하면 첫 번째 직원만 세트에 추가됩니다. 두 번째 요소는 중복된 요소로 간주되어 무시됩니다.
이 문제를 해결하려면 Comparator를 조정하여 equals과 호환되는(compatible with) 순서(ordering)를 생성하면 됩니다. 즉, compare를 사용할 때 동일한 것으로 표시되는 유일한 요소가 equals을 사용하여 비교할 때도 동일한 것으로 표시되도록 조정(tweak)하십시오. 이를 수행하는 방법은 Name과 같이 두 부분으로 비교를 수행하는 것입니다. 여기서 첫 번째 부분은 우리가 관심 있는 부분(이 경우 hireDate)이고 두 번째 부분은 각 객체를 고유하게 식별하는 속성입니다. 여기서 직원 번호는 명백한 속성입니다. 이것이 결과 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의 최종 return 문을 더 간단한 것으로 바꾸고 싶을 수도 있습니다.
return e1.number() - e2.number();누구도 음수의 직원 번호를 갖지 않을 것이라는 절대적 확신이 없다면 그렇게 하지 마십시오! 이 트릭은 일반적으로 부호 있는(signed) 정수 유형이 임의의 두 부호 있는 정수의 차이를 나타낼 만큼 크지 않기 때문에 작동하지 않습니다. i가 큰 양의 정수이고 j가 큰 음의 정수이면 i - j는 오버플로되어 음의 정수를 반환합니다. 결과 Comparator는 우리가 계속 이야기하는 네 가지 기술적 제한 사항(이행성) 중 하나를 위반하고 끔찍하고 미묘한 버그를 생성합니다. 이것은 순전히 이론적인 문제가 아닙니다. 사람들은 그것에 화상을 입습니다.
