Course Module 1 no mu - Lecture: 介紹 TreeMap 集合

在大學的一天，我需要編寫代碼對同學的姓氏進行升序排序，姓氏是他們個人數據的關鍵。我在這上面花了很多時間。但如果我當時知道TreeMap類，我會更快地完成任務。

什麼是樹圖？它是一種類似字典的數據結構，將元素存儲為鍵值對，並按鍵對它們進行排序。

在哪里以及如何使用它？好吧，用我同學的姓氏來完成同樣的作業是很理想的。如果我需要按升序存儲值，而不是編寫自己的排序算法，我所要做的就是創建一個TreeMap並將值放入其中。

它按升序對Integer和String等類型進行排序。但是，如果您想將自己的自定義類型放入 TreeMap 中，則您的類需要實現Comparable接口，以便它實現compareTo()方法，該方法指示如何對您的類的實例進行排序。


public class Person implements Comparable<Person> {
 
    private String firstName;
    private String lastName;
 
    public Person(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }
 
    public String getFirstName() {
        return firstName;
    }
 
    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }
 
  …
 
    @Override
    public int compareTo(Person person) {
        return person.getFirstName().compareTo(firstName);
    }
 
    @Override
    public String toString() {
        return "Person{" +
                "firstName='" + firstName + '\'' +
                ", lastName='" + lastName + '\'' +
                '}';
    }
}

讓我們覆蓋compareTo()方法，以便它按名字的逆字母順序對值進行排序：


TreeMap map = new TreeMap<Person, String>();
 
map.put(new Person("AA","BB"), "aa");
map.put(new Person("BB","BB"), "aa");
map.put(new Person("DD","BB"), "aa");
map.put(new Person("CC","BB"), "aa");

這些值將按以下順序存儲：


Person{firstName='DD', lastName='BB'}
Person{firstName='CC', lastName='BB'}
Person{firstName='BB', lastName='BB'}
Person{firstName='AA', lastName='BB'}

TreeMap類實現了NavigableMap接口，後者又擴展了SortedMap接口。這讓TreeMap類使用樹來按排序順序存儲值。

正如維基百科所說，樹是一種自平衡的二進制搜索結構，它在首先比較值後將數據存儲在其節點中。

簡單來說，紅黑樹是一種數據結構，如果值大於根，則將值存儲在右子樹中，如果值小於根，則存儲在左子樹中。此實現可以非常快速地查找結構中的值。

紅黑樹是自平衡的，因此它會隨著每個新值的插入而改變其結構。首先添加的值最初被認為是根，但在平衡過程中另一個值可以成為根。

好了，現在您知道什麼是TreeMap及其工作原理了。

請記住，TreeMap只能存儲其類實現Comparable接口並重寫compareTo()方法的對象。

但是，如果我們使用從各種庫加載的第三方類並且無法在其中實現Comparable怎麼辦？有一個解決方案：編寫自己的Comparator。

Comparator是一個具有 compare() 方法的接口。我們可以用它來比較對象並將它們存儲在TreeMap中。


Comparator<Person> comparator = new Comparator<Person>() {
 
    @Override
    public int compare(Person person1, Person person2) {
        return person1.getFirstName().compareTo(person2.getFirstName());
    }
};
 
 
TreeMap map = new TreeMap<Person, String>(comparator);

在此示例中，我們創建了一個自定義Comparator並將TreeMap傳遞給該類。

從 Java 8 開始，我們可以使用 lambda 表達式來編寫：


TreeMap map = new TreeMap<Person, String>((Person person1, Person person2) -> person1.getFirstName().compareTo(person2.getFirstName()));

換句話說，為了將值存儲在TreeMap中，您需要指定如何對它們進行排序。有兩種方法可以做到這一點：實施Comparable或實施您自己的Comparator。

但是，如果我們需要將null作為鍵放入TreeMap中怎麼辦？HashMap可以讓你做到這一點。是的，但是TreeMap如何處理這個問題？


TreeMap map = new TreeMap<Person, String>();
map.put (null, "Person");

運行這段代碼給我們一個錯誤：

java.base/java.util.TreeMap.put(TreeMap.java:561) 線程“main”中的異常 java.lang.NullPointerException

問題在於TreeMap類在內部使用compareTo()方法比較值。您當然可以傳入一個空值，代碼將編譯。但是在運行時你會得到一個錯誤，因為該方法將在空值上調用，導致拋出NullPointerException 。

HashMap 和 TreeMap 的比較

與TreeMap不同，HashMap允許您將null存儲為鍵。該結構對所有空鍵都有一個特定的位置。HashMap之所以能夠存儲空鍵，是因為它根據哈希值確定它們的去向，而計算哈希值不需要比較。所以所有的空鍵都有它們的位置。

好了——現在您知道了當您需要按排序順序存儲值時該使用什麼，以及如何設置排序規則。

﻿介紹 TreeMap 集合

HashMap 和 TreeMap 的比較

介紹 TreeMap 集合