滾雪球學Java(67)：深入理解 TreeMap：Java 中的有序鍵值映射表

在這里插入圖片描述

??咦咦咦，各位小可愛，我是你們的好伙伴——bug菌，今天又來給大家普及Java SE相關知識點了，別躲起來啊，聽我講干貨還不快點贊，贊多了我就有動力講得更嗨啦！所以呀，養成先點贊后閱讀的好習慣，別被干貨淹沒了哦~

在這里插入圖片描述

🏆本文收錄于「滾雪球學Java」專欄，專業攻堅指數級提升，助你一臂之力，帶你早日登頂🚀，歡迎大家關注&&收藏！持續更新中，up！up！up！！

環境說明：Windows 10 + IntelliJ IDEA 2021.3.2 + Jdk 1.8

文章目錄

前言
摘要
TreeMap
- 概述
- 源代碼解析
- 應用場景案例
- 優缺點分析
- - 優點
  - 缺點
- 類代碼方法介紹
- - 構造方法
  - 讀取方法
  - 寫入方法
  - 轉換方法
- 測試用例
- - 測試用例
  - 測試結果
  - 測試代碼分析
  - 性能測試
  - - 測試代碼演示
    - 測試結果
    - 測試代碼分析
- 結論
總結
- 附錄源碼
??建議/推薦你
📣關于我

前言

??在 Java 編程中，我們經常需要使用到鍵值映射表這種數據結構。其中，HashMap 是最常用的一種，它能夠以 O(1) 的時間復雜度完成插入、查找、刪除等操作。但是，HashMap 并不能對鍵進行排序，因此如果我們需要按有序方式來保存鍵值對，就需要使用到 TreeMap了。

摘要

??本篇文章將深入介紹 TreeMap 的原理、源碼實現、應用場景、優缺點以及相關測試用例。

TreeMap

概述

??TreeMap 是一種基于紅黑樹實現的有序鍵值映射表。它實現了 Map 接口，并且根據鍵的自然排序或者根據一個 Comparator 進行排序。在 TreeMap 中，鍵值對是按照鍵進行排序的，因此遍歷 TreeMap 時得到的鍵值對是有序的。

源代碼解析

TreeMap 的主要實現類是 TreeMap 類。我們來看一下它的源碼實現。

public class TreeMap<K,V> extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, java.io.Serializable {// 省略了一些常量和字段的定義public TreeMap() {comparator = null;}public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;}// 省略了一些構造方法的定義public Set<Map.Entry<K,V>> entrySet() {return new EntrySet();}// 省略了一些方法的定義}

??從代碼中可以看出，TreeMap 實現了 Map 接口和 NavigableMap 接口，并且繼承了 AbstractMap。它也提供了多個構造方法，可以根據需要選擇。

??如下是部分源碼截圖：

在這里插入圖片描述

??下面我們來看一下 TreeMap 中最重要的實現類 Entry。Entry 類表示 TreeMap 中的一個鍵值對，它包含了鍵和值兩個屬性，其中鍵是有序的。

static final class Entry<K,V> implements Map.Entry<K,V> {K key;V value;Entry<K,V> left = null;Entry<K,V> right = null;Entry<K,V> parent;boolean color = BLACK;/*** Make a new cell with given key, value, and parent, and with* {@code null} child links, and BLACK color.*/Entry(K key, V value, Entry<K,V> parent) {this.key = key;this.value = value;this.parent = parent;}// 省略了一些方法的定義
}

??Entry 類中定義了一個 boolean 類型的 color 屬性，它表示該節點的顏色，用于紅黑樹的平衡操作。Entry 類中還包含了 left、right、parent 三個指針，用于指向該節點的左子節點、右子節點和父節點。

??如下是部分源碼截圖：

在這里插入圖片描述

應用場景案例

??以下是使用 TreeMap 的一個實際案例。我們有一個成績表，需要按照學生姓名的字典序進行排序，而 TreeMap 剛好可以滿足這個需求。

import java.util.*;public class ScoreTable {public static void main(String[] args) {TreeMap<String, Integer> map = new TreeMap<>();map.put("Tom", 85);map.put("Jack", 92);map.put("Lily", 76);for (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println(entry.getKey() + " : " + entry.getValue());}}
}

運行結果如下：

Jack : 92
Lily : 76
Tom : 85

??從運行結果可以看出，TreeMap 把學生姓名按照字典序排序后輸出。

優缺點分析

以下是 TreeMap 的優缺點分析。

優點

TreeMap 可以對鍵進行排序，因此遍歷 TreeMap 時得到的鍵值對是有序的。
TreeMap 可以根據自然順序或者自定義比較器進行排序。
TreeMap 的內部實現使用紅黑樹，因此插入、查找、刪除等操作的時間復雜度為 O(log n)。

缺點

TreeMap 要求鍵是可比較的，因此不能存儲自定義對象類型的鍵。
TreeMap 的內部結構是紅黑樹，它比 HashMap 內部的哈希表結構要占用更多的內存，因此 TreeMap 的空間復雜度要高于 HashMap。
對于頻繁的插入、刪除操作，TreeMap 的效率不如 HashMap 高。

類代碼方法介紹

以下是 TreeMap 類中一些常用的方法的介紹。

構造方法

