自学内容网 自学内容网

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

大家好,我是栗筝i,这篇文章是我的 “栗筝i 的 Java 技术栈” 专栏的第 021 篇文章,在 “栗筝i 的 Java 技术栈” 这个专栏中我会持续为大家更新 Java 技术相关全套技术栈内容。专栏的主要目标是已经有一定 Java 开发经验,并希望进一步完善自己对整个 Java 技术体系来充实自己的技术栈的同学。与此同时,本专栏的所有文章,也都会准备充足的代码示例和完善的知识点梳理,因此也十分适合零基础的小白和要准备工作面试的同学学习。当然,我也会在必要的时候进行相关技术深度的技术解读,相信即使是拥有多年 Java 开发经验的从业者和大佬们也会有所收获并找到乐趣。

在 Java 的集合框架中,TreeMap 是一种重要的数据结构,它基于红黑树实现,提供了有序的键值对存储方式。与 HashMap 不同,TreeMap 保证了元素的顺序性,使得我们可以在集合中按自然顺序或自定义顺序进行排序和查找。这使得 TreeMap 在需要排序的数据操作中表现出色,尤其适合处理有序的数据集合和范围查询。

TreeMap 的实现原理涉及红黑树,一种自平衡的二叉搜索树。这种树结构能够在 O(log n) 时间复杂度内完成插入、删除和查找操作。与之相比,HashMap 的操作虽然平均时间复杂度为 O(1),但不保持元素的顺序。因此,TreeMap 在需要保持键顺序的场景中显得尤为重要。

本文将深入探讨 TreeMap 的使用方法、内部原理及其源码实现。我们将从基本概念和常见操作入手,逐步分析 TreeMap 的实现细节。通过对源码的解析,您将能够深入理解 TreeMap 的工作机制,从而在实际编程中更好地利用这一强大的数据结构。无论您是 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()floorKeyceilingKeyhigherKey()只返回关联的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、查询元素

TreeMapget 方法通过调用 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、HashMapTreeMap 的实现

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、HashMapTreeMap 的线程安全性

两者均为非线程安全。若需线程安全的操作,可以使用 Collections.synchronizedMapConcurrentHashMap

3.3、SortedMap 接口

SortedMap 接口保证了键的有序性。它提供了视图(子集)和访问方法,但元素必须实现 Comparable 接口,或提供一个 Comparator 实现。TreeMapSortedMap 的唯一实现。

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 进行排序。
  • 两者都非线程安全,如果需要线程安全的操作,需使用其他线程安全的实现。

原文地址:https://blog.csdn.net/weixin_45187434/article/details/140643080

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!