第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
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
// 默认构造函数。使用该构造函数，TreeSet中的元素按照自然排序进行排列。TreeSet()// 创建的TreeSet包含collectionTreeSet(Collection<? extends E> collection)// 指定TreeSet的比较器TreeSet(Comparator<? super E> comparator)// 创建的TreeSet包含setTreeSet(SortedSet<E> set)TreeSet的APIboolean 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
|
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
|
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();// 不带参数的构造函数。创建一个空的TreeMappublic 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中的对象opublic boolean remove(Object o) {return m.remove(o)==PRESENT;}// 清空TreeSetpublic void clear() {m.clear();}// 将集合c中的全部元素添加到TreeSet中public boolean addAll(Collection<? extends E> c) {// Use linear-time version if applicableif (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 kuiwu-wang@163.com*/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);}// 顺序遍历TreeSetpublic 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()); }}// 逆序遍历TreeSetpublic 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
|
---- 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
|
import java.util.*;/** * @desc TreeSet的API测试 * * @author skywang * @email kuiwu-wang@163.com */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 |
补充：Java中关于使用TreeSet存储数据的自然排序和定制排序
一、题目
创建类的 5 个对象，并把这些对象放入 TreeSet 集合中（TreeSet 需使用泛型和不用泛型分别来定义）
分别按以下两种方式对集合中的元素进行排序，并遍历输出：
1、使 Employee 实现 Comparable 接口，并按 name 排序
2、创建 TreeSet 时传入 Comparator 对象，按生日日期的先后排序。
二、定义一个 Employee 类
|
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
|
/** * 该类包含：private 成员变量 name,age,birthday，其中 birthday 为 * MyDate 类的对象； * 并为每一个属性定义 getter, setter 方法； * 并重写 toString 方法输出 name, age, birthday * @author * @create 2021-01-22-15:00 */public class Employee implements Comparable<Employee> { private String name; private int age; private MyDate birthday; public Employee() { } public Employee(String name, int age, MyDate birthday) { this.name = name; this.age = age; this.birthday = birthday; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } public MyDate getBirthday() { return birthday; } public void setBirthday(MyDate birthday) { this.birthday = birthday; } @Override public String toString() { return "Employee{" + "name='" + name + '\'' + ", age=" + age + ", birthday=" + birthday + '}'; } //不用泛型// @Override// public int compareTo(Object o) {// if(o instanceof Employee){// Employee employee = (Employee) o;// return this.name.compareTo(employee.name);// }// throw new RuntimeException("输入的数据类型不一致");// } //使用泛型 @Override public int compareTo(Employee o) { return this.name.compareTo(o.name); }} |
三、MyDate 类
|
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
|
/** * MyDate 类包含: * private 成员变量 year,month,day；并为每一个属性定义 getter, setter * 方法； * @author * @create 2021-01-22-15:00 */public class MyDate implements Comparable<MyDate> { private int year; private int month; private int day; public MyDate() { } public MyDate(int year, int month, int day) { this.year = year; this.month = month; this.day = day; } @Override public String toString() { return "MyDate{" + "year=" + year + ", month=" + month + ", day=" + day + '}'; } public int getYear() { return year; } public void setYear(int year) { this.year = year; } public int getMonth() { return month; } public void setMonth(int month) { this.month = month; } public int getDay() { return day; } public void setDay(int day) { this.day = day; } @Override public int compareTo(MyDate o) { int minusYear= this.year-o.year; if (minusYear !=0){ return minusYear; } int minusMonth= this.month-o.month; if (minusMonth !=0){ return minusMonth; } return this.day-o.day; }} |
四、单元测试
（一）
|
1
2
3
4
5
6
7
8
9
10
11
12
|
@Test public void test1(){ TreeSet<Employee> set = new TreeSet<>(); set.add(new Employee("hh",23,new MyDate(1992,4,12))); set.add(new Employee("ff",43,new MyDate(1956,5,4))); set.add(new Employee("aa",27,new MyDate(1936,8,6))); set.add(new Employee("gg",38,new MyDate(1992,4,4))); Iterator<Employee> iterator = set.iterator(); while (iterator.hasNext()){ System.out.println(iterator.next()); } } |
结果如下：
（二）
|
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
|
@Test public void test2(){ TreeSet<Employee> set = new TreeSet<>(new Comparator<Employee>() { @Override public int compare(Employee e1, Employee e2) { //加上泛型 MyDate b1 = e1.getBirthday(); MyDate b2 = e2.getBirthday(); return b1.compareTo(b2); //不加泛型// if (o1 instanceof Employee && o2 instanceof Employee){// Employee m1 = (Employee) o1;// Employee m2 = (Employee) o2;// MyDate m1Birthday = m1.getBirthday();// MyDate m2Birthday = m2.getBirthday();//// int minusYear = m1Birthday.getYear()- m2Birthday.getYear();// if (minusYear!=0){// return minusYear;// }// int minusMonth = m1Birthday.getMonth()- m2Birthday.getMonth();// if (minusMonth!=0){// return minusMonth;// }// int minusDay = m1Birthday.getDay()- m2Birthday.getDay();// return minusDay;//// }// throw new RuntimeException("传入的数据类型不一致"); } }); set.add(new Employee("hh",23,new MyDate(1944,12,4))); set.add(new Employee("ff",43,new MyDate(1957,5,4))); set.add(new Employee("aa",27,new MyDate(1906,12,6))); set.add(new Employee("gg",38,new MyDate(1906,4,4))); Iterator<Employee> iterator = set.iterator(); while (iterator.hasNext()){ System.out.println(iterator.next()); } } |
结果如下：
以上为个人经验，希望能给大家一个参考，也希望大家多多支持服务器之家。如有错误或未考虑完全的地方，望不吝赐教。
原文链接：https://blog.csdn.net/a1439775520/article/details/95373610
