TreeMap源码详解

TreeMap 是 Java Collections Framework 中的一个重要部分，它实现了 NavigableMap 接口，并使用红黑树作为底层数据结构。TreeMap 的特点是按照键的自然顺序或者根据指定的比较器进行排序。接下来，我们将深入分析 TreeMap 的源码及其核心功能。

TreeMap 的基本结构

首先，TreeMap 的核心是其节点类 TreeMap.Entry。每个节点包含以下几个字段： - key：存储键 - value：存储值 - left 和 right：分别指向左子节点和右子节点 - parent：指向父节点 - color：节点的颜色，用于红黑树的平衡

以下是 TreeMap.Entry 的简化代码示例：

static final class Entry<K, V> extends AbstractMap.SimpleEntry<K, V> {
    Entry<K, V> left, right, parent;
    boolean color = RED;

    Entry(K key, V value, Entry<K, V> parent) {
        super(key, value);
        this.parent = parent;
    }
}

TreeMap 的构造

当创建一个新的 TreeMap 实例时，可以指定一个比较器或使用自然顺序。TreeMap 的构造函数大致如下：

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
    this.tree = null; // 初始时树为空
    this.size = 0; // 初始化大小为零
}

添加元素

向 TreeMap 中添加元素的主要方法是 put，其核心逻辑是通过比较键的顺序来维护红黑树的性质。具体的插入过程涉及多个步骤：

1. 找到插入位置：通过比较键值，沿着树向下查找。
2. 插入节点：在找到的叶子节点位置上插入新节点。
3. 调整红黑树：根据规则调整树的颜色和结构，以保证红黑树的特性。

以下是 put 方法的简化实现：

public V put(K key, V value) {
    return putVal(root, key, value, false, true);
}

private V putVal(Entry<K,V> root, K key, V value, boolean replace, boolean notNull) {
    Entry<K,V> p = root;
    if (p == null) {
        // 创建根节点
        this.tree = new Entry<>(key, value, null);
        size++;
        return null;
    }
    // 这里是查找合适插入位置的逻辑
    // ...

    // 插入后进行调整
    fixAfterInsertion(newEntry);
}

删除元素

TreeMap 的删除操作同样复杂，涉及到的步骤有查找要删除的节点、去掉节点后重新连接树结构、以及调整树，使其重新符合红黑树的性质。

public V remove(Object key) {
    Entry<K,V> p = getEntry(key); // 首先查找键值
    if (p == null) return null;

    V oldValue = p.value;
    // 进行删除操作
    if (p.left != null && p.right != null) {
        // 两个子节点的情况
        // 找到后继节点，替换并删除后继节点
    } else {
        // 只有一个或零个子节点的情况
    }

    fixAfterRemoval(p); // 删除后重新平衡
    return oldValue;
}

总结

TreeMap 作为一种基于红黑树的实现，提供了高效的键值对存储与检索功能。通过其有序性，可以实现许多复杂的数据结构操作，如范围查找、用户自定义排序等。虽然底层实现较为复杂，但对开发者而言，TreeMap 提供了一种优雅的 API，使得数据结构的使用变得简单与高效。通过理解其源码，开发者可以更牢固地掌握 Java 中数据结构的运作机制。