1.TreeSet概述

TreeSet实现了Set接口，与HashSet不同的时，他是有序集合，底层是一个TreeMap

默认按照升序排列，代码示例：

TreeSet treeSet = new TreeSet();
treeSet.add("tom");
treeSet.add("lili");
treeSet.add("kangkang");
treeSet.add("abc");
System.out.println(treeSet);
---------------------------
输出：
[abc, kangkang, lili, tom]
1
2
3
4
5
6
7
8
9

---

2.自定义排序规则

TreeSet可以在初始化对象的时候传入一个接口对象，并对属性进行赋值

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

---

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}
1
2
3
4
5
6
7
8
9

我们可以通过内部类的形式传入一个比较器，借助字符串的compareTo方法对TreeSet的排序进行自定义

例如，如下是一个升序排序：

TreeSet treeSet = new TreeSet(new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        return ((String) o1).compareTo((String) o2);
    }
});
treeSet.add("tom");
treeSet.add("lili");
treeSet.add("kangkang");
treeSet.add("abc");
System.out.println(treeSet);
1
2
3
4
5
6
7
8
9
10
11

现在，更改一下o1和o2的位置，排序变成了逆序排序：

TreeSet treeSet = new TreeSet(new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        return ((String) o2).compareTo((String) o1);
    }
});
treeSet.add("tom");
treeSet.add("lili");
treeSet.add("kangkang");
treeSet.add("abc");
System.out.println(treeSet);
1
2
3
4
5
6
7
8
9
10
11

---

3.添加元素排序机制源码解读

首先会进入TreeSet的add方法：

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}
1
2
3

之后，进入TreeMap的put方法：

public V put(K key, V value) {
    return put(key, value, true);
}
1
2
3

继续步入，直到添加了第二个元素，再次进入接受比较器的代码（核心）：🍳

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 {
            V oldValue = t.value;
            if (replaceOld || oldValue == null) {
                t.value = value;
            }
            return oldValue;
        }
    } while (t != null);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

接下来我们来解析一下上面这段代码：

接收了传入的比较器：

Comparator<? super K> cpr = comparator;
1

此时的cpr不为空，会进入if执行：

执行cpr.compare，会动态绑定到我们传入的匿名内部类的compare方法，随后传入两个元素key和t.key进行比较器的比较🐱‍💻

cmp = cpr.compare(key, t.key);
1

---

4.发散思维

注意：当我们传入比较器到TreeSet中时，如果TreeSet判断存在两个元素是相等的，则不会进行添加操作，怎么才算元素相等，取决于我们传入的比较器👨🏻

例如：我们想实现一个功能，根据元素字符串的长度进行升序排序，那么我们可以这样编写比较器：

TreeSet treeSet1 = new TreeSet(new Comparator() {
    @Override
    public int compare(Object o1, Object o2) {
        return ((String) o1).length() - ((String) o2).length();
    }
});
1
2
3
4
5
6

那么此时，元素的长度将会变成元素相等的条件，故我们执行如下代码块：

treeSet1.add("tom");
treeSet1.add("lili");
treeSet1.add("wangwei");
treeSet1.add("wu");
treeSet1.add("zhan");
System.out.println(treeSet1);
---------------------
输出：
[wu, tom, lili, wangwei]
1
2
3
4
5
6
7
8
9

会发现，“zhan”元素并没有添加成功！🍤

注意：对于TreeMap的此种情况，他的Key值依然不会添加成功，但是会替换value的值

---

5.TreeMap

TreeMap和TreeSet差距不大，TreeMap保存键值对，默认按照键值升序排序

TreeMap treeMap = new TreeMap();
treeMap.put("jack","杰克");
treeMap.put("tom","汤姆");
treeMap.put("smith","史密斯");
System.out.println(treeMap);
----------------------------------
输出：
{jack=杰克, smith=史密斯, tom=汤姆}
1
2
3
4
5
6
7
8

---

6.TreeMap的自定义排序

和TreeSet一样，TreeMap也可以传入你个匿名内部类，实现自定义排序的效果

例如：按照Key值升序排序：

TreeMap treeMap = new TreeMap(new Comparator() {
    @Override
    public int compare(Object o, Object t1) {
        return ((String) o).compareTo((String) t1);
    }
});
treeMap.put("jack","杰克");
treeMap.put("tom","汤姆");
treeMap.put("smith","史密斯");
System.out.println(treeMap);
1
2
3
4
5
6
7
8
9
10

按照Key值逆序排序：

TreeMap treeMap = new TreeMap(new Comparator() {
    @Override
    public int compare(Object o, Object t1) {
        return ((String) t1).compareTo((String) o);
    }
});
treeMap.put("jack","杰克");
treeMap.put("tom","汤姆");
treeMap.put("smith","史密斯");
System.out.println(treeMap);
1
2
3
4
5
6
7
8
9
10

按照字符串长度从小到大排序：

TreeMap treeMap = new TreeMap(new Comparator() {
    @Override
    public int compare(Object o, Object t1) {
        return ((String) o).length() - ((String) t1).length();
    }
});
treeMap.put("jack","杰克");
treeMap.put("tom","汤姆");
treeMap.put("smith","史密斯");
System.out.println(treeMap);
1
2
3
4
5
6
7
8
9
10

TreeMap与TreeSet的源码大同小异