面試了十個應屆生九個都沒用過TreeMap，你确定你們是個 Java 程式員？(2)

01、自然順序

預設情況下，TreeMap 是根據 key 的自然順序排列的。比如說整數，就是升序，1、2、3、4、5。

TreeMap<Integer,String> mapInt = new TreeMap<>();
mapInt.put(3, "沉默王二");
mapInt.put(2, "沉默王二");
mapInt.put(1, "沉默王二");
mapInt.put(5, "沉默王二");
mapInt.put(4, "沉默王二");
System.out.println(mapInt);      

輸出結果如下所示：

{1=沉默王二, 2=沉默王二, 3=沉默王二, 4=沉默王二, 5=沉默王二}

1

TreeMap 是怎麼做到的呢？想一探究竟，就得上源碼了，來看 TreeMap 的 put() 方法（省去了一部分，版本為 JDK 14）：

public V put(K key, V value) {
    TreeMap.Entry<K,V> t = root;
    int cmp;
    TreeMap.Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
    }
    else {
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    return null;
}      

注意 cmp = k.compareTo(t.key) 這行代碼，就是用來進行 key 的比較的，由于此時 key 是 int，是以就會調用 Integer 類的 compareTo() 方法進行比較。

public int compareTo(Integer anotherInteger) {
    return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
    return (x < y) ? -1 : ((x == y) ? 0 : 1);
}      

那相應的，如果 key 是字元串的話，也就會調用 String 類的 compareTo() 方法進行比較。

public int compareTo(String anotherString) {
    byte v1[] = value;
    byte v2[] = anotherString.value;
    byte coder = coder();
    if (coder == anotherString.coder()) {
        return coder == LATIN1 ? StringLatin1.compareTo(v1, v2)
                : StringUTF16.compareTo(v1, v2);
    }
    return coder == LATIN1 ? StringLatin1.compareToUTF16(v1, v2)
            : StringUTF16.compareToLatin1(v1, v2);
}      

由于内部是由字元串的位元組數組的字元進行比較的，是不是聽起來很繞？對，就是很繞，是以使用中文字元串作為 key 的話，看不出來效果。

TreeMap<String,String> mapString = new TreeMap<>();
mapString.put("c", "沉默王二");
mapString.put("b", "沉默王二");
mapString.put("a", "沉默王二");
mapString.put("e", "沉默王二");
mapString.put("d", "沉默王二");
System.out.println(mapString);      

{a=沉默王二, b=沉默王二, c=沉默王二, d=沉默王二, e=沉默王二}

字母的升序，對吧？

02、自定義排序

如果自然順序不滿足，那就可以在聲明 TreeMap 對象的時候指定排序規則。

TreeMap<Integer,String> mapIntReverse = new TreeMap<>(Comparator.reverseOrder());

mapIntReverse.put(3, "沉默王二");

mapIntReverse.put(2, "沉默王二");

mapIntReverse.put(1, "沉默王二");

mapIntReverse.put(5, "沉默王二");

mapIntReverse.put(4, "沉默王二");

System.out.println(mapIntReverse);

TreeMap 提供了可以指定排序規則的構造方法：

public TreeMap(Comparator<? super K> comparator) {

   this.comparator = comparator;

}

Comparator.reverseOrder() 傳回的是 ReverseComparator 對象，就是用來反轉順序的，非常友善。

是以，輸出結果如下所示：

{5=沉默王二, 4=沉默王二, 3=沉默王二, 2=沉默王二, 1=沉默王二}

HashMap 是無序的，插入的順序随着元素的增加會不停地變動。但 TreeMap 能夠至始至終按照指定的順序排列，這對于需要自定義排序的場景，實在是太有用了！

03、排序的好處

既然 TreeMap 的元素是經過排序的，那找出最大的那個，最小的那個，或者找出所有大于或者小于某個值的鍵來說，就友善多了。

Integer highestKey = mapInt.lastKey();
Integer lowestKey = mapInt.firstKey();
Set<Integer> keysLessThan3 = mapInt.headMap(3).keySet();
Set<Integer> keysGreaterThanEqTo3 = mapInt.tailMap(3).keySet();
System.out.println(highestKey);
System.out.println(lowestKey);
System.out.println(keysLessThan3);
System.out.println(keysGreaterThanEqTo3);      

TreeMap 考慮得很周全，恰好就提供了 lastKey()、firstKey() 這樣擷取最後一個 key 和第一個 key 的方法。

headMap() 擷取的是到指定 key 之前的 key；tailMap() 擷取的是指定 key 之後的 key（包括指定 key）。

來看一下輸出結果：

5

[1, 2]

[3, 4, 5]

04、如何選擇 Map

在學習 TreeMap 之前，我們已經學習了 HashMap 和 LinkedHashMap ，那如何從它們三個中間選擇呢？

HashMap、LinkedHashMap、TreeMap 都實作了 Map 接口，并提供了幾乎相同的功能（增删改查）。它們之間最大的差別就在于元素的順序：

HashMap 完全不保證元素的順序，添加了新的元素，之前的順序可能完全逆轉。

LinkedHashMap 預設會保持元素的插入順序。

TreeMap 預設會保持 key 的自然順序（根據 compareTo() 方法）。

來個表格吧，一目了然。

謝謝大家，下期見，同學們。