教做甜品的网站,删除wordpress主题字体载入,射阳网页定制,太原seo推广优化咦咦咦#xff0c;各位小可爱#xff0c;我是你们的好伙伴——bug菌#xff0c;今天又来给大家普及Java SE相关知识点了#xff0c;别躲起来啊#xff0c;听我讲干货还不快点赞#xff0c;赞多了我就有动力讲得更嗨啦#xff01;所以呀#xff0c;养成先点赞后阅读的好… 咦咦咦各位小可爱我是你们的好伙伴——bug菌今天又来给大家普及Java SE相关知识点了别躲起来啊听我讲干货还不快点赞赞多了我就有动力讲得更嗨啦所以呀养成先点赞后阅读的好习惯别被干货淹没了哦~ 本文收录于「滚雪球学Java」专栏专业攻坚指数级提升助你一臂之力带你早日登顶欢迎大家关注收藏持续更新中upupup
环境说明Windows 10 IntelliJ IDEA 2021.3.2 Jdk 1.8文章目录 前言摘要TreeMap概述源代码解析应用场景案例优缺点分析优点缺点 类代码方法介绍构造方法读取方法写入方法转换方法 测试用例测试用例测试结果测试代码分析性能测试测试代码演示测试结果测试代码分析 结论 总结附录源码 ☀️建议/推荐你关于我 前言 在 Java 编程中我们经常需要使用到键值映射表这种数据结构。其中HashMap 是最常用的一种它能够以 O(1) 的时间复杂度完成插入、查找、删除等操作。但是HashMap 并不能对键进行排序因此如果我们需要按有序方式来保存键值对就需要使用到 TreeMap了。
摘要 本篇文章将深入介绍 TreeMap 的原理、源码实现、应用场景、优缺点以及相关测试用例。
TreeMap
概述 TreeMap 是一种基于红黑树实现的有序键值映射表。它实现了 Map 接口并且根据键的自然排序或者根据一个 Comparator 进行排序。在 TreeMap 中键值对是按照键进行排序的因此遍历 TreeMap 时得到的键值对是有序的。
源代码解析
TreeMap 的主要实现类是 TreeMap 类。我们来看一下它的源码实现。
public class TreeMapK,V extends AbstractMapK,Vimplements NavigableMapK,V, Cloneable, java.io.Serializable {// 省略了一些常量和字段的定义public TreeMap() {comparator null;}public TreeMap(Comparator? super K comparator) {this.comparator comparator;}// 省略了一些构造方法的定义public SetMap.EntryK,V entrySet() {return new EntrySet();}// 省略了一些方法的定义}从代码中可以看出TreeMap 实现了 Map 接口和 NavigableMap 接口并且继承了 AbstractMap。它也提供了多个构造方法可以根据需要选择。 如下是部分源码截图 下面我们来看一下 TreeMap 中最重要的实现类 Entry。Entry 类表示 TreeMap 中的一个键值对它包含了键和值两个属性其中键是有序的。
static final class EntryK,V implements Map.EntryK,V {K key;V value;EntryK,V left null;EntryK,V right null;EntryK,V parent;boolean color BLACK;/*** Make a new cell with given key, value, and parent, and with* {code null} child links, and BLACK color.*/Entry(K key, V value, EntryK,V parent) {this.key key;this.value value;this.parent parent;}// 省略了一些方法的定义
}Entry 类中定义了一个 boolean 类型的 color 属性它表示该节点的颜色用于红黑树的平衡操作。Entry 类中还包含了 left、right、parent 三个指针用于指向该节点的左子节点、右子节点和父节点。 如下是部分源码截图 应用场景案例 以下是使用 TreeMap 的一个实际案例。我们有一个成绩表需要按照学生姓名的字典序进行排序而 TreeMap 刚好可以满足这个需求。
import java.util.*;public class ScoreTable {public static void main(String[] args) {TreeMapString, Integer map new TreeMap();map.put(Tom, 85);map.put(Jack, 92);map.put(Lily, 76);for (Map.EntryString, Integer entry : map.entrySet()) {System.out.println(entry.getKey() : entry.getValue());}}
}运行结果如下
Jack : 92
Lily : 76
Tom : 85从运行结果可以看出TreeMap 把学生姓名按照字典序排序后输出。
优缺点分析
以下是 TreeMap 的优缺点分析。
优点
TreeMap 可以对键进行排序因此遍历 TreeMap 时得到的键值对是有序的。TreeMap 可以根据自然顺序或者自定义比较器进行排序。TreeMap 的内部实现使用红黑树因此插入、查找、删除等操作的时间复杂度为 O(log n)。
缺点
TreeMap 要求键是可比较的因此不能存储自定义对象类型的键。TreeMap 的内部结构是红黑树它比 HashMap 内部的哈希表结构要占用更多的内存因此 TreeMap 的空间复杂度要高于 HashMap。对于频繁的插入、删除操作TreeMap 的效率不如 HashMap 高。
类代码方法介绍
以下是 TreeMap 类中一些常用的方法的介绍。
构造方法 // 构造一个空的 TreeMappublic TreeMap()// 构造一个 TreeMap并指定一个比较器进行排序public TreeMap(Comparator? super K comparator)代码拓展 这段代码是 Java 中 TreeMap 类的构造函数用于创建 TreeMap 对象。 第一个构造函数 public TreeMap() 创建一个空的 TreeMap没有指定任何比较器默认使用自然排序即实现 Comparable 接口。 第二个构造函数 public TreeMap(Comparator? super K comparator) 创建一个 TreeMap 对象并指定一个特定的比较器来对键进行排序。Comparator 参数是用于比较键的比较器它可以是任何实现了 Comparator 接口的类或者 lambda 表达式。通过这个构造函数我们可以根据自己的需要自定义排序规则。 注意TreeMap 的键必须实现 Comparable 接口或者在创建 TreeMap 时指定一个 Comparator 比较器否则会抛出 ClassCastException 异常。
读取方法 // 获取 TreeMap 的大小public int size()// 判断 TreeMap 是否为空public boolean isEmpty()// 获取 TreeMap 中键为 key 对应的值public V get(Object key)// 获取 TreeMap 中比键 key 大的最小键值对public Map.EntryK,V higherEntry(K key)// 获取 TreeMap 中比键 key 大的最小键public K higherKey(K key)// 获取 TreeMap 中比键 key 小的最大键值对public Map.EntryK,V lowerEntry(K key)// 获取 TreeMap 中比键 key 小的最大键public K lowerKey(K key)// 获取 TreeMap 中键值比 key 大的最小键值对如果 TreeMap 为空则返回 nullpublic Map.EntryK,V ceilingEntry(K key)// 获取 TreeMap 中键值比 key 大的最小键如果 TreeMap 为空则返回 nullpublic K ceilingKey(K key)// 获取 TreeMap 中键值比 key 小的最大键值对如果 TreeMap 为空则返回 nullpublic Map.EntryK,V floorEntry(K key)// 获取 TreeMap 中键值比 key 小的最大键如果 TreeMap 为空则返回 nullpublic K floorKey(K key)// 获取 TreeMap 中最小的键值对public Map.EntryK,V firstEntry()// 获取 TreeMap 中最小的键public K firstKey()// 获取 TreeMap 中最大的键值对public Map.EntryK,V lastEntry()// 获取 TreeMap 中最大的键public K lastKey()代码拓展 这段代码是 TreeMap 类中的一些常用方法具体说明如下
size()返回 TreeMap 的大小即键值对个数。isEmpty()判断 TreeMap 是否为空如果为空则返回 true否则返回 false。get(key)返回键为 key 对应的值如果 key 不存在则返回 null。higherEntry(key)返回 TreeMap 中比键 key 大的最小键值对如果不存在则返回 null。higherKey(key)返回 TreeMap 中比键 key 大的最小键如果不存在则返回 null。lowerEntry(key)返回 TreeMap 中比键 key 小的最大键值对如果不存在则返回 null。lowerKey(key)返回 TreeMap 中比键 key 小的最大键如果不存在则返回 null。ceilingEntry(key)返回 TreeMap 中键值比 key 大的最小键值对如果 TreeMap 为空则返回 null。ceilingKey(key)返回 TreeMap 中键值比 key 大的最小键如果 TreeMap 为空则返回 null。floorEntry(key)返回 TreeMap 中键值比 key 小的最大键值对如果 TreeMap 为空则返回 null。floorKey(key)返回 TreeMap 中键值比 key 小的最大键如果 TreeMap 为空则返回 null。firstEntry()返回 TreeMap 中最小的键值对如果 TreeMap 为空则返回 null。firstKey()返回 TreeMap 中最小的键如果 TreeMap 为空则抛出 NoSuchElementException 异常。lastEntry()返回 TreeMap 中最大的键值对如果 TreeMap 为空则返回 null。lastKey()返回 TreeMap 中最大的键如果 TreeMap 为空则抛出 NoSuchElementException 异常。 这些方法可以帮助我们操作 TreeMap 中的键值对常用于查询和遍历操作。
写入方法 // 插入键值对public V put(K key, V value)// 删除键值对public V remove(Object key)// 清空 TreeMappublic void clear()代码拓展 这是针对 Java 中的 TreeMap 类进行的方法分析 put(K key, V value): 该方法用于将指定的键值对插入到 TreeMap 中。如果 TreeMap 中已经有该键则用新的值替换旧的值并返回旧的值如果 TreeMap 中没有该键则插入该键值对并返回 null。 remove(Object key): 该方法用于从 TreeMap 中删除指定的键及其对应的值。如果 TreeMap 中有该键则删除该键值对并返回其对应的值如果 TreeMap 中没有该键则返回 null。 clear(): 该方法用于清空 TreeMap 中的所有键值对。调用该方法后TreeMap 的大小变为 0但 TreeMap 仍然存在。
转换方法 // 返回 TreeMap 的副本public Object clone()// 返回 TreeMap 中键的有序集合public SetK keySet()// 返回 TreeMap 中键值对的集合public SetMap.EntryK, V entrySet()// 返回 TreeMap 中值的无序集合public CollectionV values()代码拓展 这段代码是 Java 中 TreeMap 类的几个常用方法的声明具体解释如下 public Object clone() 方法会返回一个 TreeMap 的副本也就是一个新的 TreeMap其中包含与原始 TreeMap 相同的键值对。这个方法可以用来创建原始 TreeMap 的副本以在对副本进行操作时不影响原始 TreeMap。 public SetK keySet() 方法会返回 TreeMap 中所有键的有序集合。该方法可以用于遍历 TreeMap 中的所有键。 public SetMap.EntryK, V entrySet() 方法会返回 TreeMap 中所有键值对的集合。集合中每个元素都是一个 Map.Entry 对象包含键和相应的值。该方法可以用于遍历 TreeMap 中的所有键值对。 public CollectionV values() 方法会返回 TreeMap 中所有值的无序集合。该方法可以用于遍历 TreeMap 中的所有值。 需要注意的是TreeMap 的键必须是可比较的对象并且按照键的自然顺序进行排序。如果要使用自定义比较器对键进行排序可以使用 TreeMap 的另一个构造函数该构造函数接受一个实现了 Comparator 接口的比较器对象作为参数。
测试用例
以下是针对 TreeMap 的测试用例。
测试用例
测试 TreeMap 的基本操作包括插入、删除和遍历。
package com.demo.javase.day67;import java.util.Map;
import java.util.TreeMap;/*** Author bug菌* Date 2023-11-06 12:10*/
public class TreeMapTest {public static void main(String[] args) {TreeMapString, Integer map new TreeMap();map.put(Tom, 85);map.put(Jack, 92);map.put(Lily, 76);map.put(Bob, 88);System.out.println(Initial TreeMap:);for (Map.EntryString, Integer entry : map.entrySet()) {System.out.println(entry.getKey() : entry.getValue());}map.remove(Lily);System.out.println(\nAfter removing Lily:);for (Map.EntryString, Integer entry : map.entrySet()) {System.out.println(entry.getKey() : entry.getValue());}}
}测试结果 根据如上测试用例本地测试结果如下仅供参考你们也可以自行修改测试用例或者添加更多的测试数据或测试方法进行熟练学习以此加深理解。
运行结果如下
Initial TreeMap:
Jack : 92
Lily : 76
Bob : 88
Tom : 85After removing Lily:
Bob : 88
Jack : 92
Tom : 85具体执行截图如下 测试代码分析 根据如上测试用例在此我给大家进行深入详细的解读一下测试代码以便于更多的同学能够理解并加深印象。 此代码是一个简单的关于 TreeMap 的使用示例。 TreeMap 是基于红黑树实现的可以保证有序性且插入、删除、查找的时间复杂度是 O(log n)。 该代码创建了一个 TreeMap 对象键类型为 String值类型为 Integer。然后向 TreeMap 中添加了四个键值对。接着打印出初始 TreeMap 中的所有键值对。再移除 key 为 “Lily” 的键值对最后再次打印出移除后的 TreeMap 中的所有键值对。
运行结果如下 Initial TreeMap: Jack : 92 Lily : 76 Bob : 88 Tom : 85 After removing Lily: Bob : 88 Jack : 92 Tom : 85 可以看到初始 TreeMap 中所有键值对的顺序是按照键的自然顺序进行排序的即按照字母顺序。而移除 key 为 “Lily” 的键值对后再次打印出的所有键值对的顺序仍然是有序的。这证明 TreeMap 确实有序且移除操作也能保持 TreeMap 的顺序性。
性能测试
测试 TreeMap 的性能包括插入、查找和删除操作的时间消耗。
测试代码演示
package com.demo.javase.day67;import java.util.TreeMap;/*** Author bug菌* Date 2023-11-06 12:12*/
public class TreeMapPerformanceTest {private static final int SIZE 1000000;public static void main(String[] args) {System.out.println(TreeMap Performance Test:);System.out.println(-------------------------);TreeMapInteger, Integer map new TreeMap();// Insert testlong start System.currentTimeMillis();for (int i 0; i SIZE; i) {map.put(i, i);}long end System.currentTimeMillis();System.out.println(Insert SIZE elements time: (end - start) ms);// Search teststart System.currentTimeMillis();for (int i 0; i SIZE; i) {map.get(i);}end System.currentTimeMillis();System.out.println(Search SIZE elements time: (end - start) ms);// Delete teststart System.currentTimeMillis();for (int i 0; i SIZE; i) {map.remove(i);}end System.currentTimeMillis();System.out.println(Delete SIZE elements time: (end - start) ms);}
}测试结果 根据如上测试用例本地测试结果如下仅供参考你们也可以自行修改测试用例或者添加更多的测试数据或测试方法进行熟练学习以此加深理解。
运行结果如下
TreeMap Performance Test:
-------------------------
Insert 1000000 elements time: 148ms
Search 1000000 elements time: 64ms
Delete 1000000 elements time: 65ms测试代码分析 根据如上测试用例在此我给大家进行深入详细的解读一下测试代码以便于更多的同学能够理解并加深印象。 这是一个测试TreeMap性能的Java程序主要进行了三项测试
插入测试向TreeMap中插入1000000个元素并记录时间查找测试在TreeMap中查找1000000个元素并记录时间删除测试从TreeMap中删除1000000个元素并记录时间。 通过这些测试可以评估TreeMap在插入、查找和删除操作时的性能。
结论 本文对 Java 中的有序键值映射表 TreeMap 进行了详细的介绍。我们讲解了 TreeMap 的原理、源码实现、应用场景、优缺点以及相关测试用例。通过本文的学习我们能够更加深入地理解 TreeMap以及在实际开发中如何正确地使用它。
总结 本篇文章主要介绍了 Java 中的有序键值映射表 TreeMap包括其原理、源码实现、应用场景、优缺点以及相关测试用例。从文章中可以了解到TreeMap 是一种基于红黑树实现的有序键值映射表可以根据键进行排序遍历 TreeMap 时得到的键值对是有序的。同时TreeMap 的内部实现使用红黑树因此插入、查找、删除等操作的时间复杂度为 O(log n)。文章还提供了针对 TreeMap 的测试用例对其进行性能测试以评估 TreeMap 在插入、查找和删除操作时的性能。 … 好啦这期的内容就基本接近尾声啦若你想学习更多可以参考这篇专栏总结《「滚雪球学Java」教程导航帖》本专栏致力打造最硬核 Java 零基础系列学习内容打造全网精品硬核专栏带你直线超车欢迎大家订阅持续学习。
附录源码 如上涉及所有源码均已上传同步在「Gitee」提供给同学们一对一参考学习辅助你更迅速的掌握。
☀️建议/推荐你 无论你是计算机专业的学生还是对编程有兴趣的小伙伴都建议直接毫无顾忌的学习此专栏「滚雪球学Java」bug菌郑重承诺凡是学习此专栏的同学均能获取到所需的知识和技能全网最快速入门Java编程就像滚雪球一样越滚越大指数级提升。 最后如果这篇文章对你有所帮助帮忙给作者来个一键三连关注、点赞、收藏您的支持就是我坚持写作最大的动力。 同时欢迎大家关注公众号:「猿圈奇妙屋」 以便学习更多同类型的技术文章免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板、技术文章Markdown文档等海量资料。 关于我 我是bug菌CSDN | 掘金 | infoQ | 51CTO 等社区博客专家历届博客之星Top30掘金年度人气作者Top4051CTO年度博主Top12华为云 | 阿里云| 腾讯云等社区优质创作者全网粉丝合计15w 硬核微信公众号「猿圈奇妙屋」欢迎你的加入免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板等海量资料。
