使用Java之TreeMap，轻松实现高效有序映射！有两下子！

原创

bug菌

发布于 2024-08-15 09:06:41

890

发布于 2024-08-15 09:06:41

文章被收录于专栏：滚雪球学Java

咦咦咦，各位小可爱，我是你们的好伙伴——bug菌，今天又来给大家普及Java SE相关知识点了，别躲起来啊，听我讲干货还不快点赞，赞多了我就有动力讲得更嗨啦！所以呀，养成先点赞后阅读的好习惯，别被干货淹没了哦~

🏆本文收录于「滚雪球学Java」专栏中，这个专栏专为有志于提升Java技能的你打造，覆盖Java编程的方方面面，助你从零基础到掌握Java开发的精髓。赶紧关注，收藏，学习吧！

环境说明：Windows 10 + IntelliJ IDEA 2021.3.2 + Jdk 1.8

前言

在Java开发中，数据的有序存储和高效查找是两个非常关键的需求。无论是在配置管理、数据索引，还是在实现缓存机制中，有序存储都能大大提升程序的可读性和性能。TreeMap 是Java集合框架中一个重要的实现类，专门用于处理有序的键值对映射。通过TreeMap，我们可以轻松实现高效的有序映射操作，确保数据在插入后能够自动排序，方便后续的查找和操作。本文将全面探讨TreeMap的使用与优化策略，帮助你在Java开发中更加游刃有余。

摘要

本文深入解析了Java中的TreeMap，探讨其底层实现、性能特性及最佳应用场景。通过对TreeMap的核心源码解读和实际案例分析，本文将帮助读者理解如何高效地操作有序映射。我们将展示TreeMap在排序、范围查询等方面的优势，并通过代码示例和测试用例，深入分析TreeMap的应用效果。最后，文章将总结TreeMap的优缺点，并提供最佳实践建议，助力开发者在Java开发中充分利用TreeMap的强大功能。

简介

TreeMap 是Java集合框架中的一个重要实现，它基于红黑树结构实现，能够自动维护键值对的顺序。这种特性使得TreeMap非常适用于需要按键的自然顺序或自定义顺序存储和操作数据的场景。与HashMap不同，TreeMap不仅支持高效的查找和插入操作，还能确保数据的有序性。

什么是`TreeMap`？

有序映射：TreeMap是一个基于红黑树的有序映射类，它能够保证所有的键值对按键的自然顺序或指定的顺序存储。
自动排序：在插入数据时，TreeMap会自动对键进行排序，确保任何时候取出的数据都是有序的。

为什么使用`TreeMap`？

TreeMap 适用于需要维护键值对顺序的场景，如排序操作、范围查询、按顺序迭代等。通过使用TreeMap，我们可以轻松实现从数据插入到有序查找的一体化操作，大大简化开发流程。

概述

TreeMap 是基于红黑树实现的，红黑树是一种自平衡二叉搜索树，能够在插入、删除和查找操作中保持O(log n)的时间复杂度。与HashMap不同，TreeMap能够确保键的有序性，同时提供额外的有序操作，如subMap、headMap、tailMap等。

`TreeMap` 的主要特性

键的自然顺序：默认情况下，TreeMap按键的自然顺序（如数字从小到大，字符串按字母顺序）排序。
自定义顺序：可以通过提供一个自定义的比较器来决定键的排序顺序。
有序操作：TreeMap支持各种有序操作，如范围查询、子映射等，方便处理有序数据。

核心源码解读

`TreeMap` 的实现原理

TreeMap 基于红黑树实现，能够在插入、删除和查找时保持平衡，从而确保高效的操作性能。以下是TreeMap的部分源码解析：

TreeMap的`put()` 方法

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == 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();
        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;
}

红黑树结构：TreeMap 使用红黑树来存储键值对，保证所有操作（如插入、删除、查找）的时间复杂度为O(log n)。
键的比较：TreeMap通过键的比较来决定新元素插入的位置，如果没有提供自定义比较器，则使用键的自然顺序。

`TreeMap` 的排序与有序操作

除了基本的增删改查操作，TreeMap 还支持丰富的有序操作，这使得它在处理有序数据时具有天然的优势。以下是几个常用的有序操作：

`subMap()` 方法

