第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
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持移动技术网。
如对本文有疑问， 点击进行留言回复！！
ScrollView和RecyclerView的滑动事件处理
配置JAVA环境+安装Android Studio全过程+踩坑记录
Android P Camera2当SD卡被拔出来自动切换到内部存储
android 多个edittext 判空监听 让Button动态是否可点击
Android开源项目滚轮选择器WheelPicker的基本用法总结
网友评论