深入学习 TreeMap 源码 – SuperBloom`s 小码头

在最近一次的面试中，面试官问到了对 TreeMap 的了解，因为在项目中很少用这个类，导致对这个集合类的理解很不够，今天来针对源码深入学习一下 TreeMap这个集合类。

继承体系

public class TreeMap<K,V>  
    extends AbstractMap<K,V>  
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable  
{

注意和 HashMap（直接实现 Map 接口）相比，TreeMap 额外实现了两个子接口：

SortedMap 接口，让 TreeMap 能够根据键对集合内元素排序
NavigableMap<K,V> 接口，让 TreeMap 有对集合内元素搜索的能力

这两个子接口的额外实现正代表着 TreeMap 的特点。

`SortedMap` 子接口

SortedMap 是 Java 集合框架中的一个接口，它在标准 Map 的基础上扩展了键的有序性和范围操作功能。以下是其核心功能详解：

核心功能

有序键管理

键按照自然顺序（Comparable 实现）或自定义比较器（Comparator）排序。
所有视图（如 keySet()、values()、entrySet()）的遍历均按顺序进行。

范围视图

subMap(fromKey, toKey)
返回 [fromKey, toKey) 区间的子映射（左闭右开）。
headMap(toKey)
返回键小于 toKey 的子映射。
tailMap(fromKey)
返回键大于等于 fromKey 的子映射。

边界访问

firstKey()
返回最小键（若映射为空，抛出 NoSuchElementException）。
lastKey()
返回最大键（同样需非空条件）。

有序视图覆盖

重写 keySet()、values()、entrySet()，确保返回的集合元素按键顺序排列。

使用场景

有序数据处理：如按时间戳查询日志、按分数段筛选学生。
高效范围查询：避免遍历整个集合，直接访问子映射。
首尾元素快速访问：例如获取排行榜首尾名次。

`NavigableMap<K,V>` 子接口

NavigableMap 是 SortedMap 的增强扩展，在有序映射基础上提供了更丰富的导航能力和操作灵活性。下面是这个接口提供的一些额外功能：

1. 导航方法：精准定位相邻键

NavigableMap 新增四类邻近查询方法，直接获取与目标键相邻的键值对：

Map.Entry<K,V> lowerEntry(K key);   // 严格小于
Map.Entry<K,V> floorEntry(K key);   // 小于等于
Map.Entry<K,V> ceilingEntry(K key); // 大于等于
Map.Entry<K,V> higherEntry(K key);  // 严格大于

2. 逆序操作：倒序视图与遍历

descendingMap()
返回逆序映射视图，所有导航方法的方向随之反转，便于倒序遍历：

3. 更加灵活的范围控制

精确控制边界包含性
通过 boolean 参数指定是否包含端点：

NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive);

而在 SortedMap 中，是固定左闭右开区间：

SortedMap<K,V> subMap(K fromKey, K toKey); // 等效于 fromInclusive=true, toInclusive=false

底层实现

从下面源码可以看出，不同于 HashMap 是数组+链表/红黑树，TreeMap 的底层实现是一个红黑树

private transient Entry<K,V> root;
...

static final class Entry<K,V> implements Map.Entry<K,V> {  
    K key;  
    V value;  
    Entry<K,V> left;  
    Entry<K,V> right;  
    Entry<K,V> parent;  
    boolean color = BLACK;
    ...
}

由于 TreeMap 底层是红黑树而不是数组，不能进行随机访问，所以查找、添加、删除的时间复杂度为 O(logn) 速度会比较慢。并且在插入、删除时还需要进行旋转、染色操作，更加费时。

构造方法

public TreeMap() {  
    comparator = null;  
}

public TreeMap(Comparator<? super K> comparator) {  
    this.comparator = comparator;  
}

在使用无参构造方法时，key 必须实现了 Comparable 接口、重写 compareTo() 方法。比如 String、Integer等都本身实现 Comparable，可以直接构造。
如果作为Key的class没有实现Comparable接口，那么，必须在创建TreeMap时同时指定一个 Comparator。

核心方法

put() and delete()

插入和删除节点后，通过旋转变色来维护红黑树。代码就不贴了

get()

基于二叉搜索树的特性（左子树比 root 小、右子树比 root 大），递归查找目标键，因此查找的时间复杂度为 O(logN)。

public V get(Object key) {  
    Entry<K,V> p = getEntry(key);  
    return (p==null ? null : p.value);  
}

final Entry<K,V> getEntry(Object key) {  
    // Offload comparator-based version for sake of performance  
    if (comparator != null)  
        return getEntryUsingComparator(key);  
    if (key == null)  
        throw new NullPointerException();  
    @SuppressWarnings("unchecked")  
    Comparable<? super K> k = (Comparable<? super K>) key;  
    Entry<K,V> p = root;  
    while (p != null) {  
        int cmp = k.compareTo(p.key);  
        if (cmp < 0)  
            p = p.left;  
        else if (cmp > 0)  
            p = p.right;  
        else  
            return p;  
    }  
    return null;  
}

subMap()

该方法是 NavigableMap 接口声明的一个核心方法，提供了对元素进行按照 key 进行高效范围查找的能力。

NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,  
                         K toKey,   boolean toInclusive);

应用场景

TreeMap 是一种有序的映射，它可以在保证高效性的同时，提供一些基于排序的操作。因此，TreeMap 适用于以下场景：

动态排序：需要按照键的自然顺序或者指定的比较器进行排序的场景，例如字典，排行榜，日程安排等。
- 日程安排：key 为时间，value 为日程内容。
- 游戏的纪录排行榜：key 为得分值，value 为得到该分数的玩家集合（例如 List 或 Set）。就很容易得到排序好的得分值，以及每个分段的玩家集合，方便进行对应的玩家返利。
最小/最大值查找：需要快速找到映射中最小或者最大的键或者值的场景，例如优先队列，堆，区间查询等。
范围查找：需要快速找到映射中某个范围内的所有键或者值的场景，例如范围搜索，前缀匹配，区间统计等。

LinkedHashMap v.s. TreeMap

前一篇文章我们学习了 LinkedHashMap，我们知道它是通过双向链表为 HashMap 提供了排序功能，而它的排序是基于插入顺序/访问顺序的，在本文中学习的 TreeMap 是根据 Key 的排序器来排序的。这一点是需要明确的。

因此二者的应用场景分别如下：

LinkedHashMap：需要按照访问顺序对 k-v 结构进行排序，并提供高时间性能的场景，能容忍高内存开销的场景。比如框架源码中提供的很多 LRU 缓存系统就是基于 LinkedHashMap 实现的；
TreeMap：需要根据 key 对 k-v 结构进行动态排序的场景，并且可以接受 O(log2n) 查找时间复杂度的场景，比如动态更新的排行榜