public SortedMap<K,V> subMap(K fromKey, K toKey) {
    return new SubMap<>(this, fromKey, toKey, false, false);
}

作用：返回一个子映射，包含从fromKey（包含）到toKey（不包含）之间的所有键值对。
应用场景：非常适合需要处理数据范围查询的场景，如获取某一时间段内的日志记录。

`headMap()` 方法

public SortedMap<K,V> headMap(K toKey) {
    return new SubMap<>(this, null, toKey, true, false);
}

作用：返回一个子映射，包含所有小于toKey的键值对。
应用场景：适用于从头部开始处理一批数据，如获取所有早于某个时间点的记录。

`tailMap()` 方法

public SortedMap<K,V> tailMap(K fromKey) {
    return new SubMap<>(this, fromKey, null, false, true);
}

作用：返回一个子映射，包含所有大于等于fromKey的键值对。
应用场景：适用于从某个关键点开始处理剩余的数据，如从某一时间点开始处理后续日志。

案例分析

案例：使用`TreeMap`实现排行榜

假设我们需要实现一个排行榜，能够动态添加用户成绩，并随时查看排行榜的前N名用户。TreeMap 的有序特性使得它非常适合这种场景。

使用`TreeMap`实现排行榜

以下是一个简单的排行榜实现示例：

public class Leaderboard {
    private TreeMap<Integer, String> scores = new TreeMap<>(Collections.reverseOrder());

    public void addScore(String user, int score) {
        scores.put(score, user);
    }

    public Map<Integer, String> getTopN(int n) {
        return scores.entrySet()
                     .stream()
                     .limit(n)
                     .collect(Collectors.toMap(
                         Map.Entry::getKey,
                         Map.Entry::getValue,
                         (e1, e2) -> e1,
                         LinkedHashMap::new));
    }

    public static void main(String[] args) {
        Leaderboard leaderboard = new Leaderboard();
        leaderboard.addScore("Alice", 95);
        leaderboard.addScore("Bob", 85);
        leaderboard.addScore("Charlie", 92);

        System.out.println("Top 2: " + leaderboard.getTopN(2));
    }
}

代码分析

有序存储：TreeMap 按分数的逆序存储用户成绩，最高分排在前面。
前N名查询：通过TreeMap的有序性，可以很方便地获取前N名用户及其成绩。

应用场景演示

TreeMap 在以下场景中有着广泛的应用：

日志管理：在日志系统中，TreeMap 可以用于按时间戳存储日志条目，并支持时间范围查询和有序输出。
配置管理：在存储和管理应用程序管理配置时，TreeMap 可以按配置项的名称或优先级进行有序存储，从而方便快速查找和有序输出配置项。例如，在一个需要加载层次化配置的应用中，可以通过TreeMap按配置层级顺序存储配置项，并根据不同优先级有序加载配置。
金融交易记录：在金融应用中，可以使用TreeMap存储交易记录，键为交易时间戳，值为交易详情。这样可以轻松实现按时间顺序查询交易记录的功能，并支持获取某一时间范围内的交易数据。

优缺点分析

优点

有序存储：TreeMap天然支持键的有序存储，适用于需要排序和范围查询的场景。
自定义排序：通过实现Comparator接口，TreeMap可以支持各种自定义排序需求。
高效操作：TreeMap的操作，如插入、删除和查找，时间复杂度为O(log n)，性能稳定。

缺点

内存占用较大：TreeMap基于红黑树实现，维护树的平衡需要额外的内存开销，特别是在大量数据情况下，内存消耗会明显增加。
操作复杂度高：相对于HashMap的O(1)时间复杂度，TreeMap的O(log n)操作在某些场景下性能不如HashMap。
线程不安全：TreeMap不是线程安全的，在多线程环境下需要手动加锁或使用并发集合类如ConcurrentSkipListMap。

类代码方法介绍及演示

使用`TreeMap`实现按分数排名的学生成绩管理系统

以下代码演示了如何使用TreeMap来实现一个学生成绩管理系统，能够按分数从高到低自动排序，并支持查询前N名学生：

import java.util.Map;
import java.util.TreeMap;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.stream.Collectors;

public class StudentScoreManager {
    private TreeMap<Integer, String> scoreMap = new TreeMap<>(Collections.reverseOrder());

    public void addStudentScore(String student, int score) {
        scoreMap.put(score, student);
    }

