TreeSet 使用与详细分析

底层基于TreeMap，在集合创建时使用其自然排序或Comparator提供的排序，具体取决于使用的构造函数。

import java.util.*;
public class Test {
    public static void main(String[] args) {
        TreeSet set=new TreeSet<>();
        set.add(5);
        set.add(4);
        System.out.println(set.toString());//[4, 5]
        set.forEach(i-> System.out.println(i));
    }

}

非线程安全，并发场景下可以使用Collections.synchronizedSortedSet(new TreeSet(...))包装.

基于红黑树的NavigableMap实现。Map根据其键的自然顺序或Comparator在Map创建时提供的排序，具体取决于使用的构造函数。

TreeMap利用了红黑树左节点小，右节点大的性质，根据 key 进行排序，使每个元素能够插入到红黑树适当的位置，维护了 key 的大小关系，适用于 key 需要排序的场景。

因为底层使用的是红黑树，所以 TreeMap 中的 containsKey、get、put、remove 等方法的时间复杂度都是 log(n)。

import java.util.*;
public class Test {
    public static void main(String[] args) {
        TreeMap map=new TreeMap<>();
        map.put(3,"1");
        map.put(4,"4");
        map.get(1);
        map.remove(3);
        System.out.println(map.toString());

    }

}

基础类型和String都实现了比较接口

   //比较器，如果外部有传进来Comparator比较器，首先用外部的
   private final Comparator comparator;

    private transient Entry root;//红黑树的根节点

    
    private transient int size = 0;

    
    private transient int modCount = 0;

红黑树节点的结构

 static final class Entry implements Map.Entry {
        K key;
        V value;
        Entry left;
        Entry right;
        Entry parent;
        boolean color = BLACK;
        ...
        
        }

默认构造方法，需要key实现比较接口。

  public TreeMap() {
        comparator = null;
    }
  public TreeMap(Comparator comparator) {
        this.comparator = comparator;
    }

• Comparable：构造器不传递时候要求key必须实现Comparable接口
• comparator：传入的comparator比较器比较两个key的大小，key不用实现比较接口
• 如果以上两种情况都满足，优先使用外部的Comparator比较器