Java 集合框架：TreeMap 的介绍、使用、原理与源码解析

1、treemap 概述

1.1、treemap 介绍

map 在 java 里面分为两种：hashmap 和 treemap，区别就是 treemap 有序，hashmap 无序。如果只需要存映射，那么 hashmap 就够了，但是如果需要存有顺序的 key 那么就用 treemap。

treemap 存储 k-v 键值对，通过红黑树（r-b tree）实现。treemap 继承了 navigablemap 接口，navigablemap 接口继承了 sortedmap 接口，可支持一系列的导航定位以及导航操作的方法，当然只是提供了接口，需要 treemap 自己去实现；treemap 实现了 cloneable 接口，可被克隆，实现了 serializable 接口，可序列化；treemap 因为是通过红黑树实现，红黑树结构天然支持排序，默认情况下通过 key 值的自然顺序进行排序。

treemap 是一个能比较元素大小的 map 集合，会对传入的 key 进行了大小排序。可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序。

treemap 的特点：

1. treemap 是有序的 key-value 集合，通过红黑树实现。根据键的自然顺序进行排序或根据提供的 comparator 进行排序。
2. treemap 继承了 abstractmap，实现了 navigablemap 接口，支持一系列的导航方法，给定具体搜索目标，可以返回最接近的匹配项。如 floorentry()、ceilingentry() 分别返回小于等于、大于等于给定键关联的 map.entry() 对象，不存在则返回 null。lowerkey()、floorkey、ceilingkey、higherkey()只返回关联的key。

1.2、红黑树回顾

红⿊树和 avl 树 类似，都是在进⾏插⼊和删除时通过旋转保持⾃身平衡，从⽽获得较⾼的查找性能。与 avl 树 相⽐，红⿊树不追求所有递归⼦树的⾼度差不超过 1，保证从根节点到叶尾的最⻓路径不超过最短路径的 2 倍，所以最差时间复杂度是 o(logn)。

红⿊树通过重新着⾊和左右旋转，更加⾼效地完成了插⼊和删除之后的⾃平衡调整。红⿊树在本质上还是⼆叉查找树，它额外引⼊了 5 个约束条件： ① 节点只能是红⾊或⿊⾊。 ② 根节点必须是⿊⾊。 ③ 所有 nil 节点都是⿊⾊的。 ④ ⼀条路径上不能出现相邻的两个红⾊节点。 ⑤ 在任何递归⼦树中，根节点到叶⼦节点的所有路径上包含相同数⽬的⿊⾊节点。

这五个约束条件保证了红⿊树的新增、删除、查找的最坏时间复杂度均为 o(logn)。如果⼀个树的左⼦节点或右⼦节点不存在，则均认定为⿊⾊。红⿊树的任何旋转在 3 次之内均可完成。

2、treemap 底层实现

2.1、treemap 底层结构

treemap 类是一个基于红黑树的实现，treemap 维护了键的有序性。提供了几种构造函数来初始化映射，包括使用自然顺序、指定比较器、从已有映射构造等。内部的 entry 类表示树中的节点，每个节点包含了键、值、子节点和父节点的引用，以及节点的颜色标记（红黑树特性）。

