TreeSet

TreeSet的特点：
1、排序：
1）自然排序
2）比较器排序

2、唯一：底层通过TreeMap实现了元素的唯一性。

1、自然排序：

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
    public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }  

解析：通过构造方法可以看出，TreeSet底层实际上是new的TreeMap。所以直接看TreeMap的put的时候是怎么进行排序的

   Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);

这里可以看出，实际上它是将传进来的key（元素）向上转型成了一个Comparable，然后通过compareTo方法比较大小，如果比当前节点小找左节点，如果t大于当前节点找右节点，如果相等，值覆盖。所以TreeSet添加进的元素必须实现Comparable接口，否则向上转型会报错，如下图。

image.png

可以重写compareTo方法，这里我们通过age来比较大小

    @Override
    public int compareTo(Cat o) {
        return this.age-o.age;
    }

        TreeSet<Cat> set = new TreeSet<Cat>();
        set.add(new Cat("tom", 20));
        set.add(new Cat("tom", 18));
        set.add(new Cat("tom", 23));
        set.add(new Cat("tom", 22));
        set.add(new Cat("tom", 17));
        set.add(new Cat("tom", 24));
        set.add(new Cat("tom", 19));
        set.add(new Cat("tom", 18));
        set.add(new Cat("jack", 24));
        for (Cat cat : set) {
            System.out.println(cat);
        }

image.png

从根节点20开始开始找到左节点18，然后将18当作当前节点找左节点17，发现没有左节点了取出17.然后找18，19，找20，找22，找23，找24

当然上面写的还是有些问题，我们将最后一个cat的name改成jack，发现还是会被过滤掉。因为这里我们只对age进行了比较，没对name做判断。
将compareTo方法改造一下，如果年龄相等，再对姓名做比较。如果姓名也一样那就返回0，也就会被过滤掉了。

    @Override
    public int compareTo(Cat o) {
        int num=this.age-o.age;
        int num2=num==0?this.name.compareTo(o.name):num;
        return num2;
    }
    

如果想逆序输出compareTo就直接返回-1，想正序输出就返回1。

由于底层将key转成了Comparable，那么我们就知道TreeSet是不能添加null的，TreeMap的key是不能为null的，vaule可以为null。（编译不报错，运行报错，有点坑。）

2、比较器排序

TreeSet<Cat> set = new TreeSet<Cat>(new Comparator<Cat>() {
            @Override
            public int compare(Cat o1, Cat o2) {
                int num=o1.age-o2.age;
                int num2=num==0?o1.name.compareTo(o2.name):num;
                return num2;
            }
            
});

new 一个Comparator的匿名内部类放进构造方法就可以了，其他基本一样。