核心内容摘要
PH中文版：开启你的感官新纪元
文章目录TreeMap、TreeSet与Collections.sort()排序机制揭秘
TreeMap与TreeSet红黑树的奥秘
1 TreeMap的工作原理
2 TreeSet的工作原理
3 Comparable与Comparator的区别
4 性能比较
Collections.sort()排序界的瑞士军刀
1 Collections.sort()的基本用法
2 归并排序的特点
3 使用场景的选择
三、
常见问题与坑点
1 自然顺序与自定义排序的冲突
2 null值的处理
3 并发环境下的线程安全性
四、
总结通过以上分析希望你对TreeMap/TreeSet和Collections.sort()有了更深入的理解并能够在实际项目中做出更加合理的选择。
领取 | 1000 套高质量面试题大合集无套路闫工带你飞一把TreeMap、TreeSet与Collections.sort()排序机制揭秘大家好我是闫工今天咱们要聊的是Java中三个非常重要的排序相关的知识点TreeMap、TreeSet以及Collections.sort()。
这三个工具在日常开发中可以说是随处可见但它们的底层实现和使用场景却常常被我们忽视。
很多人可能会觉得它们都是用来排序的那我直接用就好了呗但其实这里面有很多细节需要注意甚至可能会踩到一些坑。
今天咱们就一起来揭开它们的神秘面纱看看它们到底是怎么工作的以及在实际开发中该如何选择合适的工具。
TreeMap与TreeSet红黑树的奥秘首先咱们先来聊聊TreeMap和TreeSet。
这两个类都是基于红黑树实现的这一点我相信大家都知道。
但什么是红黑树呢简单来说红黑树是一种自平衡二叉搜索树它通过一些颜色标记红色或黑色来保证树的高度不会过高从而使得插入、删除和查找操作的时间复杂度均为O(log n)。
1 TreeMap的工作原理TreeMap是基于键值对的有序集合它的实现依赖于红黑树结构。
当你往TreeMap中添加元素时它会根据键的自然顺序或者自定义的比较器Comparator来进行排序。
默认情况下TreeMap使用的是Comparable接口中的compareTo方法来比较键的大小。
举个栗子假设我们有一个学生类Student其中有一个年龄属性agepublicclassStudentimplementsComparableStudent{privateintage;publicStudent(intage){this.ageage;}OverridepublicintcompareTo(Studentother){returnthis.age-other.age;}}然后我们用TreeMap来存储这些学生TreeMapStudent,StringtreeMapnewTreeMap();treeMap.put(newStudent(
,Alice);treeMap.put(newStudent(
,Bob);treeMap.put(newStudent(
,Charlie);这时候TreeMap会根据Student类中定义的compareTo方法按照年龄从小到大进行排序。
当我们遍历这个TreeMap的时候得到的结果就是Bob、Alice、Charlie。
2 TreeSet的工作原理TreeSet同样是基于红黑树实现的但它是一个无序集合不存储键值对。
TreeSet中的元素会根据自然顺序或者自定义的比较器进行排序并且不允许有重复元素。
比如说TreeSetStudenttreeSetnewTreeSet();treeSet.add(newStudent(
);treeSet.add(newStudent(
);treeSet.add(newStudent(
);遍历这个TreeSet得到的结果同样会是Bob、Alice、Charlie。
3 Comparable与Comparator的区别在上述例子中我们使用了Comparable接口来实现自然排序。
但有时候我们的需求可能需要动态改变排序规则这时候就需要用到Comparator了。
比如说如果我们想按照学生的年龄从大到小排序TreeMapStudent,StringtreeMapnewTreeMap(newComparatorStudent(){Overridepublicintcompare(Students1,Students
{returns
getAge()-s
getAge();}});这样TreeMap中的元素就会按照年龄从大到小排序。
需要注意的是当使用Comparator时如果同时定义了Comparable接口的实现那么Comparator会覆盖自然顺序。
因此在选择使用哪种方式时需要格外小心。
4 性能比较由于TreeMap和TreeSet都是基于红黑树实现的它们的插入、删除和查找操作的时间复杂度均为O(log n)这在处理大数据量的时候表现非常优秀。
但需要注意的是红黑树的实现相对来说是比较复杂的因此在实际开发中需要权衡性能与代码复杂度。
Collections.sort()排序界的瑞士军刀接下来咱们来聊一聊Collections.sort()这个方法。
它是一个静态方法位于java.util.Collections类中用于对List集合进行排序。
它的底层实现是基于归并排序算法Merge Sort而归并排序是一种稳定的排序算法时间复杂度为O(n log n)。
1 Collections.sort()的基本用法使用起来非常简单ListStudentlistnewArrayList();list.add(newStudent(
);list.add(newStudent(
);list.add(newStudent(
);Collections.sort(list);这样list中的元素就会按照自然顺序也就是Student类中定义的Comparable接口进行排序。
如果想使用自定义的比较器Collections.sort(list,newComparatorStudent(){Overridepublicintcompare(Students1,Students
{returns
getAge()-s
getAge();}});这样list中的元素就会按照年龄从大到小排序。
2 归并排序的特点归并排序的特点是稳定且时间复杂度较低但需要额外的空间来存储临时数组。
因此在处理大数据量的时候Collections.sort()可能会有一些性能上的损耗。
不过由于它是基于JDK内部的实现通常情况下它的表现还是非常优秀的。
3 使用场景的选择那么问题来了什么时候该用TreeMap/TreeSet什么时候该用Collections.sort()呢如果你需要一个有序集合并且希望在插入的时候就保持顺序那么TreeMap和TreeSet是更好的选择。
因为它们的插入、删除和查找操作的时间复杂度都是O(log n)适合需要频繁进行这些操作的场景。
如果你只是需要对一个现有的List进行排序而不需要后续的有序集合操作那么使用Collections.sort()会更加高效因为它避免了红黑树结构的额外开销。
三、
常见问题与坑点在实际开发中我们可能会遇到一些常见的问题或者误区。
接下来咱们来一一分析。
1 自然顺序与自定义排序的冲突假设你有一个类同时实现了Comparable接口并且又传入了一个Comparator到TreeMap或Collections.sort()中publicclassStudentimplementsComparableStudent{// 实现了自然排序比如按年龄从小到大publicintcompareTo(Studentother){returnthis.age-other.age;}}// 使用自定义的ComparatorTreeMapStudent,StringtreeMapnewTreeMap(newComparatorStudent(){Overridepublicintcompare(Students1,Students
{// 按照年龄从大到小排序returns
getAge()-s
getAge();}});这时候TreeMap会使用传入的Comparator来排序而不是自然顺序。
因此在定义Comparator时需要特别小心避免与自然顺序产生冲突。
2 null值的处理在Java中无论是TreeMap、TreeSet还是Collections.sort()都不允许null值的存在。
如果尝试插入一个null元素或者排序包含null的List都会抛出NullPointerException异常。
因此在使用这些集合或方法之前需要确保数据中不包含null值或者在代码中进行适当的处理。
3 并发环境下的线程安全性TreeMap和TreeSet都是非线程安全的集合如果在多线程环境下使用需要手动加锁或者使用它们的同步版本如Collections.synchronizedSortedMap()来保证线程安全。
而Collections.sort()方法本身是针对单个List进行排序因此在并发环境下需要特别注意避免多个线程同时修改同一个List。
四、
总结TreeMap/TreeSet适合需要有序集合并且需要频繁插入、删除和查找操作的场景。
Collections.sort()适合只需要对一个现有的List进行排序而不需要后续有序集合操作的场景。
在选择使用哪种方法时需要根据具体的需求来权衡性能与代码复杂度。
同时在实际开发中需要注意自然顺序与自定义排序的冲突、null值的处理以及并发环境下的线程安全性等问题。
通过以上分析希望你对TreeMap/TreeSet和Collections.sort()有了更深入的理解并能够在实际项目中做出更加合理的选择。
领取 | 1000 套高质量面试题大合集无套路闫工带你飞一把成体系的面试题无论你是大佬还是小白都需要一套JAVA体系的面试题我已经上岸了你也想上岸吗闫工精心准备了程序准备面试想系统提升技术实力闫工精心整理了1000 套涵盖前端、后端、算法、数据库、操作系统、网络、设计模式等方向的面试真题 详细解析并附赠高频考点