文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

【Java 数据结构】TreeMap和TreeSet的介绍

2023-09-04 09:37

关注


目录

1、认识 TreeMap 和 TreeSet

2、TreeMap 的主要成员变量

3、TreeMap 的主要构造方法

4、TreeMap 和 TreeSet 的元素必须可比较

5、TreeMap 和 TreeSet 关于 key 有序 

6、TreeMap 和 TreeSet 的关系 

7、总结


TreeMap 和 TreeSet 是Java中利用搜索树实现的 Map 和 Set,它们的底层是红黑树,而红黑树是一棵近似平衡的二叉搜索树,关于红黑树相关知识后续讲解。本期主要是学会 TreeMap 和 TreeSet 的使用,以及知道他们的特点即可。


// 存储传入比较器的引用private final Comparator comparator;// 搜索树的根节点private transient Entry root;// 节点个数private transient int size = 0;// 统计搜索树结构修改的次数private transient int modCount = 0;

这里我们需要注意的是 comparator 这个引用,它是用来接收一个比较器的,主要功能后续会讲解,这里注意一下即可。


public TreeMap() {    comparator = null;}public TreeMap(Comparator comparator) {    this.comparator = comparator;}public TreeMap(Map m) {    comparator = null;    putAll(m);}
  • 第一个构造方法,没什么意外的,你没传比较器嘛,自然就是 null。
  • 第二个是传了比较器的构造方法, 指定了比较器也很简单。
  • 第三个构造方法, 则是把你传递的 Map 构造一个新的树映射,包含与给定映射相同的映射,并根据其 key 的自然顺序进行排序,这些 key,必须可相互比较!

因为 TreeMap 和 TreeSet 实现了 SortedSet 接口,表示是一个需要实现排序功能的 Map 或 Set,那实现排序的前提,你放入的元素必须是可比较的,那么也就是说,当你往 TreeMap 里面放 key 的时候,这个 key 必须可比较,也就是重写了 compaerTo 方法,你也可也直接传一个比较器也是可以的。

public class Test {    public static void main(String[] args) {        Map map = new TreeMap<>();        System.out.println(map);    }}

这个报错就是在说, Person 无法被转换成 Comparable,也就是在 TreeMap 底层实现中无法将 key 对象中的 compareTo 方法。

具体我们还是要去看 TreeMap 的无参构造方法以及 put 的源码:

public TreeMap() {    comparator = null;}

对于 TreeMap 的无参构造方法,其实很简单,如果你没有传比较器进去,默认就是 null 的,接下来就得看一下 put 方法了。

源码中比较多,我们这里只截取一小部分,能明白为啥重写 compareTo 方法即可。

很明显,我们是第一次 put 元素,所以搜索树的根节点也就是 root 节点为 null,接着将我们 put 进去的 key 作为 compare 两个参数传递进去,接着去看 compare 的实现:

这里我们没有传比较器,所以刚开始的无参构造方法已经将 comparator 置 null了,很明显这里可以发现,如果我们传了比较器,就按照比较器的方式来比较,如果没有比较器,则会将 key 转换成 Comparable,这个尖括号中的类型, 此时我们这里是转换成 Person,这也是泛型上界的相关知识,所以即最终调用了我们 key 对象中的 compareTo 方法,那如果我们没有实现 Comparable 这个接口,也没有重写 compareTo 方法自然会抛异常。

当然后续 put 元素也是按照上面的方法来比较的,有比较器,使用比较器来比较,无比较器,调用对象中的 compareTo 进行比较。


我们前面讲到过, TreeMap 和 TreeSet 的底层其实是搜索树,而且是红黑树,那么中序遍历搜索树是有序的,也即按照 key 提供的比较方式,或者你自己提供的比较器,关于 key 是有序的。

class Person implements Comparable {    private String name;    private int age;    public Person(String name, int age) {        this.name = name;        this.age = age;    }    @Override    public String toString() {        return "Person{" +                "name='" + name + '\'' +                ", age=" + age +                '}';    }    @Override    public int compareTo(Person o) {        return this.age - o.age;    }}public class Test {    public static void main(String[] args) {        TreeMap map = new TreeMap<>();        map.put(new Person("张三", 12), 1);        map.put(new Person("李四", 21), 2);        map.put(new Person("王五", 16), 3);        Set> entrySet = map.entrySet();        for (Map.Entry personIntegerEntry : entrySet) {            System.out.println(personIntegerEntry);        }    }}

由于 Map 没有继承于Iterable 接口,所以不能采用 for-each 遍历,只能返回 Key-value 的映射关系放入 Set 中进行遍历。

上述代码是按照 Person 中的年龄进行比较的,所以如果最终打印出来的结果是 12 21 16 这样的年龄排序的顺序话,也足以说明,在 TreeMap 和 TreeSet 中是关于 key 有序的,打印结果:

看到这,可能有的小伙伴说,确实是关于 key 有序,但是怎么保证底层是一棵搜索树呢?其实也很简单验证,搜索树前几期也讲过,如果是按照我们 Person 类比较的方式的话,那么根节点的左边都小于它,根节点的右边都大于它,这里我们通过调试看看 map 中存储的结构就ok了:

这里我们通过调试的方式进入到源码中,输入我们想观察的变量,于是可以看到,确实是一棵搜索树,而且不是简单的二叉搜索树,是一棵红黑树。

为什么是这里就能看出来是红黑树呢,因为如果是按照我们前面讲二叉搜索树的逻辑, 根节点一定是第一次插入的 “张三,12”,而这里跟节点为什么是 “王五,16”,因为当插入 “王五” 的时候,搜索树的左右子树高度不平衡了,红黑树进行了旋转调整,至于更多底层实现细节,目前我们可以不用关心,由此也可能看出来并不是一棵简单的二叉搜索树。


上期其实也提到过,Set 的底层其实就是 Map,而 TreeSet 也是一样,底层仍然是 TreeMap,拿什么证明呢?其实我们来看 Set 的构造方法就可以了:

TreeSet(NavigableMap m) {    this.m = m;}public TreeSet() {    this(new TreeMap());}public TreeSet(Comparator comparator) {    this(new TreeMap<>(comparator));}public TreeSet(Collection c) {    this();    addAll(c);}

这里的 NavigableMap 也是一个继承 SortedMap 的接口,因此具有SortedMap,Map接口的属性方法,通过上述的构造方法也能看出,当你实例化一个 TreeSet 对象的时候,本质上还是 new 了一个 TreeMap 对象。而能明显看到,value 为一个 Object 默认对象。


TreeMap 和 TreeSet 底层都是红黑树,插入删除查找的时间复杂度为 O(logN),数据关于 key 是有序的,key 必须要能够比较,不然会抛出 ClassCastException 异常,主要运用于需要 key 有序的场景下,TreeMap 和 TreeSet 是线程不安全的。 


下期预告:【Java 数据结构】HashMap和HashSet

来源地址:https://blog.csdn.net/m0_61784621/article/details/128428551

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