TreeSet源码解析
程序员文章站
2022-05-14 13:08:18
...
来源:
Java编程的逻辑
1 实现原理
1.1 构造方法
TreeSet的基本构造方法有两个:
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
默认构造方法假定元素实现了Comparable接口,第二个使用传入的比较器,不要求元素实现Comparable。
TreeSet的其他构造方法为:
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
前两个都是以一个已有的集合为参数,将其中的所有元素添加到当前TreeSet,区别在于,在第一个中,比较器为null,假定元素实现了Comparable接口,而第二个中,比较器设为和参数SortedSet中的一样。
第三个不是public的,是内部用的。
1.2 SortedSet接口
public interface SortedSet<E> extends Set<E> {
Comparator<? super E> comparator();
SortedSet<E> subSet(E fromElement, E toElement);
SortedSet<E> headSet(E toElement);
SortedSet<E> tailSet(E fromElement);
E first();
E last();
}
1.3 NavigableSet
扩展了SortedSet,主要增加了一些查找邻近元素的方法,比如:
E floor(E e); //返回小于等于e的最大元素
E lower(E e); // 返回小于e的最大元素
E ceiling(E e); //返回大于等于e的最小元素
E higher(E e); //返回大于e的最小元素
1.4 内部组成
TreeSet的内部有如下成员:
private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();
m就是背后的那个TreeMap,这里用的是更为通用的接口类型NavigableMap,PRESENT就是那个固定的共享值。
TreeSet的方法实现主要就是调用m的方法
1.5 add
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
就是调用map的put方法,元素e用作键,值就是固定值PRESENT,put返回null表示原来没有对应的键,添加成功了。
1.6 contains
public boolean contains(Object o) {
return m.containsKey(o);
}
检查map中是否包含对应的键。
1.7 remove
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
调用map的remove方法,返回值为PRESENT表示原来有对应的键且删除成功了。
1.8 子集视图
subSet方法的代码:
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
先调用subMap方法获取NavigatebleMap的子集,然后调用内部的TreeSet构造方法。
1.9 头尾操作
public E first() {
return m.firstKey();
}
public E last() {
return m.lastKey();
}
public E pollFirst() {
Map.Entry<E,?> e = m.pollFirstEntry();
return (e == null) ? null : e.getKey();
}
public E pollLast() {
Map.Entry<E,?> e = m.pollLastEntry();
return (e == null) ? null : e.getKey();
}
1.10 逆序遍历
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
}
public NavigableSet<E> descendingSet() {
return new TreeSet<>(m.descendingMap());
}
2 特点分析
与HashSet相比,TreeSet同样实现了Set接口,但内部基于TreeMap实现,而TreeMap基于大致平衡的排序二叉树 - 红黑树,这决定了它有如下特点:
- 没有重复元素
- 添加、删除元素、判断元素是否存在,效率比较高,为O(log2(N)),N为元素个数。
- 有序,TreeSet同样实现了SortedSet和NavigatableSet接口,可以方便的根据顺序进行查找和操作,如第一个、最后一个、某一取值范围、某一值的邻近元素等。
- 为了有序,TreeSet要求元素实现Comparable接口或通过构造方法提供一个Comparator对象。