   // 構造一個空的 TreeMappublic TreeMap()// 構造一個 TreeMap，并指定一個比較器進行排序public TreeMap(Comparator<? super K> comparator)

代碼拓展

??這段代碼是 Java 中 TreeMap 類的構造函數，用于創建 TreeMap 對象。

??第一個構造函數 public TreeMap() 創建一個空的 TreeMap，沒有指定任何比較器，默認使用自然排序（即實現 Comparable 接口）。

??第二個構造函數 public TreeMap(Comparator<? super K> comparator) 創建一個 TreeMap 對象，并指定一個特定的比較器來對鍵進行排序。Comparator 參數是用于比較鍵的比較器，它可以是任何實現了 Comparator 接口的類或者 lambda 表達式。通過這個構造函數，我們可以根據自己的需要自定義排序規則。

??注意，TreeMap 的鍵必須實現 Comparable 接口或者在創建 TreeMap 時指定一個 Comparator 比較器，否則會拋出 ClassCastException 異常。

讀取方法

   // 獲取 TreeMap 的大小public int size()// 判斷 TreeMap 是否為空public boolean isEmpty()// 獲取 TreeMap 中鍵為 key 對應的值public V get(Object key)// 獲取 TreeMap 中比鍵 key 大的最小鍵值對public Map.Entry<K,V> higherEntry(K key)// 獲取 TreeMap 中比鍵 key 大的最小鍵public K higherKey(K key)// 獲取 TreeMap 中比鍵 key 小的最大鍵值對public Map.Entry<K,V> lowerEntry(K key)// 獲取 TreeMap 中比鍵 key 小的最大鍵public K lowerKey(K key)// 獲取 TreeMap 中鍵值比 key 大的最小鍵值對，如果 TreeMap 為空則返回 nullpublic Map.Entry<K,V> ceilingEntry(K key)// 獲取 TreeMap 中鍵值比 key 大的最小鍵，如果 TreeMap 為空則返回 nullpublic K ceilingKey(K key)// 獲取 TreeMap 中鍵值比 key 小的最大鍵值對，如果 TreeMap 為空則返回 nullpublic Map.Entry<K,V> floorEntry(K key)// 獲取 TreeMap 中鍵值比 key 小的最大鍵，如果 TreeMap 為空則返回 nullpublic K floorKey(K key)// 獲取 TreeMap 中最小的鍵值對public Map.Entry<K,V> firstEntry()// 獲取 TreeMap 中最小的鍵public K firstKey()// 獲取 TreeMap 中最大的鍵值對public Map.Entry<K,V> lastEntry()// 獲取 TreeMap 中最大的鍵public K lastKey()

代碼拓展

??這段代碼是 TreeMap 類中的一些常用方法，具體說明如下：

size()：返回 TreeMap 的大小（即鍵值對個數）。
isEmpty()：判斷 TreeMap 是否為空，如果為空則返回 true，否則返回 false。
get(key)：返回鍵為 key 對應的值，如果 key 不存在則返回 null。
higherEntry(key)：返回 TreeMap 中比鍵 key 大的最小鍵值對，如果不存在則返回 null。
higherKey(key)：返回 TreeMap 中比鍵 key 大的最小鍵，如果不存在則返回 null。
lowerEntry(key)：返回 TreeMap 中比鍵 key 小的最大鍵值對，如果不存在則返回 null。
lowerKey(key)：返回 TreeMap 中比鍵 key 小的最大鍵，如果不存在則返回 null。
ceilingEntry(key)：返回 TreeMap 中鍵值比 key 大的最小鍵值對，如果 TreeMap 為空則返回 null。
ceilingKey(key)：返回 TreeMap 中鍵值比 key 大的最小鍵，如果 TreeMap 為空則返回 null。
floorEntry(key)：返回 TreeMap 中鍵值比 key 小的最大鍵值對，如果 TreeMap 為空則返回 null。
floorKey(key)：返回 TreeMap 中鍵值比 key 小的最大鍵，如果 TreeMap 為空則返回 null。
firstEntry()：返回 TreeMap 中最小的鍵值對，如果 TreeMap 為空則返回 null。
firstKey()：返回 TreeMap 中最小的鍵，如果 TreeMap 為空則拋出 NoSuchElementException 異常。
lastEntry()：返回 TreeMap 中最大的鍵值對，如果 TreeMap 為空則返回 null。
lastKey()：返回 TreeMap 中最大的鍵，如果 TreeMap 為空則拋出 NoSuchElementException 異常。

??這些方法可以幫助我們操作 TreeMap 中的鍵值對，常用于查詢和遍歷操作。

寫入方法