public class treemap<k,v>
    extends abstractmap<k,v>
    implements navigablemap<k,v>, cloneable, java.io.serializable
{
    /**
     * 用于维护树映射中顺序的比较器，如果为 null，则使用键的自然顺序。
     *
     * @serial
     */
    private final comparator<? super k> comparator;

    private transient entry<k,v> root; // 树的根节点，使用 transient 以防序列化

    /**
     * 树中的条目数量
     */
    private transient int size = 0;

    /**
     * 树的结构性修改次数
     */
    private transient int modcount = 0;

    /**
     * 构造一个新的空的树映射，使用键的自然顺序。所有插入到映射中的键必须实现 {@link comparable} 接口。
     * 此外，所有这些键必须是 <em>相互可比较</em>：{@code k1.compareto(k2)} 对于映射中的任何键 {@code k1} 和 {@code k2}
     * 不得抛出 {@code classcastexception}。如果用户尝试将一个违反此约束的键插入到映射中（例如，用户尝试
     * 将字符串键插入到一个键为整数的映射中），{@code put(object key, object value)} 调用将抛出 {@code classcastexception}。
     */
    public treemap() {
        comparator = null;
    }

    /**
     * 构造一个新的空的树映射，按照给定的比较器排序。所有插入到映射中的键必须通过给定的比较器进行 <em>相互可比较</em>：
     * {@code comparator.compare(k1, k2)} 对于映射中的任何键 {@code k1} 和 {@code k2} 不得抛出 {@code classcastexception}。
     * 如果用户尝试将一个违反此约束的键插入到映射中，{@code put(object key, object value)} 调用将抛出 {@code classcastexception}。
     *
     * @param comparator 用于排序此映射的比较器。如果 {@code null}，则使用 {@linkplain comparable 自然顺序}。
     */
    public treemap(comparator<? super k> comparator) {
        this.comparator = comparator;
    }

    /**
     * 构造一个新的树映射，包含与给定映射相同的映射，根据键的 <em>自然顺序</em> 进行排序。
     * 所有插入到新映射中的键必须实现 {@link comparable} 接口。此外，所有这些键必须是 <em>相互可比较</em>：
     * {@code k1.compareto(k2)} 对于映射中的任何键 {@code k1} 和 {@code k2} 不得抛出 {@code classcastexception}。
     * 此方法的运行时间为 n*log(n)。
     *
     * @param  m 要放置在此映射中的映射
     * @throws classcastexception 如果 m 中的键不是 {@link comparable}，或不是相互可比较的
     * @throws nullpointerexception 如果指定的映射为 null
     */
    public treemap(map<? extends k, ? extends v> m) {
        comparator = null;
        putall(m);
    }

    /**
     * 构造一个新的树映射，包含与指定的排序映射相同的映射，并使用相同的排序。
     * 此方法的运行时间为线性时间。
     *
     * @param  m 要放置在此映射中的排序映射，及其比较器将用于排序此映射
     * @throws nullpointerexception 如果指定的映射为 null
     */
    public treemap(sortedmap<k, ? extends v> m) {
        comparator = m.comparator();
        try {
            buildfromsorted(m.size(), m.entryset().iterator(), null, null);
        } catch (java.io.ioexception cannothappen) {
        } catch (classnotfoundexception cannothappen) {
        }
    }
}

entry 类:表示树中的一个节点，包含键、值、左右子节点和父节点的引用。提供了基本的 map.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; // 节点颜色，红黑树的颜色标记

    /**
     * 创建一个具有给定键、值和父节点的新的节点，并且子节点链接为 {@code null}，颜色为黑色。
     */
    entry(k key, v value, entry<k,v> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }

    /**
     * 返回键。
     *
     * @return 键
     */
    public k getkey() {
        return key;
    }

    /**
     * 返回与键关联的值。
     *
     * @return 与键关联的值
     */
    public v getvalue() {
        return value;
    }

    /**
     * 用给定的值替换当前与键关联的值。
     *
     * @return 调用此方法之前与键关联的值
     */
    public v setvalue(v value) {
        v oldvalue = this.value;
        this.value = value;
        return oldvalue;
    }

    public boolean equals(object o) {
        if (!(o instanceof map.entry))
            return false;
        map.entry<?,?> e = (map.entry<?,?>)o;

        return valequals(key,e.getkey()) && valequals(value,e.getvalue());
    }

    public int hashcode() {
        int keyhash = (key==null ? 0 : key.hashcode());
        int valuehash = (value==null ? 0 : value.hashcode());
        return keyhash ^ valuehash;
    }

    public string tostring() {
        return key + "=" + value;
    }
}

2.2、添加元素

put 方法在 treemap 中用于插入或更新键值对。首先，它检查树是否为空，若为空则创建一个新根节点。如果树非空，它根据提供的比较器或自然排序路径遍历树，找到适合插入的位置。如果键已存在，则更新对应的值。插入新节点后，调用 fixafterinsertion 方法修复树的结构以维持红黑树的平衡性，并更新树的大小和结构修改次数。

/**
 * 将指定的值与指定的键关联在此映射中。
 * 如果映射中之前包含该键的映射，则替换旧值。
 *
 * @param key 与指定的值关联的键
 * @param value 要与指定键关联的值
 *
 * @return 之前与 {@code key} 关联的值，如果 {@code key} 没有映射，则返回 {@code null}。
 *         （{@code null} 的返回值也可能表示映射中之前与 {@code key} 关联了 {@code null}。）
 * @throws classcastexception 如果指定的键无法与当前映射中的键进行比较
 * @throws nullpointerexception 如果指定的键为 {@code null} 并且此映射使用自然排序，或其比较器
 *         不允许 {@code null} 键
 */
