TreeMap 是 Java 集合框架中的一个重要类，它实现了 Map 接口，并且保证键的有序性。TreeMap 基于红黑树（Red-Black Tree）实现，能够在 O(log n) 时间复杂度内完成元素的插入、删除和查找操作。

1. TreeMap 的基本特性

• 基于红黑树实现：TreeMap 的底层是红黑树，保证键值对按照键的自然顺序或指定的比较器排序，并且具有平衡二叉树的特性。
• 键的有序性：TreeMap 按照键的顺序（默认自然排序或自定义比较器）进行存储，保证在遍历时按照有序的方式输出键值对。
• 非线程安全：TreeMap 是非线程安全的，如果需要线程安全的实现，可以使用 Collections.synchronizedSortedMap() 来包装它。
• 不允许 null 键：TreeMap 不允许键为 null，但可以存储 null 值（前提是比较器允许）。

2. 构造函数

TreeMap 提供了多个构造函数，用于不同的初始化需求：

• 默认构造函数：

  public TreeMap() {
      comparator = null;
  }
  

  • 创建一个空的 TreeMap，使用键的自然顺序进行排序。

• 指定比较器的构造函数：

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

  • 允许用户提供自定义的比较器来定义键的排序方式。

• 使用现有 Map 初始化：

  public TreeMap(Map<? extends K, ? extends V> m) {
      putAll(m);
  }
  

  • 使用已有的 Map 初始化 TreeMap，并将其元素插入到红黑树中。

3. 数据结构

TreeMap 的核心数据结构是红黑树，通过 Entry 类来存储节点，以下是关键的数据结构：

• 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;
      // ...
  }
  

  • key 和 value 分别存储键值对。
  • left、right 和 parent 分别指向左子节点、右子节点和父节点，维护树结构。
  • color 用于标记节点的颜色（红或黑），以维持红黑树的平衡。

4. 插入元素 (put() 方法)

put() 方法用于在 TreeMap 中插入键值对，其核心逻辑如下：

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        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;
}

• 查找插入位置：通过循环查找合适的插入位置，将新节点插入到树中。
• 维持红黑树平衡：调用 fixAfterInsertion() 方法，确保红黑树的性质不被破坏。

5. 维持红黑树平衡 (fixAfterInsertion() 方法)

在插入新节点后，需要调用 fixAfterInsertion() 方法来维持红黑树的平衡，避免树变得不平衡，从而影响性能。

private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;
    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 = 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 = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;
}

• 红黑树特性：在插入新节点后，如果父节点为红色，会引起红黑树性质的破坏，需要通过重新着色和旋转来修复。
• 旋转操作：包括左旋和右旋，具体操作取决于树的结构，以确保树的平衡性。

6. 删除元素 (remove() 方法)

remove() 方法用于从 TreeMap 中删除指定的键值对，其逻辑涉及到查找要删除的节点并对红黑树进行调整，以保持平衡。

public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

• getEntry()：首先查找到要删除的节点。
• deleteEntry()：删除节点后调用该方法进行调整，以保持红黑树的平衡。

7. 总结

TreeMap 基于红黑树实现，具有键值对有序存储的特性。通过对 TreeMap 的源码分析，可以看到它在插入、删除和查找过程中，借助红黑树来保证较高的效率（O(log n) 的时间复杂度）。红黑树的自平衡特性使得 TreeMap 在面对大量数据时依然能够保持较快的操作速度，因此适用于需要按顺序存储和快速查找数据的场景。