TreeSet
简介
Java注释
A {@link NavigableSet} implementation based on a {@link TreeMap}.The elements are ordered using their {@linkplain Comparable natural ordering}, or by a {@link Comparator} provided at set creation time, depending on which constructor is used.
翻译
基于
TreeMap的NavigableSet实现。元素使用其可比自然排序进行排序，或通过在集合创建时提供的Comparator进行排序，具体取决于所使用的构造函数。
TreeSet底层是采用NavigableMap实现的一种Set，所以它是有序的，同样也是非线程安全的。
类图
源码
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
//元素存储在NavigableMap中
private transient NavigableMap<E,Object> m;
//存放在value处占位
private static final Object PRESENT = new Object();
//使用NavigableMap构造
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
//无参构造
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);
}
//指定SortedSet构造
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
//迭代器
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}
//逆序迭代器
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
}
//逆序返回一个新的TreeSet
public NavigableSet<E> descendingSet() {
return new TreeSet<>(m.descendingMap());
}
//元素个数
public int size() {
return m.size();
}
//是否空集合
public boolean isEmpty() {
return m.isEmpty();
}
//是否包含某元素
public boolean contains(Object o) {
return m.containsKey(o);
}
//添加元素
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
//移除元素
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
//清空集合
public void clear() {
m.clear();
}
//添加集合中所有元素
public boolean addAll(Collection<? extends E> c) {
// Use linear-time version if applicable
if (m.size()==0 && c.size() > 0 &&
c instanceof SortedSet &&
m instanceof TreeMap) {
SortedSet<? extends E> set = (SortedSet<? extends E>) c;
TreeMap<E,Object> map = (TreeMap<E, Object>) m;
Comparator<?> cc = set.comparator();
Comparator<? super E> mc = map.comparator();
if (cc==mc || (cc != null && cc.equals(mc))) {
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
return super.addAll(c);
}
//子set
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
//头set
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new TreeSet<>(m.headMap(toElement, inclusive));
}
//尾set
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
return new TreeSet<>(m.tailMap(fromElement, inclusive));
}
//子set
public SortedSet<E> subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
}
//头set
public SortedSet<E> headSet(E toElement) {
return headSet(toElement, false);
}
//尾set
public SortedSet<E> tailSet(E fromElement) {
return tailSet(fromElement, true);
}
//比较器
public Comparator<? super E> comparator() {
return m.comparator();
}
//返回最小的元素
public E first() {
return m.firstKey();
}
//返回最大的元素
public E last() {
return m.lastKey();
}
// NavigableSet API methods
//返回小于e的最大的元素
public E lower(E e) {
return m.lowerKey(e);
}
//返回大于等于e的最小的元素
public E floor(E e) {
return m.floorKey(e);
}
//返回大于等于e的最小的元素
public E ceiling(E e) {
return m.ceilingKey(e);
}
//返回大于e的最小的元素
public E higher(E e) {
return m.higherKey(e);
}
//弹出最小的元素
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();
}
//克隆方法
@SuppressWarnings("unchecked")
public Object clone() {
TreeSet<E> clone;
try {
clone = (TreeSet<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
clone.m = new TreeMap<>(m);
return clone;
}
//序列化
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden stuff
s.defaultWriteObject();
// Write out Comparator
s.writeObject(m.comparator());
// Write out size
s.writeInt(m.size());
// Write out all elements in the proper order.
for (E e : m.keySet())
s.writeObject(e);
}
//反序列化
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden stuff
s.defaultReadObject();
// Read in Comparator
@SuppressWarnings("unchecked")
Comparator<? super E> c = (Comparator<? super E>) s.readObject();
// Create backing TreeMap
TreeMap<E,Object> tm = new TreeMap<>(c);
m = tm;
// Read in size
int size = s.readInt();
tm.readTreeSet(size, s, PRESENT);
}
//可分割的迭代器
public Spliterator<E> spliterator() {
return TreeMap.keySpliteratorFor(m);
}
//序列化ID
private static final long serialVersionUID = -2479143000061671589L;
}
总结
TreeSet底层使用NavigableMap存储元素；TreeSet是有序的；TreeSet是非线程安全的；TreeSet实现了NavigableSet接口，而NavigableSet继承自SortedSet接口；TreeSet实现了SortedSet接口；
