TreeSet底层源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>{
    //外置比较器
    private final Comparator<? super K> comparator;
    
    public TreeMap() {
        comparator = null;
    }
    
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
    
    //key - new Student("麻生希", '女', 25, "2301", "001")
    //value - PRESENT(TreeSet中的占位对象)
    public V put(K key, V value) {
        //获取外置比较器
        Comparator<? super K> cpr = comparator;
        if(cpr != null){//说明有外置比较器
            ...执行外置比较器中的排序规则...
            cpr.compare();
        }else{//说明没有外置比较器
            ...执行内置比较器中的排序规则...
            key.comparTo()
        }
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>{
    
    private transient NavigableMap<E,Object> m;
    //占位对象
    private static final Object PRESENT = new Object();
    
    public TreeSet() {
        this(new TreeMap<E,Object>());//注意：使用TreeMap的无参构造创建TreeMap对象
    }
    
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));//注意：使用TreeMap的有参构造创建TreeMap对象
    }
    
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
    
    //e - new Student("麻生希", '女', 25, "2301", "001")
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
    
    
}
1
2
3
4
5
6
场景一：
    TreeSet<Student> set = new TreeSet<>();
		
    set.add(new Student("麻生希", '女', 25, "2301", "001"));   
    set.add(new Student("椎名空", '女', 20, "2301", "002"));   
    set.add(new Student("水菜丽", '女', 27, "2301", "003"));  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
场景二：
    TreeSet<Student> set = new TreeSet<>(new Comparator<Student>() {

			//排序规则 - 按照名字排序，名字长度一致按照年龄排序
			@Override
			public int compare(Student o1, Student o2) {
				if(o1.equals(o2)){
					return 0;
				}
				
				int nameLen1 = o1.getName().length();
				int nameLen2 = o2.getName().length();
				if(nameLen1 != nameLen2){
					return nameLen1 - nameLen2;
				}
				
				int age1 = o1.getAge();
				int age2 = o2.getAge();
				if(age1 != age2){
					return age1 - age2;
				}
				return 1;
			}
		});
		
		set.add(new Student("麻生希", '女', 25, "2301", "001"));   
		set.add(new Student("椎名空", '女', 20, "2301", "002"));   
		set.add(new Student("水菜丽", '女', 27, "2301", "003"));

  1. TreeSet底层是将元素存入TreeMapkey的位置

  2. TreeMap中先判断是否有外置比较器，再判断内置比较器

    （说明外置比较器的优先级别高于内置比较器）