Java集合框架(12): TreeSet源码分析

发表于   |   分类于 
1
2
public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

简介

TreeSet是基于TreeMap实现的，它的作用是提供有序的Set集合，其中的元素支持两种排序方式：自然排序和Comparator方式。

TreeSet为基本操作(add、remove和contains)提供受保证的复杂度$O(\log{N})$。是非线程安全的。

源码分析

属性

1
2
3
4
// The backing map
   private transient NavigableMap<E,Object> m;
   // Dummy value to associate with an Object in the backing Map
   private static final Object PRESENT = new Object();

构造方法

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
/**
 * default修饰，不对外公开的
 */
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
/**
 * 默认底层实现使用TreeMap
 */
public TreeSet() {
    this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}
public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

方法

迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 返回TreeSet的顺序排列的迭代器
 * Returns an iterator over the elements in this set in ascending order.
 */
public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();
}
/**
 * 返回TreeSet的逆序排列的迭代器
 * Returns an iterator over the elements in this set in descending order.
 */
public Iterator<E> descendingIterator() {
    return m.descendingKeySet().iterator();
}

contains

1
2
3
public boolean contains(Object o) {
    return m.containsKey(o);
}

add

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

remove

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