public v put(k key, v value) {
    // 获取树的根节点
    entry<k,v> t = root;

    // 如果树为空，则插入新的根节点
    if (t == null) {
        // 检查键的类型（以及可能的 null 值）
        compare(key, key);

        // 创建一个新的根节点
        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();  // 不允许 null 键

        @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 方法用于在 treemap 中插入新节点后修复红黑树的平衡性。它通过调整节点颜色和旋转操作来维护红黑树的性质，确保树的高度平衡。具体来说，当插入节点的父节点为红色时，根据其叔父节点的颜色和位置，进行节点颜色调整和必要的旋转操作，最后确保根节点始终为黑色。

/**
 * 插入节点后的修复方法，用于保持红黑树的平衡性。
 * 
 * @param x 插入的节点
 */
private void fixafterinsertion(entry<k,v> x) {
    // 将新插入节点的颜色设为红色
    x.color = red;

    // 当 x 节点存在且不是根节点，且 x 节点的父节点是红色时
    while (x != null && x != root && x.parent.color == red) {
        // 如果 x 节点的父节点是祖父节点的左子节点
        if (parentof(x) == leftof(parentof(parentof(x)))) {
            // 获取 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 节点继续修复
                x = parentof(parentof(x));
            } else {
                // 如果 x 节点是其父节点的右子节点
                if (x == rightof(parentof(x))) {
                    // 将 x 节点的父节点作为新的 x 节点，进行左旋操作
                    x = parentof(x);
                    rotateleft(x);
                }
                // 将父节点设为黑色，祖父节点设为红色，进行右旋操作
                setcolor(parentof(x), black);
                setcolor(parentof(parentof(x)), red);
                rotateright(parentof(parentof(x)));
            }
        } else { // 如果 x 节点的父节点是祖父节点的右子节点
            // 获取 x 节点的叔父节点（祖父节点的左子节点）
            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 节点继续修复
                x = parentof(parentof(x));
            } else {
                // 如果 x 节点是其父节点的左子节点
                if (x == leftof(parentof(x))) {
                    // 将 x 节点的父节点作为新的 x 节点，进行右旋操作
                    x = parentof(x);
                    rotateright(x);
                }
                // 将父节点设为黑色，祖父节点设为红色，进行左旋操作
                setcolor(parentof(x), black);
                setcolor(parentof(parentof(x)), red);
                rotateleft(parentof(parentof(x)));
            }
        }
    }
    // 将根节点的颜色设为黑色
    root.color = black;
}

2.3、删除元素

treemap 的删除操作包括三个主要步骤：首先，通过 getentry 方法查找指定键的节点。如果节点存在，调用 deleteentry 方法删除该节点。在删除过程中，如果节点有两个子节点，将其替换为后继节点；如果只有一个子节点或没有子节点，则直接更新父节点的链接，并处理可能引发的树结构不平衡问题，最终确保红黑树的性质。删除操作完成后，更新树的大小和修改计数器。

static final class entry<k,v> implements map.entry<k,v> {
    public v remove(object key) {
        treemap.entry<k,v> p = getentry(key); // 查找指定键对应的节点
        if (p == null)
            return null; // 如果找不到节点，返回 null

        v oldvalue = p.value; // 记录旧值
        deleteentry(p); // 删除节点
        return oldvalue; // 返回被删除节点的值
    }

    /**
     * 删除 treemap 中所有的映射，清空 map。
     * 调用此方法后，map 为空。
     */
    public void clear() {
        modcount++; // 增加修改计数
        size = 0; // 清空大小
        root = null; // 设置根节点为 null
    }

    /**
     * 删除节点 p，并重新平衡树。
     */
    private void deleteentry(treemap.entry<k,v> p) {
        modcount++; // 增加修改计数
        size--; // 减少元素数量

        // 如果节点 p 有两个子节点
        if (p.left != null && p.right != null) {
            treemap.entry<k,v> s = successor(p); // 找到 p 的后继节点
            p.key = s.key; // 用后继节点的键替换当前节点的键
            p.value = s.value; // 用后继节点的值替换当前节点的值
            p = s; // 将 p 指向后继节点
        } // p 现在只有一个子节点或没有子节点

        treemap.entry<k,v> replacement = (p.left != null ? p.left : p.right); // 确定替换节点

        if (replacement != null) {
            // 将替换节点链接到 p 的父节点
            replacement.parent = p.parent;
            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 的链接以便后续修复使用
            p.left = p.right = p.parent = null;

            // 修复替换节点
            if (p.color == black)
                fixafterdeletion(replacement);
        } else if (p.parent == null) { // 如果节点 p 是唯一的节点
            root = null; // 设置根节点为 null
        } else { // 节点 p 没有子节点
            if (p.color == black)
                fixafterdeletion(p); // 修复删除操作后的树结构

            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null; // 更新父节点的左子节点
                else if (p == p.parent.right)
                    p.parent.right = null; // 更新父节点的右子节点
                p.parent = null; // 清除父节点
            }
        }
    }
}

2.4、查询元素

treemap 的 get 方法通过调用 getentry 查找指定键的 entry 节点。getentry 根据是否使用比较器来决定使用哪种查找策略：若使用比较器，则调用 getentryusingcomparator 进行查找；否则，通过比较键的自然顺序在树中遍历。最终，get 返回找到的节点的值，或在键不存在时返回 null。

