TreeMap详解

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 7.8k 阅读时长 ≈ 7 分钟

TreeMap 深度解析（基于 JDK 8）

TreeMap 是 Java 集合框架中基于红黑树实现的 Map 接口实现类，其核心特性是键的有序性—— 通过键的自然排序或定制排序维持键值对的顺序。与 HashMap 相比，TreeMap 不依赖哈希值，而是通过比较键的大小来组织数据，适用于需要有序键值对的场景。本文将从底层结构、排序机制、核心方法及红黑树平衡操作等方面，全面解析 TreeMap 的实现原理。

TreeMap 核心特性与继承关系

核心特性

  • 有序性：键值对按键的顺序（自然排序或定制排序）存储，遍历顺序为键的升序（或定制排序顺序）。
  • 无哈希冲突：基于红黑树实现，不依赖哈希值，因此不存在哈希冲突问题。
  • 键不可为 null：自然排序时，键需实现 Comparable 接口，compareTo 方法无法处理 null；定制排序时，若 Comparator 不支持 null，则键也不能为 null（否则抛出 NullPointerException）。
  • 非线程安全：多线程并发修改需手动同步（如使用 Collections.synchronizedSortedMap）。
  • 导航方法：实现 NavigableMap 接口，提供丰富的导航方法（如 ceilingKey、floorKey、subMap 等），方便范围查询。

继承关系

TreeMap

public class TreeMap<K,V> extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
  • 继承 AbstractMap：复用 Map 接口的基础实现（如 entrySet、size 等）。
  • 实现 NavigableMap：扩展 SortedMap 接口，支持导航操作（如获取大于 / 小于某键的最值）。
  • 实现 Cloneable：支持浅拷贝（复制红黑树结构，键值对对象本身不复制）。
  • 实现 Serializable：支持序列化，通过自定义 writeObject 和 readObject 保存 / 恢复红黑树结构。

底层结构：红黑树

TreeMap 的底层是红黑树—— 一种自平衡二叉搜索树（BST），通过维护节点颜色和旋转操作，确保树的高度始终为 O(log n)，从而保证增删改查的时间复杂度为 O(log n)。

红黑树的基本性质

红黑树通过以下性质维持平衡：

  1. 每个节点要么是红色，要么是黑色；
  2. 根节点是黑色；
  3. 所有叶子节点（NIL 节点，空节点）是黑色；
  4. 若一个节点是红色，则其两个子节点必为黑色（红色节点的子节点不能是红色）；
  5. 从任一节点到其所有叶子节点的路径中，黑色节点的数量相同（“黑高” 相等）。

节点结构（Entry 内部类）

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; // 节点颜色（默认黑色，红黑树初始节点为黑色）

    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
}
  • 每个节点包含键、值、左右子节点、父节点及颜色，构成红黑树的基本单元。

关键变量

private final Comparator<? super K> comparator; // 排序比较器（null 表示自然排序）
private transient Entry<K,V> root; // 红黑树的根节点
private transient int size = 0; // 键值对数量
private transient int modCount = 0; // 结构修改次数（用于迭代器的 fail-fast 机制）

排序机制：自然排序与定制排序

TreeMap 的有序性依赖于键的比较逻辑，分为两种方式：

自然排序（comparator == null）

当未指定比较器时，TreeMap 采用自然排序，要求键必须实现 Comparable 接口，通过 compareTo 方法比较大小：

// 自然排序的比较逻辑（简化）
Comparable<? super K> k = (Comparable<? super K>) key;
int cmp = k.compareTo(p.key); // 调用键的 compareTo 方法
  • 例如：Integer、String 等类已实现 Comparable，可直接作为 TreeMap 的键，按默认顺序（数字升序、字符串字典序）排列。

定制排序（comparator != null）

当传入 Comparator 时，TreeMap 按比较器的 compare 方法排序，无需键实现 Comparable：

// 定制排序的比较逻辑（简化）
Comparator<? super K> cpr = comparator;
int cmp = cpr.compare(key, t.key); // 调用比较器的 compare 方法

  • 示例：创建按字符串长度排序的 TreeMap：

    Map<String, Integer> map = new TreeMap<>((s1, s2) -> Integer.compare(s1.length(), s2.length()));

构造函数：初始化排序方式

TreeMap 提供 4 种构造函数，核心是初始化比较器（决定排序方式）。

无参构造器（自然排序）

public TreeMap() {
    comparator = null; // 无比较器，使用自然排序
}

带比较器的构造器（定制排序）

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator; // 使用指定的比较器
}

基于已有 Map 初始化

public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null; // 自然排序
    putAll(m); // 批量插入键值对（按自然排序）
}

基于 SortedMap 初始化

public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator(); // 复用原 SortedMap 的比较器
    buildFromSorted(m.size(), m.entrySet().iterator(), null, null); // 高效构建红黑树
}

核心方法解析

1. get(Object key)：查询键对应的值

通过比较键的大小遍历红黑树，找到匹配的节点。

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

final Entry<K,V> getEntry(Object key) {
    if (comparator != null) {
        return getEntryUsingComparator(key); // 定制排序查询
    }
    if (key == null) {
        throw new NullPointerException(); // 自然排序不允许 null 键
    }
    @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; // 未找到
}
  • 查询过程：从根节点开始，通过比较键的大小决定遍历左子树（键更小）或右子树（键更大），直到找到匹配节点或遍历至叶子节点（返回 null）。

2. put(K key, V value)：插入键值对

插入节点后，需通过红黑树的平衡操作（变色、旋转）维持红黑树性质。

