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

朱雀 2024-03-30 11:51 45阅读 0赞

![b4bad7429a1f4d79b63ad0e7d179a7b4.gif][]

--------------------

**目录**

1、认识 TreeMap 和 TreeSet

2、TreeMap 的主要成员变量

3、TreeMap 的主要构造方法

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

5、TreeMap 和 TreeSet 关于 key 有序

6、TreeMap 和 TreeSet 的关系

7、总结

--------------------

## **1、认识 TreeMap 和 TreeSet** ##

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

![86272d4c92e943b1a03b473f584636fd.png][]

--------------------

## **2、TreeMap 的主要成员变量** ##

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

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

--------------------

## **3、TreeMap 的主要构造方法** ##

public TreeMap() {
        comparator = null;
    }
    
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
    
    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }

>  *  第一个构造方法，没什么意外的，你没传比较器嘛，自然就是 null。
>  *  第二个是传了比较器的构造方法， 指定了比较器也很简单。
>  *  第三个构造方法， 则是把你传递的 Map 构造一个新的树映射，包含与给定映射相同的映射，并根据其 key 的自然顺序进行排序，这些 key，必须可相互比较！

--------------------

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

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

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

![84c32d74bce54bd0b36448f5c190e1ec.png][]

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

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

public TreeMap() {
        comparator = null;
    }

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

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

![944105e2e8fc4ec99ff3d7f394827383.png][]

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

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

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

--------------------

## **5、TreeMap 和 TreeSet 关于 key 有序** ##

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

class Person implements Comparable<Person> {
        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<Person, Integer> map = new TreeMap<>();
            map.put(new Person("张三", 12), 1);
            map.put(new Person("李四", 21), 2);
            map.put(new Person("王五", 16), 3);
            Set<Map.Entry<Person, Integer>> entrySet = map.entrySet();
            for (Map.Entry<Person, Integer> personIntegerEntry : entrySet) {
                System.out.println(personIntegerEntry);
            }
        }
    }

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

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

![31b98d11dddd44bda51fc0b2188b9724.png][]

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

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

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

--------------------

## **6、TreeMap 和 TreeSet 的关系** ##

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

TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
    
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
    
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }
    
    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }

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

--------------------

## **7、总结** ##

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

--------------------

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

[b4bad7429a1f4d79b63ad0e7d179a7b4.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6dda6e70bf954d0b9f89ecb91696e8da.gif
[86272d4c92e943b1a03b473f584636fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2e0b838522444a6b9f501ab9c87670f3.png
[84c32d74bce54bd0b36448f5c190e1ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/95c96fb030da4957a3ab1516c7b51125.png
[944105e2e8fc4ec99ff3d7f394827383.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/51835a27104c4524b4e50425eab5a5cf.png
[2367b4b55f824bd1955b624be0b7858b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f3c051caa74742c9b90b1446bb7c2bfa.png
[31b98d11dddd44bda51fc0b2188b9724.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fb4ba0bbc9dc4e6bbf3ee433c2fa0a5d.png
[eb481ad10099434c9aa04e0a8ea6d90d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/1ef3a547b1bf40d39ea8badeb93c4d2a.png