集合——使用TreeMap

我們已經知道，HashMap是一種以空間換時間的映射表，它的實作原理決定了内部的Key是無序的，即周遊HashMap的Key時，其順序是不可預測的（但每個Key都會周遊一次且僅周遊一次）。

還有一種Map，它在内部會對Key進行排序，這種Map就是SortedMap。注意到SortedMap是接口，它的實作類是TreeMap。

SortedMap保證周遊時以Key的順序來進行排序。例如，放入的Key是"apple"、“pear”、“orange”，周遊的順序一定是"apple"、“orange”、“pear”，因為String預設按字母排序：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> map = new TreeMap<>();
        map.put("orange", 1);
        map.put("apple", 2);
        map.put("pear", 3);
        for (String key : map.keySet()) {
            System.out.println(key);
        }
        // apple, orange, pear
    }
}
           

使用TreeMap時，放入的Key必須實作Comparable接口。String、Integer這些類已經實作了Comparable接口，是以可以直接作為Key使用。作為Value的對象則沒有任何要求。

如果作為Key的class沒有實作Comparable接口，那麼，必須在建立TreeMap時同時指定一個自定義排序算法：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<Person, Integer> map = new TreeMap<>(new Comparator<Person>() {
            public int compare(Person p1, Person p2) {
                return p1.name.compareTo(p2.name);
            }
        });
        map.put(new Person("Tom"), 1);
        map.put(new Person("Bob"), 2);
        map.put(new Person("Lily"), 3);
        for (Person key : map.keySet()) {
            System.out.println(key);
        }
        // {Person: Bob}, {Person: Lily}, {Person: Tom}
        System.out.println(map.get(new Person("Bob"))); // 2
    }
}

class Person {
    public String name;
    Person(String name) {
        this.name = name;
    }
    public String toString() {
        return "{Person: " + name + "}";
    }
}
           

注意到Comparator接口要求實作一個比較方法，它負責比較傳入的兩個元素a和b，如果a<b，則傳回負數，通常是-1，如果a==b，則傳回0，如果a>b，則傳回正數，通常是1。TreeMap内部根據比較結果對Key進行排序。

從上述代碼執行結果可知，列印的Key确實是按照Comparator定義的順序排序的。如果要根據Key查找Value，我們可以傳入一個new Person(“Bob”)作為Key，它會傳回對應的Integer值2。

另外，注意到Person類并未覆寫equals()和hashCode()，因為TreeMap不使用equals()和hashCode()。

我們來看一個稍微複雜的例子：這次我們定義了Student類，并用分數score進行排序，高分在前：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<Student, Integer> map = new TreeMap<>(new Comparator<Student>() {
            public int compare(Student p1, Student p2) {
                return p1.score > p2.score ? -1 : 1;
            }
        });
        map.put(new Student("Tom", 77), 1);
        map.put(new Student("Bob", 66), 2);
        map.put(new Student("Lily", 99), 3);
        for (Student key : map.keySet()) {
            System.out.println(key);
        }
        System.out.println(map.get(new Student("Bob", 66))); // null?
    }
}

class Student {
    public String name;
    public int score;
    Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
    public String toString() {
        return String.format("{%s: score=%d}", name, score);
    }
}
           

在for循環中，我們确實得到了正确的順序。但是，且慢！根據相同的Key：new Student(“Bob”, 66)進行查找時，結果為null！

這是怎麼肥四？難道TreeMap有問題？遇到TreeMap工作不正常時，我們首先回顧Java程式設計基本規則：出現問題，不要懷疑Java标準庫，要從自身代碼找原因。

在這個例子中，TreeMap出現問題，原因其實出在這個Comparator上：

public int compare(Student p1, Student p2) {
    return p1.score > p2.score ? -1 : 1;
}
           

在p1.score和p2.score不相等的時候，它的傳回值是正确的，但是，在p1.score和p2.score相等的時候，它并沒有傳回0！這就是為什麼TreeMap工作不正常的原因：TreeMap在比較兩個Key是否相等時，依賴Key的compareTo()方法或者Comparator.compare()方法。在兩個Key相等時，必須傳回0。是以，修改代碼如下：

public int compare(Student p1, Student p2) {
    if (p1.score == p2.score) {
        return 0;
    }
    return p1.score > p2.score ? -1 : 1;
}
           

或者直接借助Integer.compare(int, int)也可以傳回正确的比較結果。

小結

SortedMap在周遊時嚴格按照Key的順序周遊，最常用的實作類是TreeMap；

作為SortedMap的Key必須實作Comparable接口，或者傳入Comparator；

要嚴格按照compare()規範實作比較邏輯，否則，TreeMap将不能正常工作。