   // 插入鍵值對public V put(K key, V value)// 刪除鍵值對public V remove(Object key)// 清空 TreeMappublic void clear()

代碼拓展

??這是針對 Java 中的 TreeMap 類進行的方法分析：

put(K key, V value): 該方法用于將指定的鍵值對插入到 TreeMap 中。如果 TreeMap 中已經有該鍵，則用新的值替換舊的值，并返回舊的值；如果 TreeMap 中沒有該鍵，則插入該鍵值對，并返回 null。
remove(Object key): 該方法用于從 TreeMap 中刪除指定的鍵及其對應的值。如果 TreeMap 中有該鍵，則刪除該鍵值對，并返回其對應的值；如果 TreeMap 中沒有該鍵，則返回 null。
clear(): 該方法用于清空 TreeMap 中的所有鍵值對。調用該方法后，TreeMap 的大小變為 0，但 TreeMap 仍然存在。

轉換方法

   // 返回 TreeMap 的副本public Object clone()// 返回 TreeMap 中鍵的有序集合public Set<K> keySet()// 返回 TreeMap 中鍵值對的集合public Set<Map.Entry<K, V>> entrySet()// 返回 TreeMap 中值的無序集合public Collection<V> values()

代碼拓展

??這段代碼是 Java 中 TreeMap 類的幾個常用方法的聲明，具體解釋如下：

public Object clone() 方法會返回一個 TreeMap 的副本，也就是一個新的 TreeMap，其中包含與原始 TreeMap 相同的鍵值對。這個方法可以用來創建原始 TreeMap 的副本，以在對副本進行操作時不影響原始 TreeMap。
public Set<K> keySet() 方法會返回 TreeMap 中所有鍵的有序集合。該方法可以用于遍歷 TreeMap 中的所有鍵。
public Set<Map.Entry<K, V>> entrySet() 方法會返回 TreeMap 中所有鍵值對的集合。集合中每個元素都是一個 Map.Entry 對象，包含鍵和相應的值。該方法可以用于遍歷 TreeMap 中的所有鍵值對。
public Collection<V> values() 方法會返回 TreeMap 中所有值的無序集合。該方法可以用于遍歷 TreeMap 中的所有值。

??需要注意的是，TreeMap 的鍵必須是可比較的對象，并且按照鍵的自然順序進行排序。如果要使用自定義比較器對鍵進行排序，可以使用 TreeMap 的另一個構造函數，該構造函數接受一個實現了 Comparator 接口的比較器對象作為參數。

測試用例

以下是針對 TreeMap 的測試用例。

測試用例

測試 TreeMap 的基本操作，包括插入、刪除和遍歷。

package com.demo.javase.day67;import java.util.Map;
import java.util.TreeMap;/*** @Author bug菌* @Date 2023-11-06 12:10*/
public class TreeMapTest {public static void main(String[] args) {TreeMap<String, Integer> map = new TreeMap<>();map.put("Tom", 85);map.put("Jack", 92);map.put("Lily", 76);map.put("Bob", 88);System.out.println("Initial TreeMap:");for (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println(entry.getKey() + " : " + entry.getValue());}map.remove("Lily");System.out.println("\nAfter removing Lily:");for (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println(entry.getKey() + " : " + entry.getValue());}}
}

測試結果

??根據如上測試用例，本地測試結果如下，僅供參考，你們也可以自行修改測試用例或者添加更多的測試數據或測試方法，進行熟練學習以此加深理解。

運行結果如下：

Initial TreeMap:
Jack : 92
Lily : 76
Bob : 88
Tom : 85After removing Lily:
Bob : 88
Jack : 92
Tom : 85

具體執行截圖如下：

在這里插入圖片描述

測試代碼分析

??根據如上測試用例，在此我給大家進行深入詳細的解讀一下測試代碼，以便于更多的同學能夠理解并加深印象。

??此代碼是一個簡單的關于 TreeMap 的使用示例。 TreeMap 是基于紅黑樹實現的，可以保證有序性，且插入、刪除、查找的時間復雜度是 O(log n)。

??該代碼創建了一個 TreeMap 對象，鍵類型為 String，值類型為 Integer。然后向 TreeMap 中添加了四個鍵值對。接著打印出初始 TreeMap 中的所有鍵值對。再移除 key 為 “Lily” 的鍵值對，最后再次打印出移除后的 TreeMap 中的所有鍵值對。

運行結果如下：

Initial TreeMap:
Jack : 92
Lily : 76
Bob : 88
Tom : 85

After removing Lily:
Bob : 88
Jack : 92
Tom : 85

??可以看到，初始 TreeMap 中所有鍵值對的順序是按照鍵的自然順序進行排序的（即按照字母順序）。而移除 key 為 “Lily” 的鍵值對后，再次打印出的所有鍵值對的順序仍然是有序的。這證明 TreeMap 確實有序，且移除操作也能保持 TreeMap 的順序性。

性能測試

測試 TreeMap 的性能，包括插入、查找和刪除操作的時間消耗。

測試代碼演示

package com.demo.javase.day67;import java.util.TreeMap;/*** @Author bug菌* @Date 2023-11-06 12:12*/
public class TreeMapPerformanceTest {private static final int SIZE = 1000000;public static void main(String[] args) {System.out.println("TreeMap Performance Test:");System.out.println("-------------------------");TreeMap<Integer, Integer> map = new TreeMap<>();// Insert testlong start = System.currentTimeMillis();for (int i = 0; i < SIZE; i++) {map.put(i, i);}long end = System.currentTimeMillis();System.out.println("Insert " + SIZE + " elements time: " + (end - start) + "ms");// Search teststart = System.currentTimeMillis();for (int i = 0; i < SIZE; i++) {map.get(i);}end = System.currentTimeMillis();System.out.println("Search " + SIZE + " elements time: " + (end - start) + "ms");// Delete teststart = System.currentTimeMillis();for (int i = 0; i < SIZE; i++) {map.remove(i);}end = System.currentTimeMillis();System.out.println("Delete " + SIZE + " elements time: " + (end - start) + "ms");}
}

測試結果

??根據如上測試用例，本地測試結果如下，僅供參考，你們也可以自行修改測試用例或者添加更多的測試數據或測試方法，進行熟練學習以此加深理解。

運行結果如下：

TreeMap Performance Test:
-------------------------
Insert 1000000 elements time: 148ms
Search 1000000 elements time: 64ms
Delete 1000000 elements time: 65ms

在這里插入圖片描述

測試代碼分析

??根據如上測試用例，在此我給大家進行深入詳細的解讀一下測試代碼，以便于更多的同學能夠理解并加深印象。

??這是一個測試TreeMap性能的Java程序，主要進行了三項測試：

插入測試：向TreeMap中插入1000000個元素，并記錄時間；
查找測試：在TreeMap中查找1000000個元素，并記錄時間；
刪除測試：從TreeMap中刪除1000000個元素，并記錄時間。

??通過這些測試，可以評估TreeMap在插入、查找和刪除操作時的性能。

結論

??本文對 Java 中的有序鍵值映射表 TreeMap 進行了詳細的介紹。我們講解了 TreeMap 的原理、源碼實現、應用場景、優缺點以及相關測試用例。通過本文的學習，我們能夠更加深入地理解 TreeMap，以及在實際開發中如何正確地使用它。

總結

??本篇文章主要介紹了 Java 中的有序鍵值映射表 TreeMap，包括其原理、源碼實現、應用場景、優缺點以及相關測試用例。從文章中可以了解到，TreeMap 是一種基于紅黑樹實現的有序鍵值映射表，可以根據鍵進行排序，遍歷 TreeMap 時得到的鍵值對是有序的。同時，TreeMap 的內部實現使用紅黑樹，因此插入、查找、刪除等操作的時間復雜度為 O(log n)。文章還提供了針對 TreeMap 的測試用例，對其進行性能測試，以評估 TreeMap 在插入、查找和刪除操作時的性能。

??…
??好啦，這期的內容就基本接近尾聲啦，若你想學習更多，可以參考這篇專欄總結《「滾雪球學Java」教程導航帖》，本專欄致力打造最硬核 Java 零基礎系列學習內容，🚀打造全網精品硬核專欄，帶你直線超車；歡迎大家訂閱持續學習。