TreeSet详解和使用示例_动力节点Java学院整理
第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的构造函数
// 默认构造函数。使用该构造函数,treeset中的元素按照自然排序进行排列。 treeset() // 创建的treeset包含collection treeset(collection<? extends e> collection) // 指定treeset的比较器 treeset(comparator<? super e> comparator) // 创建的treeset包含set treeset(sortedset<e> set)
treeset的api
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的继承关系
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源码代码作出分析。
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顺序遍历
for(iterator iter = set.iterator(); iter.hasnext(); ) { iter.next(); }
4.2 iterator顺序遍历
// 假设set是treeset对象 for(iterator iter = set.descendingiterator(); iter.hasnext(); ) { iter.next(); }
4.3 for-each遍历hashset
// 假设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遍历测试程序如下:
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); } // 顺序遍历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); } }
运行结果:
---- ascend iterator ---- asc : aaa asc : bbb asc : ccc asc : ddd asc : eee ---- descend iterator ---- desc : eee desc : ddd desc : ccc desc : bbb desc : aaa ---- for-each ---- for each : aaa for each : bbb for each : ccc for each : ddd for each : eee
第5部分 treeset示例
下面通过实例学习如何使用treeset
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"); } }
运行结果:
treeset:[aaa, bbb, ccc, ddd, eee] size : 5 floor bbb: bbb lower bbb: aaa ceiling bbb: bbb ceiling eee: eee higher bbb: ccc subset(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 : aaa for each : bbb for each : ddd for each : eee treeset:[aaa, bbb, ddd, eee] iter : aaa iter : bbb iter : ddd iter : eee pollfirst=aaa, set=[bbb, ddd, eee] polllast=eee, set=[bbb, ddd] set is empty
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
推荐阅读
-
TreeSet详解和使用示例_动力节点Java学院整理
-
Java Thread中start()和run()的区别_动力节点Java学院整理
-
BufferedInputStream(缓冲输入流)详解_动力节点Java学院整理
-
File的API和常用方法详解_动力节点Java学院整理
-
Java 中的FileReader和FileWriter源码分析_动力节点Java学院整理
-
Java中的InputStreamReader和OutputStreamWriter源码分析_动力节点Java学院整理
-
Java线程的生命周期和状态控制_动力节点Java学院整理
-
ThreadLocal使用案例_动力节点Java学院整理
-
Java中使用jaxp进行sax解析_动力节点Java学院整理
-
PipedWriter和PipedReader源码分析_动力节点Java学院整理