在大學的一天,我需要編寫代碼對同學的姓氏進行升序排序,姓氏是他們個人數據的關鍵。我在這上面花了很多時間。但如果我當時知道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");
運行這段代碼給我們一個錯誤:
問題在於TreeMap類在內部使用compareTo()方法比較值。您當然可以傳入一個空值,代碼將編譯。但是在運行時你會得到一個錯誤,因為該方法將在空值上調用,導致拋出NullPointerException 。
HashMap 和 TreeMap 的比較
與TreeMap不同,HashMap允許您將null存儲為鍵。該結構對所有空鍵都有一個特定的位置。HashMap之所以能夠存儲空鍵,是因為它根據哈希值確定它們的去向,而計算哈希值不需要比較。所以所有的空鍵都有它們的位置。
好了——現在您知道了當您需要按排序順序存儲值時該使用什麼,以及如何設置排序規則。
GO TO FULL VERSION