static final class entry<k,v> implements map.entry<k,v> {
	  /**
     * 根据指定的键获取对应的值。
     * 如果树中存在该键，则返回对应的值；否则返回 null。
     *
     * @param key 要查找的键
     * @return 如果键存在，则返回与键对应的值；否则返回 null
     */
    public v get(object key) {
        treemap.entry<k,v> p = getentry(key);
        return (p == null ? null : p.value);
    }

    /**
     * 返回该映射中给定键的条目，如果该键不存在，则返回 {@code null}。
     *
     * @param key 要查找的键
     * @return 该映射中给定键的条目，如果该键不存在，则返回 {@code null}
     * @throws classcastexception 如果指定的键无法与当前映射中的键进行比较
     * @throws nullpointerexception 如果指定的键为 null 并且该映射使用自然排序，或者其比较器不允许 null 键
     */
    final treemap.entry<k,v> getentry(object key) {
        // 针对使用比较器的版本进行优化以提高性能
        if (comparator != null)
            return getentryusingcomparator(key);
        if (key == null)
            throw new nullpointerexception();
        @suppresswarnings("unchecked")
        comparable<? super k> k = (comparable<? super k>) key;
        treemap.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;
    }

    /**
     * 使用比较器版本的 getentry 方法。为了性能优化，单独分离出来。
     *
     * @param key 要查找的键
     * @return 给定键的条目，如果该键不存在，则返回 {@code null}
     */
    final treemap.entry<k,v> getentryusingcomparator(object key) {
        @suppresswarnings("unchecked")
        k k = (k) key;
        comparator<? super k> cpr = comparator;
        if (cpr != null) {
            treemap.entry<k,v> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
    }
}

3、treemap 相关知识点

3.1、hashmap 和 treemap 的实现

hashmap:

• 基于哈希表实现。
• 键需要实现 hashcode() 和 equals() 方法（可以重写）。
• 支持通过调节初始容量和负载因子来优化空间使用。
• 构造方法：
  • hashmap(): 构建一个空的哈希映射。
  • hashmap(map m): 构建一个哈希映射，并添加映射 m 的所有映射。
  • hashmap(int initialcapacity): 构建一个具有特定容量的空哈希映射。
  • hashmap(int initialcapacity, float loadfactor): 构建一个具有特定容量和负载因子的空哈希映射。

treemap:

• 基于红黑树实现。
• 自动保持树的平衡状态，无需手动调整。
• 构造方法：
  • treemap(): 构建一个空的映射树。
  • treemap(map m): 构建一个映射树，并添加映射 m 中的所有元素。
  • treemap(comparator c): 构建一个映射树，并使用特定的比较器对键进行排序。
  • treemap(sortedmap s): 构建一个映射树，并添加映射树 s 中的所有映射，使用与 s 相同的比较器排序。

3.2、hashmap 和 treemap 的线程安全性

两者均为非线程安全。若需线程安全的操作，可以使用 collections.synchronizedmap 或 concurrenthashmap。

3.3、sortedmap 接口

sortedmap 接口保证了键的有序性。它提供了视图（子集）和访问方法，但元素必须实现 comparable 接口，或提供一个 comparator 实现。treemap 是 sortedmap 的唯一实现。

3.4、自定义比较器实现降序排序

通过实现 comparator 接口，可以定义自定义比较器来控制 treemap 的排序方式。例如，以下代码演示了如何实现降序排序：

import java.util.*;

public class maptest {

    public static void main(string[] args) {
        // 初始化自定义比较器
        mycomparator comparator = new mycomparator();
        // 初始化一个map集合
        map<string, string> map = new treemap<>(comparator);
        // 存入数据
        map.put("a", "a");
        map.put("b", "b");
        map.put("f", "f");
        map.put("d", "d");
        map.put("c", "c");
        map.put("g", "g");
        // 遍历输出
        iterator<string> iterator = map.keyset().iterator();
        while (iterator.hasnext()) {
            string key = iterator.next();
            system.out.println(map.get(key));
        }
    }

    static class mycomparator implements comparator<string> {
        @override
        public int compare(string o1, string o2) {
            // 反向比较实现降序排序
            return -o1.compareto(o2);
        }
    }
}

总结：

• hashmap 提供快速的查找、插入和删除操作，适用于无序数据；而 treemap 提供有序的键值对存储，支持范围查找和排序操作。
• hashmap 需要正确实现 hashcode() 和 equals()，treemap 需要实现 comparable 接口或提供 comparator 进行排序。
• 两者都非线程安全，如果需要线程安全的操作，需使用其他线程安全的实现。