Java TreeMap

TreeMap 是基於紅黑樹的 NavigableMap 實作，元素會依照 key 自動排序。

引入套件

import java.util.TreeMap;

建立 TreeMap

// 自然排序
TreeMap<String, Integer> map1 = new TreeMap<>();

// 自訂排序（反向）
TreeMap<String, Integer> map2 = new TreeMap<>(Comparator.reverseOrder());

// 從其他 Map 建立
TreeMap<String, Integer> map3 = new TreeMap<>(existingMap);

基本操作

TreeMap<String, Integer> map = new TreeMap<>();

map.put("Cherry", 3);
map.put("Apple", 1);
map.put("Banana", 2);

// 自動按 key 排序
System.out.println(map);  // {Apple=1, Banana=2, Cherry=3}

// 取得值
Integer value = map.get("Apple");  // 1

導航方法

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "A");
map.put(3, "C");
map.put(5, "E");
map.put(7, "G");

// 第一個和最後一個
Integer first = map.firstKey();   // 1
Integer last = map.lastKey();     // 7

// 小於/大於指定 key
Integer lower = map.lowerKey(5);   // 3（< 5）
Integer higher = map.higherKey(5); // 7（> 5）
Integer floor = map.floorKey(4);   // 3（<= 4）
Integer ceiling = map.ceilingKey(4); // 5（>= 4）

// 取得並移除
Map.Entry<Integer, String> firstEntry = map.pollFirstEntry();
Map.Entry<Integer, String> lastEntry = map.pollLastEntry();

範圍操作

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");
map.put(4, "D");
map.put(5, "E");

// 子 Map（2 到 4，含2不含4）
SortedMap<Integer, String> sub = map.subMap(2, 4);
System.out.println(sub);  // {2=B, 3=C}

// 子 Map（含兩端）
NavigableMap<Integer, String> sub2 = map.subMap(2, true, 4, true);
System.out.println(sub2);  // {2=B, 3=C, 4=D}

// 小於指定 key
SortedMap<Integer, String> head = map.headMap(3);
System.out.println(head);  // {1=A, 2=B}

// 大於等於指定 key
SortedMap<Integer, String> tail = map.tailMap(3);
System.out.println(tail);  // {3=C, 4=D, 5=E}

// 反向
NavigableMap<Integer, String> desc = map.descendingMap();
System.out.println(desc);  // {5=E, 4=D, 3=C, 2=B, 1=A}

自訂排序

// 依照字串長度排序
TreeMap<String, Integer> map = new TreeMap<>(
    Comparator.comparingInt(String::length)
);

map.put("AAA", 3);
map.put("A", 1);
map.put("AA", 2);

System.out.println(map);  // {A=1, AA=2, AAA=3}

HashMap vs TreeMap

實用範例

成績排名

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

scores.computeIfAbsent(90, k -> new ArrayList<>()).add("Alice");
scores.computeIfAbsent(85, k -> new ArrayList<>()).add("Bob");
scores.computeIfAbsent(90, k -> new ArrayList<>()).add("Charlie");

// 按分數高到低
scores.forEach((score, names) -> 
    System.out.println(score + ": " + names)
);
// 90: [Alice, Charlie]
// 85: [Bob]

重點整理

• TreeMap 依照 key 自動排序
• 基於紅黑樹，操作為 O(log n)
• 提供豐富的導航方法（first, last, lower, higher...）
• 支援範圍查詢（subMap, headMap, tailMap）
• key 不能為 null
• 需要排序或範圍查詢時使用