    public Map<Integer, String> getTopStudents(int n) {
        return scoreMap.entrySet()
                .stream()
                .limit(n)
                .collect(Collectors.toMap(
                        Map.Entry::getKey,
                        Map.Entry::getValue,
                        (e1, e2) -> e1,
                        LinkedHashMap::new));
    }

    public static void main(String[] args) {
        StudentScoreManager manager = new StudentScoreManager();
        manager.addStudentScore("Alice", 88);
        manager.addStudentScore("Bob", 95);
        manager.addStudentScore("Charlie", 92);

        System.out.println("Top 2 Students: " + manager.getTopStudents(2));
    }
}

方法解析

自动排序：TreeMap会根据分数自动排序，最高分的学生总是排在前面。
获取前N名学生：通过流操作，可以轻松获取分数最高的前N名学生，输出结果为一个按分数排序的LinkedHashMap。

测试用例

为了验证TreeMap的操作效果，以下是一个简单的测试用例，展示如何通过TreeMap存储和操作有序数据：

测试代码

import java.util.TreeMap;

public class TreeMapTest {
    public static void main(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<>();
        map.put("Apple", 3);
        map.put("Banana", 5);
        map.put("Orange", 2);

        System.out.println("Original TreeMap: " + map);
        System.out.println("First Entry: " + map.firstEntry());
        System.out.println("Last Entry: " + map.lastEntry());
        System.out.println("SubMap (Apple to Orange): " + map.subMap("Apple", "Orange"));
    }
}

测试结果预期

在运行测试代码后，预期的输出结果应为：

Original TreeMap: {Apple=3, Banana=5, Orange=2}
First Entry: Apple=3
Last Entry: Orange=2
SubMap (Apple to Orange): {Apple=3, Banana=5}

这表明TreeMap成功地按键的自然顺序存储和操作数据，并能够正确执行有序操作，如获取首尾元素和子映射。

测试代码分析

通过这个测试，我们验证了TreeMap在有序存储和范围查询方面的功能。TreeMap能够确保所有键值对按自然顺序存储，并支持快速访问第一个和最后一个元素，以及根据键范围提取子映射的操作。

小结

本文通过对Java中的TreeMap进行详细解析，帮助读者理解了如何使用TreeMap实现高效的有序映射操作。我们探讨了TreeMap的实现原理、主要特性及其适用场景，并通过实际案例展示了TreeMap在排序和范围查询中的强大功能。通过本文的学习，读者应能够在实际开发中有效利用TreeMap，处理有序数据的存储与操作。

总结

TreeMap 是Java集合框架中不可忽视的工具，尤其在需要对数据进行有序存储和查询时表现出色。通过掌握TreeMap的使用，你可以轻松实现复杂的排序、范围查询和数据管理功能。尽管TreeMap在内存消耗和操作复杂度上有一定的成本，但其强大的有序存储能力使得它在特定场景下成为不可替代的选择。希望本文的内容能够为你的Java开发提供有益的参考和指导。

寄语

编程不仅仅是写代码，更是理解数据结构与算法的艺术。掌握像TreeMap这样的工具，能让你在处理数据时得心应手。愿你在Java开发的道路上，不断学习，不断成长，成为一名更优秀的开发者！

☀️建议/推荐你

无论你是计算机专业的学生，还是对编程有兴趣的小伙伴，都建议直接毫无顾忌的学习此专栏「滚雪球学Java」，bug菌郑重承诺，凡是学习此专栏的同学，均能获取到所需的知识和技能，全网最快速入门Java编程，就像滚雪球一样，越滚越大，指数级提升。

码字不易，如果这篇文章对你有所帮助，帮忙给bug菌来个一键三连(关注、点赞、收藏) ，您的支持就是我坚持写作分享知识点传播技术的最大动力。同时也推荐大家关注我的硬核公众号:「猿圈奇妙屋」；以第一手学习bug菌的首发干货，不仅能学习更多技术硬货，还可白嫖最新BAT大厂面试真题、4000G Pdf技术书籍、万份简历/PPT模板、技术文章Markdown文档等海量资料，你想要的我都有！

📣关于我

--End

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java ee

腾讯技术创作特训营S8

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java ee

腾讯技术创作特训营S8

登录后参与评论

0 条评论

热度