第1部分 TreeSet介紹
TreeSet簡介
TreeSet 是一個有序的集合，它的作用是提供有序的Set集合。它繼承于AbstractSet抽象類，實現了NavigableSet<E>, Cloneable, java.io.Serializable接口。
TreeSet 繼承于AbstractSet，所以它是一個Set集合，具有Set的屬性和方法。
TreeSet 實現了NavigableSet接口，意味著它支持一系列的導航方法。比如查找與指定目標最匹配項。
TreeSet 實現了Cloneable接口，意味著它能被克隆。
TreeSet 實現了java.io.Serializable接口，意味著它支持序列化。
TreeSet是基于TreeMap實現的。TreeSet中的元素支持2種排序方式：自然排序 或者 根據創建TreeSet 時提供的 Comparator 進行排序。這取決于使用的構造方法。
TreeSet為基本操作（add、remove 和 contains）提供受保證的 log(n) 時間開銷。
另外，TreeSet是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。
TreeSet的構造函數
|
1
2
3
4
5
6
7
8
9
10
11
|
// 默認構造函數。使用該構造函數，TreeSet中的元素按照自然排序進行排列。TreeSet()// 創建的TreeSet包含collectionTreeSet(Collection<? extends E> collection)// 指定TreeSet的比較器TreeSet(Comparator<? super E> comparator)// 創建的TreeSet包含setTreeSet(SortedSet<E> set) |
TreeSet的API
|
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
|
boolean add(E object)boolean addAll(Collection<? extends E> collection)void clear()Object clone()boolean contains(Object object)E first()boolean isEmpty()E last()E pollFirst()E pollLast()E lower(E e)E floor(E e)E ceiling(E e)E higher(E e)boolean remove(Object object)int size()Comparator<? super E> comparator()Iterator<E> iterator()Iterator<E> descendingIterator()SortedSet<E> headSet(E end)NavigableSet<E> descendingSet()NavigableSet<E> headSet(E end, boolean endInclusive)SortedSet<E> subSet(E start, E end)NavigableSet<E> subSet(E start, boolean startInclusive, E end, boolean endInclusive)NavigableSet<E> tailSet(E start, boolean startInclusive)SortedSet<E> tailSet(E start) |
說明：
(01) TreeSet是有序的Set集合，因此支持add、remove、get等方法。
(02) 和NavigableSet一樣，TreeSet的導航方法大致可以區分為兩類，一類時提供元素項的導航方法，返回某個元素；另一類時提供集合的導航方法，返回某個集合。
lower、floor、ceiling 和 higher 分別返回小于、小于等于、大于等于、大于給定元素的元素，如果不存在這樣的元素，則返回 null。
第2部分 TreeSet數據結構
TreeSet的繼承關系
|
1
2
3
4
5
6
7
|
java.lang.Object ? java.util.AbstractCollection<E> ? java.util.AbstractSet<E> ? java.util.TreeSet<E>public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable{} |
TreeSet與Collection關系如下圖：
從圖中可以看出：
(01) TreeSet繼承于AbstractSet，并且實現了NavigableSet接口。
(02) TreeSet的本質是一個"有序的，并且沒有重復元素"的集合，它是通過TreeMap實現的。TreeSet中含有一個"NavigableMap類型的成員變量"m，而m實際上是"TreeMap的實例"。
第3部分 TreeSet源碼解析(基于JDK1.6.0_45)
為了更了解TreeSet的原理，下面對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
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
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
|
package java.util;public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable{ // NavigableMap對象 private transient NavigableMap<E,Object> m; // TreeSet是通過TreeMap實現的， // PRESENT是鍵-值對中的值。 private static final Object PRESENT = new Object(); // 不帶參數的構造函數。創建一個空的TreeMap public TreeSet() { this(new TreeMap<E,Object>()); } // 將TreeMap賦值給 "NavigableMap對象m" TreeSet(NavigableMap<E,Object> m) { this.m = m; } // 帶比較器的構造函數。 public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<E,Object>(comparator)); } // 創建TreeSet，并將集合c中的全部元素都添加到TreeSet中 public TreeSet(Collection<? extends E> c) { this(); // 將集合c中的元素全部添加到TreeSet中 addAll(c); } // 創建TreeSet，并將s中的全部元素都添加到TreeSet中 public TreeSet(SortedSet<E> s) { this(s.comparator()); addAll(s); } // 返回TreeSet的順序排列的迭代器。 // 因為TreeSet時TreeMap實現的，所以這里實際上時返回TreeMap的“鍵集”對應的迭代器 public Iterator<E> iterator() { return m.navigableKeySet().iterator(); } // 返回TreeSet的逆序排列的迭代器。 // 因為TreeSet時TreeMap實現的，所以這里實際上時返回TreeMap的“鍵集”對應的迭代器 public Iterator<E> descendingIterator() { return m.descendingKeySet().iterator(); } // 返回TreeSet的大小 public int size() { return m.size(); } // 返回TreeSet是否為空 public boolean isEmpty() { return m.isEmpty(); } // 返回TreeSet是否包含對象(o) public boolean contains(Object o) { return m.containsKey(o); } // 添加e到TreeSet中 public boolean add(E e) { return m.put(e, PRESENT)==null; } // 刪除TreeSet中的對象o public boolean remove(Object o) { return m.remove(o)==PRESENT; } // 清空TreeSet public void clear() { m.clear(); } // 將集合c中的全部元素添加到TreeSet中 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<? super E> cc = (Comparator<? super E>) 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，實際上是通過TreeMap的subMap()實現的。 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new TreeSet<E>(m.subMap(fromElement, fromInclusive, toElement, toInclusive)); } // 返回Set的頭部，范圍是：從頭部到toElement。 // inclusive是是否包含toElement的標志 public NavigableSet<E> headSet(E toElement, boolean inclusive) { return new TreeSet<E>(m.headMap(toElement, inclusive)); } // 返回Set的尾部，范圍是：從fromElement到結尾。 // inclusive是是否包含fromElement的標志 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { return new TreeSet<E>(m.tailMap(fromElement, inclusive)); } // 返回子Set。范圍是：從fromElement(包括)到toElement(不包括)。 public SortedSet<E> subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); } // 返回Set的頭部，范圍是：從頭部到toElement(不包括)。 public SortedSet<E> headSet(E toElement) { return headSet(toElement, false); } // 返回Set的尾部，范圍是：從fromElement到結尾(不包括)。 public SortedSet<E> tailSet(E fromElement) { return tailSet(fromElement, true); } // 返回Set的比較器 public Comparator<? super E> comparator() { return m.comparator(); } // 返回Set的第一個元素 public E first() { return m.firstKey(); } // 返回Set的最后一個元素 public E first() { public E last() { return m.lastKey(); } // 返回Set中小于e的最大元素 public E lower(E e) { return m.lowerKey(e); } // 返回Set中小于/等于e的最大元素 public E floor(E e) { return m.floorKey(e); } // 返回Set中大于/等于e的最小元素 public E ceiling(E e) { return m.ceilingKey(e); } // 返回Set中大于e的最小元素 public E higher(E e) { return m.higherKey(e); } // 獲取第一個元素，并將該元素從TreeMap中刪除。 public E pollFirst() { Map.Entry<E,?> e = m.pollFirstEntry(); return (e == null)? null : e.getKey(); } // 獲取最后一個元素，并將該元素從TreeMap中刪除。 public E pollLast() { Map.Entry<E,?> e = m.pollLastEntry(); return (e == null)? null : e.getKey(); } // 克隆一個TreeSet，并返回Object對象 public Object clone() { TreeSet<E> clone = null; try { clone = (TreeSet<E>) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } clone.m = new TreeMap<E,Object>(m); return clone; } // java.io.Serializable的寫入函數 // 將TreeSet的“比較器、容量，所有的元素值”都寫入到輸出流中 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { s.defaultWriteObject(); // 寫入比較器 s.writeObject(m.comparator()); // 寫入容量 s.writeInt(m.size()); // 寫入“TreeSet中的每一個元素” for (Iterator i=m.keySet().iterator(); i.hasNext(); ) s.writeObject(i.next()); } // java.io.Serializable的讀取函數：根據寫入方式讀出 // 先將TreeSet的“比較器、容量、所有的元素值”依次讀出 private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden stuff s.defaultReadObject(); // 從輸入流中讀取TreeSet的“比較器” Comparator<? super E> c = (Comparator<? super E>) s.readObject(); TreeMap<E,Object> tm; if (c==null) tm = new TreeMap<E,Object>(); else tm = new TreeMap<E,Object>(c); m = tm; // 從輸入流中讀取TreeSet的“容量” int size = s.readInt(); // 從輸入流中讀取TreeSet的“全部元素” tm.readTreeSet(size, s, PRESENT); } // TreeSet的序列版本號 private static final long serialVersionUID = -2479143000061671589L;} |
總結：
(01) TreeSet實際上是TreeMap實現的。當我們構造TreeSet時；若使用不帶參數的構造函數，則TreeSet的使用自然比較器；若用戶需要使用自定義的比較器，則需要使用帶比較器的參數。
(02) TreeSet是非線程安全的。
(03) TreeSet實現java.io.Serializable的方式。當寫入到輸出流時，依次寫入“比較器、容量、全部元素”；當讀出輸入流時，再依次讀取。
第4部分 TreeSet遍歷方式
4.1 Iterator順序遍歷
|
1
2
3
|
for(Iterator iter = set.iterator(); iter.hasNext(); ) { iter.next();} |
4.2 Iterator順序遍歷
|
1
2
3
4
|
// 假設set是TreeSet對象for(Iterator iter = set.descendingIterator(); iter.hasNext(); ) { iter.next();} |
4.3 for-each遍歷HashSet
|
1
2
3
4
|
// 假設set是TreeSet對象，并且set中元素是String類型String[] arr = (String[])set.toArray(new String[0]);for (String str:arr) System.out.printf("for each : %s\n", str); |
TreeSet不支持快速隨機遍歷，只能通過迭代器進行遍歷！
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
import java.util.*;/** * @desc TreeSet的遍歷程序 * * @author skywang * @email [email protected] */public class TreeSetIteratorTest { public static void main(String[] args) { TreeSet set = new TreeSet(); set.add("aaa"); set.add("aaa"); set.add("bbb"); set.add("eee"); set.add("ddd"); set.add("ccc"); // 順序遍歷TreeSet ascIteratorThroughIterator(set) ; // 逆序遍歷TreeSet descIteratorThroughIterator(set); // 通過for-each遍歷TreeSet。不推薦！此方法需要先將Set轉換為數組 foreachTreeSet(set); } // 順序遍歷TreeSet public static void ascIteratorThroughIterator(TreeSet set) { System.out.print("\n ---- Ascend Iterator ----\n"); for(Iterator iter = set.iterator(); iter.hasNext(); ) { System.out.printf("asc : %s\n", iter.next()); } } // 逆序遍歷TreeSet public static void descIteratorThroughIterator(TreeSet set) { System.out.printf("\n ---- Descend Iterator ----\n"); for(Iterator iter = set.descendingIterator(); iter.hasNext(); ) System.out.printf("desc : %s\n", (String)iter.next()); } // 通過for-each遍歷TreeSet。不推薦！此方法需要先將Set轉換為數組 private static void foreachTreeSet(TreeSet set) { System.out.printf("\n ---- For-each ----\n"); String[] arr = (String[])set.toArray(new String[0]); for (String str:arr) System.out.printf("for each : %s\n", str); }} |
運行結果：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
---- Ascend Iterator ----asc : aaaasc : bbbasc : cccasc : dddasc : eee ---- Descend Iterator ----desc : eeedesc : ddddesc : cccdesc : bbbdesc : aaa ---- For-each ----for each : aaafor each : bbbfor each : cccfor each : dddfor each : eee |
第5部分 TreeSet示例
下面通過實例學習如何使用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
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
|
import java.util.*;/** * @desc TreeSet的API測試 * * @author skywang * @email [email protected] */public class TreeSetTest { public static void main(String[] args) { testTreeSetAPIs(); } // 測試TreeSet的api public static void testTreeSetAPIs() { String val; // 新建TreeSet TreeSet tSet = new TreeSet(); // 將元素添加到TreeSet中 tSet.add("aaa"); // Set中不允許重復元素，所以只會保存一個“aaa” tSet.add("aaa"); tSet.add("bbb"); tSet.add("eee"); tSet.add("ddd"); tSet.add("ccc"); System.out.println("TreeSet:"+tSet); // 打印TreeSet的實際大小 System.out.printf("size : %d\n", tSet.size()); // 導航方法 // floor(小于、等于) System.out.printf("floor bbb: %s\n", tSet.floor("bbb")); // lower(小于) System.out.printf("lower bbb: %s\n", tSet.lower("bbb")); // ceiling(大于、等于) System.out.printf("ceiling bbb: %s\n", tSet.ceiling("bbb")); System.out.printf("ceiling eee: %s\n", tSet.ceiling("eee")); // ceiling(大于) System.out.printf("higher bbb: %s\n", tSet.higher("bbb")); // subSet() System.out.printf("subSet(aaa, true, ccc, true): %s\n", tSet.subSet("aaa", true, "ccc", true)); System.out.printf("subSet(aaa, true, ccc, false): %s\n", tSet.subSet("aaa", true, "ccc", false)); System.out.printf("subSet(aaa, false, ccc, true): %s\n", tSet.subSet("aaa", false, "ccc", true)); System.out.printf("subSet(aaa, false, ccc, false): %s\n", tSet.subSet("aaa", false, "ccc", false)); // headSet() System.out.printf("headSet(ccc, true): %s\n", tSet.headSet("ccc", true)); System.out.printf("headSet(ccc, false): %s\n", tSet.headSet("ccc", false)); // tailSet() System.out.printf("tailSet(ccc, true): %s\n", tSet.tailSet("ccc", true)); System.out.printf("tailSet(ccc, false): %s\n", tSet.tailSet("ccc", false)); // 刪除“ccc” tSet.remove("ccc"); // 將Set轉換為數組 String[] arr = (String[])tSet.toArray(new String[0]); for (String str:arr) System.out.printf("for each : %s\n", str); // 打印TreeSet System.out.printf("TreeSet:%s\n", tSet); // 遍歷TreeSet for(Iterator iter = tSet.iterator(); iter.hasNext(); ) { System.out.printf("iter : %s\n", iter.next()); } // 刪除并返回第一個元素 val = (String)tSet.pollFirst(); System.out.printf("pollFirst=%s, set=%s\n", val, tSet); // 刪除并返回最后一個元素 val = (String)tSet.pollLast(); System.out.printf("pollLast=%s, set=%s\n", val, tSet); // 清空HashSet tSet.clear(); // 輸出HashSet是否為空 System.out.printf("%s\n", tSet.isEmpty()?"set is empty":"set is not empty"); }} |
運行結果：
|
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
|
TreeSet:[aaa, bbb, ccc, ddd, eee]size : 5floor bbb: bbblower bbb: aaaceiling bbb: bbbceiling eee: eeehigher bbb: cccsubSet(aaa, true, ccc, true): [aaa, bbb, ccc]subSet(aaa, true, ccc, false): [aaa, bbb]subSet(aaa, false, ccc, true): [bbb, ccc]subSet(aaa, false, ccc, false): [bbb]headSet(ccc, true): [aaa, bbb, ccc]headSet(ccc, false): [aaa, bbb]tailSet(ccc, true): [ccc, ddd, eee]tailSet(ccc, false): [ddd, eee]for each : aaafor each : bbbfor each : dddfor each : eeeTreeSet:[aaa, bbb, ddd, eee]iter : aaaiter : bbbiter : ddditer : eeepollFirst=aaa, set=[bbb, ddd, eee]pollLast=eee, set=[bbb, ddd]set is empty |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
