欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【java基础】TreeSet源码分析

程序员文章站 2022-05-14 13:08:06
...

TreeSet底层是通过TreeMap来实现的所有功能。

 private transient NavigableMap<E,Object> m;//NavigableMap是TreeMap的父类

   //定义一个静态常量,TreeSet使用TreeMap实现增加的时候,(key,value)中的value都是这个对象。
    private static final Object PRESENT = new Object();

下面来看构造函数

TreeSet(NavigableMap<E,Object> m) {
   this.m = m;
}
//无参构造函数,新建一个TreeMap对象传给m
public TreeSet() {
   this(new TreeMap<E,Object>());
}
//通过传入比较器来创建一个TreeMap对象传给m,我们知道TreeMap可以使用比较器或者自然顺序实现比较排序。
public TreeSet(Comparator<? super E> comparator) {
   this(new TreeMap<>(comparator));
}
//通过传入一个集合,调用无参构造函数,然后将集合所有元素有序插入到m
public TreeSet(Collection<? extends E> c) {
   this();
   addAll(c);
}
//传入一个实现了SortedSet接口的类,而SortedSet继承了Iterable接口,需要实现一个返回迭代器的函数。
public TreeSet(SortedSet<E> s) {
   this(s.comparator());
   addAll(s);
}

TreeSet元素插入

public boolean add(E e) {
    //通过TreeMap实现插入,key是e,值是上面提到的静态常量PRESENT
   return m.put(e, PRESENT)==null;
}

这里说一下,TreeMap是通过自然顺序,或者比较器进行比较排序,当构造器没有传入比较器时候,就需要key实现Comparable接口,实现自然排序,否则会报ClassCastException.这里TreeSet底层就是通过TreeMap实现的,所以需要TreeSet类型参数实现了 Comparable接口,或者新增的元素实现了Comparable接口。

TreeSet元素的删除

public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }

TreeSet元素的遍历

public static void main(String[] args) {
		TreeSet<Integer> t=new TreeSet<Integer>();
		t.add(1);
		t.add(2);
		t.add(3);
		
		//正序遍历
		for(int i:t){
			System.out.println(i);
		}
		//倒叙遍历
		for(int i:t.descendingSet()){
			System.out.println(i);
		}
		
	}
///运行结果如下
1
2
3
3
2
1

TreeSet实现了AbstractSet类也就间接继承了Iterable接口,所以可以直接用foreach正序遍历,descendingSet()是反向遍历。

 

 

相关标签: TreeSet