TreeMap和TreeSet的介绍

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

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);
    }
}

这个报错就是在说， Person 无法被转换成 Comparable，也就是在 TreeMap 底层实现中无法将 key 对象中的 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 有序的，打印结果：

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 是线程不安全的。