步骤 1：定位插入位置
public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) { // 根节点为空（树为空）
        compare(key, key); // 检查 key 合法性（自然排序时非 null 且可比较）
        root = new Entry<>(key, value, null); // 根节点为黑色
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;
    // 循环找到插入位置（父节点）
    if (cpr != null) { // 定制排序
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0) {
                t = t.left;
            } else if (cmp > 0) {
                t = t.right;
            } else { // 键已存在，覆盖值
                return t.setValue(value);
            }
        } while (t != null);
    } else { // 自然排序
        if (key == null) throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0) {
                t = t.left;
            } else if (cmp > 0) {
                t = t.right;
            } else { // 键已存在，覆盖值
                return t.setValue(value);
            }
        } while (t != null);
    }
    // 创建新节点（默认红色，插入红色节点更易维持红黑树性质）
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0) {
        parent.left = e; // 插入左子树
    } else {
        parent.right = e; // 插入右子树
    }
    fixAfterInsertion(e); // 插入后平衡红黑树
    size++;
    modCount++;
    return null;
}
步骤 2：插入后平衡（fixAfterInsertion）

新节点默认为红色，可能破坏红黑树性质（如红色节点的父节点为红色），需通过变色和旋转修复。

private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED; // 新节点设为红色
    // 循环修复，直到 x 为根节点或父节点为黑色
    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // 父节点是祖父节点的左子节点
            Entry<K,V> y = rightOf(parentOf(parentOf(x))); // 叔叔节点（祖父的右子节点）
            if (colorOf(y) == RED) { // 叔叔节点为红色：变色即可
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x)); // 继续向上修复
            } else { // 叔叔节点为黑色：需要旋转
                if (x == rightOf(parentOf(x))) { // x 是父节点的右子节点：先左旋父节点
                    x = parentOf(x);
                    rotateLeft(x);
                }
                // 父节点设为黑色，祖父节点设为红色，右旋祖父节点
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else { // 父节点是祖父节点的右子节点（对称操作）
            Entry<K,V> y = leftOf(parentOf(parentOf(x))); // 叔叔节点（祖父的左子节点）
            if (colorOf(y) == RED) { // 叔叔节点为红色：变色
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else { // 叔叔节点为黑色：旋转
                if (x == leftOf(parentOf(x))) { // x 是父节点的左子节点：先右旋父节点
                    x = parentOf(x);
                    rotateRight(x);
                }
                // 父节点设为黑色，祖父节点设为红色，左旋祖父节点
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK; // 根节点必须为黑色
}
  • 旋转操作：左旋（rotateLeft）和右旋（rotateRight）用于调整树的结构，避免倾斜过度。例如，左旋将右子节点提升为父节点，原父节点变为其左子节点，维持二叉搜索树的性质。

3. remove(Object key)：删除键值对

删除节点后，需通过平衡操作维持红黑树性质，过程比插入更复杂（需处理多种子节点情况）。

步骤 1：找到要删除的节点
public V remove(Object key) {
    Entry<K,V> p = getEntry(key); // 调用 getEntry 找到节点
    if (p == null) return null;
    V oldValue = p.value;
    deleteEntry(p); // 删除节点并平衡
    return oldValue;
}
步骤 2：删除节点并平衡（deleteEntry）
private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;
    // 情况 1：节点 p 有两个子节点
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p); // 找到后继节点（右子树中最小的节点）
        p.key = s.key; // 用后继节点的值替换 p
        p.value = s.value;
        p = s; // 转为删除后继节点（后继节点最多有一个子节点）
    }
    // 情况 2：节点 p 最多有一个子节点（replacement 为非 null 的子节点，或 null）
    Entry<K,V> replacement = (p.left != null) ? p.left : p.right;
    if (replacement != null) { // 有一个子节点
        replacement.parent = p.parent; // 替换节点的父节点指向 p 的父节点
        if (p.parent == null) {
            root = replacement; // p 是根节点，替换为根
        } else if (p == p.parent.left) {
            p.parent.left = replacement; // p 是左子节点，替换为左子节点
        } else {
            p.parent.right = replacement; // p 是右子节点，替换为右子节点
        }
        p.left = p.right = p.parent = null; // 断开 p 的所有链接
        // 若 p 是黑色节点，删除后可能破坏黑高平衡，需修复
        if (p.color == BLACK) {
            fixAfterDeletion(replacement);
        }
    } else if (p.parent == null) { // 情况 3：p 是根节点且无子女
        root = null;
    } else { // 情况 4：p 是叶子节点
        if (p.color == BLACK) { // 黑色叶子节点删除后需修复
            fixAfterDeletion(p);
        }
        // 断开 p 与父节点的链接
        if (p.parent != null) {
            if (p == p.parent.left) {
                p.parent.left = null;
            } else {
                p.parent.right = null;
            }
            p.parent = null;
        }
    }
}
  • 后继节点（successor）：当节点有两个子节点时，后继节点是右子树中最小的节点（最左节点），其最多有一个右子节点，简化删除操作。
步骤 3：删除后平衡（fixAfterDeletion）

删除黑色节点可能破坏红黑树的黑高性质，需通过变色和旋转修复（过程类似插入后的平衡，但更复杂，涉及兄弟节点的处理）。

TreeMap 与其他 Map 的对比

特性 TreeMap HashMap Hashtable LinkedHashMap
底层结构 红黑树 数组 + 链表 / 红黑树 数组 + 链表 数组 + 链表 / 红黑树 + 双向链表
有序性 按键排序 无序 无序 插入 / 访问顺序
时间复杂度 O(log n) O (1)（平均） O (1)（平均） O (1)（平均）
键是否可为 null 否（自然排序） 是（最多 1 个） 否 是（最多 1 个）
线程安全 否 否 是（synchronized） 否
适用场景 有序键值对、范围查询 高效存取 旧系统兼容 需保留插入 / 访问顺序