Java之 TreeSet的详细使用说明

2023-07-05 04:55:03 83

第1部分TreeSet介绍

TreeSet简介

TreeSet是一个有序的集合，它的作用是提供有序的Set集合。它继承于AbstractSet抽象类，实现了NavigableSet,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(Collectioncollection)
//指定TreeSet的比较器
TreeSet(Comparatorcomparator)
//创建的TreeSet包含set
TreeSet(SortedSetset)
TreeSet的API
booleanadd(Eobject)
booleanaddAll(Collectioncollection)
voidclear()
Objectclone()
booleancontains(Objectobject)
Efirst()
booleanisEmpty()
Elast()
EpollFirst()
EpollLast()
Elower(Ee)
Efloor(Ee)
Eceiling(Ee)
Ehigher(Ee)
booleanremove(Objectobject)
intsize()
Comparatorcomparator()
Iteratoriterator()
IteratordescendingIterator()
SortedSetheadSet(Eend)
NavigableSetdescendingSet()
NavigableSetheadSet(Eend,booleanendInclusive)
SortedSetsubSet(Estart,Eend)
NavigableSetsubSet(Estart,booleanstartInclusive,Eend,booleanendInclusive)
NavigableSettailSet(Estart,booleanstartInclusive)
SortedSettailSet(Estart)

说明：

(01)TreeSet是有序的Set集合，因此支持add、remove、get等方法。

(02)和NavigableSet一样，TreeSet的导航方法大致可以区分为两类，一类时提供元素项的导航方法，返回某个元素；另一类时提供集合的导航方法，返回某个集合。

lower、floor、ceiling和higher分别返回小于、小于等于、大于等于、大于给定元素的元素，如果不存在这样的元素，则返回null。

第2部分TreeSet数据结构

TreeSet的继承关系

java.lang.Object
↳java.util.AbstractCollection
↳java.util.AbstractSet
↳java.util.TreeSet
publicclassTreeSetextendsAbstractSet
implementsNavigableSet,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源码代码作出分析。

packagejava.util;
publicclassTreeSetextendsAbstractSet
implementsNavigableSet,Cloneable,java.io.Serializable
{
//NavigableMap对象
privatetransientNavigableMapm;

//TreeSet是通过TreeMap实现的，
//PRESENT是键-值对中的值。
privatestaticfinalObjectPRESENT=newObject();
//不带参数的构造函数。创建一个空的TreeMap
publicTreeSet(){
this(newTreeMap());
}
//将TreeMap赋值给"NavigableMap对象m"
TreeSet(NavigableMapm){
this.m=m;
}
//带比较器的构造函数。
publicTreeSet(Comparatorcomparator){
this(newTreeMap(comparator));
}
//创建TreeSet，并将集合c中的全部元素都添加到TreeSet中
publicTreeSet(Collectionc){
this();
//将集合c中的元素全部添加到TreeSet中
addAll(c);
}
//创建TreeSet，并将s中的全部元素都添加到TreeSet中
publicTreeSet(SortedSets){
this(s.comparator());
addAll(s);
}
//返回TreeSet的顺序排列的迭代器。
//因为TreeSet时TreeMap实现的，所以这里实际上时返回TreeMap的“键集”对应的迭代器
publicIteratoriterator(){
returnm.navigableKeySet().iterator();
}
//返回TreeSet的逆序排列的迭代器。
//因为TreeSet时TreeMap实现的，所以这里实际上时返回TreeMap的“键集”对应的迭代器
publicIteratordescendingIterator(){
returnm.descendingKeySet().iterator();
}
//返回TreeSet的大小
publicintsize(){
returnm.size();
}
//返回TreeSet是否为空
publicbooleanisEmpty(){
returnm.isEmpty();
}
//返回TreeSet是否包含对象(o)
publicbooleancontains(Objecto){
returnm.containsKey(o);
}
//添加e到TreeSet中
publicbooleanadd(Ee){
returnm.put(e,PRESENT)==null;
}
//删除TreeSet中的对象o
publicbooleanremove(Objecto){
returnm.remove(o)==PRESENT;
}
//清空TreeSet
publicvoidclear(){
m.clear();
}
//将集合c中的全部元素添加到TreeSet中
publicbooleanaddAll(Collectionc){
//Uselinear-timeversionifapplicable
if(m.size()==0&&c.size()>0&&
cinstanceofSortedSet&&
minstanceofTreeMap){
SortedSetset=(SortedSet)c;
TreeMapmap=(TreeMap)m;
Comparatorcc=(Comparator)set.comparator();
Comparatormc=map.comparator();
if(cc==mc||(cc!=null&&cc.equals(mc))){
map.addAllForTreeSet(set,PRESENT);
returntrue;
}
}
returnsuper.addAll(c);
}

//返回子Set，实际上是通过TreeMap的subMap()实现的。
publicNavigableSetsubSet(EfromElement,booleanfromInclusive,
EtoElement,booleantoInclusive){
returnnewTreeSet(m.subMap(fromElement,fromInclusive,
toElement,toInclusive));
}

//返回Set的头部，范围是：从头部到toElement。
//inclusive是是否包含toElement的标志
publicNavigableSetheadSet(EtoElement,booleaninclusive){
returnnewTreeSet(m.headMap(toElement,inclusive));
}

//返回Set的尾部，范围是：从fromElement到结尾。
//inclusive是是否包含fromElement的标志
publicNavigableSettailSet(EfromElement,booleaninclusive){
returnnewTreeSet(m.tailMap(fromElement,inclusive));
}

//返回子Set。范围是：从fromElement(包括)到toElement(不包括)。
publicSortedSetsubSet(EfromElement,EtoElement){
returnsubSet(fromElement,true,toElement,false);
}

//返回Set的头部，范围是：从头部到toElement(不包括)。
publicSortedSetheadSet(EtoElement){
returnheadSet(toElement,false);
}

//返回Set的尾部，范围是：从fromElement到结尾(不包括)。
publicSortedSettailSet(EfromElement){
returntailSet(fromElement,true);
}

//返回Set的比较器
publicComparatorcomparator(){
returnm.comparator();
}

//返回Set的第一个元素
publicEfirst(){
returnm.firstKey();
}

//返回Set的最后一个元素
publicEfirst(){
publicElast(){
returnm.lastKey();
}

//返回Set中小于e的最大元素
publicElower(Ee){
returnm.lowerKey(e);
}

//返回Set中小于/等于e的最大元素
publicEfloor(Ee){
returnm.floorKey(e);
}

//返回Set中大于/等于e的最小元素
publicEceiling(Ee){
returnm.ceilingKey(e);
}

//返回Set中大于e的最小元素
publicEhigher(Ee){
returnm.higherKey(e);
}

//获取第一个元素，并将该元素从TreeMap中删除。
publicEpollFirst(){
Map.Entrye=m.pollFirstEntry();
return(e==null)?null:e.getKey();
}

//获取最后一个元素，并将该元素从TreeMap中删除。
publicEpollLast(){
Map.Entrye=m.pollLastEntry();
return(e==null)?null:e.getKey();
}

//克隆一个TreeSet，并返回Object对象
publicObjectclone(){
TreeSetclone=null;
try{
clone=(TreeSet)super.clone();
}catch(CloneNotSupportedExceptione){
thrownewInternalError();
}

clone.m=newTreeMap(m);
returnclone;
}

//java.io.Serializable的写入函数
//将TreeSet的“比较器、容量，所有的元素值”都写入到输出流中
privatevoidwriteObject(java.io.ObjectOutputStreams)
throwsjava.io.IOException{
s.defaultWriteObject();

//写入比较器
s.writeObject(m.comparator());

//写入容量
s.writeInt(m.size());

//写入“TreeSet中的每一个元素”
for(Iteratori=m.keySet().iterator();i.hasNext();)
s.writeObject(i.next());
}

//java.io.Serializable的读取函数：根据写入方式读出
//先将TreeSet的“比较器、容量、所有的元素值”依次读出
privatevoidreadObject(java.io.ObjectInputStreams)
throwsjava.io.IOException,ClassNotFoundException{
//Readinanyhiddenstuff
s.defaultReadObject();

//从输入流中读取TreeSet的“比较器”
Comparatorc=(Comparator)s.readObject();

TreeMaptm;
if(c==null)
tm=newTreeMap();
else
tm=newTreeMap(c);
m=tm;

//从输入流中读取TreeSet的“容量”
intsize=s.readInt();

//从输入流中读取TreeSet的“全部元素”
tm.readTreeSet(size,s,PRESENT);
}

//TreeSet的序列版本号
privatestaticfinallongserialVersionUID=-2479143000061671589L;
}

总结：

(01)TreeSet实际上是TreeMap实现的。当我们构造TreeSet时；若使用不带参数的构造函数，则TreeSet的使用自然比较器；若用户需要使用自定义的比较器，则需要使用带比较器的参数。

(02)TreeSet是非线程安全的。

(03)TreeSet实现java.io.Serializable的方式。当写入到输出流时，依次写入“比较器、容量、全部元素”；当读出输入流时，再依次读取。

第4部分TreeSet遍历方式

4.1Iterator顺序遍历

for(Iteratoriter=set.iterator();iter.hasNext();){
iter.next();
}

4.2Iterator顺序遍历

//假设set是TreeSet对象
for(Iteratoriter=set.descendingIterator();iter.hasNext();){
iter.next();
}

4.3for-each遍历HashSet

//假设set是TreeSet对象，并且set中元素是String类型
String[]arr=(String[])set.toArray(newString[0]);
for(Stringstr:arr)
System.out.printf("foreach:%s\n",str);

TreeSet不支持快速随机遍历，只能通过迭代器进行遍历！

TreeSet遍历测试程序如下：

importjava.util.*;

/**
*@descTreeSet的遍历程序
*
*@authorskywang
*@emailkuiwu-wang@163.com
*/
publicclassTreeSetIteratorTest{

publicstaticvoidmain(String[]args){
TreeSetset=newTreeSet();
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
publicstaticvoidascIteratorThroughIterator(TreeSetset){
System.out.print("\n----AscendIterator----\n");
for(Iteratoriter=set.iterator();iter.hasNext();){
System.out.printf("asc:%s\n",iter.next());
}
}

//逆序遍历TreeSet
publicstaticvoiddescIteratorThroughIterator(TreeSetset){
System.out.printf("\n----DescendIterator----\n");
for(Iteratoriter=set.descendingIterator();iter.hasNext();)
System.out.printf("desc:%s\n",(String)iter.next());
}

//通过for-each遍历TreeSet。不推荐！此方法需要先将Set转换为数组
privatestaticvoidforeachTreeSet(TreeSetset){
System.out.printf("\n----For-each----\n");
String[]arr=(String[])set.toArray(newString[0]);
for(Stringstr:arr)
System.out.printf("foreach:%s\n",str);
}
}

运行结果：

----AscendIterator----
asc:aaa
asc:bbb
asc:ccc
asc:ddd
asc:eee
----DescendIterator----
desc:eee
desc:ddd
desc:ccc
desc:bbb
desc:aaa
----For-each----
foreach:aaa
foreach:bbb
foreach:ccc
foreach:ddd
foreach:eee

第5部分TreeSet示例

下面通过实例学习如何使用TreeSet

importjava.util.*;
/**
*@descTreeSet的API测试
*
*@authorskywang
*@emailkuiwu-wang@163.com
*/
publicclassTreeSetTest{
publicstaticvoidmain(String[]args){
testTreeSetAPIs();
}

//测试TreeSet的api
publicstaticvoidtestTreeSetAPIs(){
Stringval;
//新建TreeSet
TreeSettSet=newTreeSet();
//将元素添加到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("floorbbb:%s\n",tSet.floor("bbb"));
//lower(小于)
System.out.printf("lowerbbb:%s\n",tSet.lower("bbb"));
//ceiling(大于、等于)
System.out.printf("ceilingbbb:%s\n",tSet.ceiling("bbb"));
System.out.printf("ceilingeee:%s\n",tSet.ceiling("eee"));
//ceiling(大于)
System.out.printf("higherbbb:%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(newString[0]);
for(Stringstr:arr)
System.out.printf("foreach:%s\n",str);
//打印TreeSet
System.out.printf("TreeSet:%s\n",tSet);
//遍历TreeSet
for(Iteratoriter=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()?"setisempty":"setisnotempty");
}
}

运行结果：

TreeSet:[aaa,bbb,ccc,ddd,eee]
size:5
floorbbb:bbb
lowerbbb:aaa
ceilingbbb:bbb
ceilingeee:eee
higherbbb: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]
foreach:aaa
foreach:bbb
foreach:ddd
foreach: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]
setisempty

补充：Java中关于使用TreeSet存储数据的自然排序和定制排序

一、题目

创建类的5个对象，并把这些对象放入TreeSet集合中（TreeSet需使用泛型和不用泛型分别来定义）

分别按以下两种方式对集合中的元素进行排序，并遍历输出：

1、使Employee实现Comparable接口，并按name排序

2、创建TreeSet时传入Comparator对象，按生日日期的先后排序。

二、定义一个Employee类

/**
*该类包含：private成员变量name,age,birthday，其中birthday为
*MyDate类的对象；
*并为每一个属性定义getter,setter方法；
*并重写toString方法输出name,age,birthday
*@author
*@create2021-01-22-15:00
*/
publicclassEmployeeimplementsComparable{
privateStringname;
privateintage;
privateMyDatebirthday;
publicEmployee(){
}
publicEmployee(Stringname,intage,MyDatebirthday){
this.name=name;
this.age=age;
this.birthday=birthday;
}
publicStringgetName(){
returnname;
}
publicvoidsetName(Stringname){
this.name=name;
}
publicintgetAge(){
returnage;
}
publicvoidsetAge(intage){
this.age=age;
}
publicMyDategetBirthday(){
returnbirthday;
}
publicvoidsetBirthday(MyDatebirthday){
this.birthday=birthday;
}
@Override
publicStringtoString(){
return"Employee{"+
"name='"+name+'\''+
",age="+age+
",birthday="+birthday+
'}';
}
//不用泛型
//@Override
//publicintcompareTo(Objecto){
//if(oinstanceofEmployee){
//Employeeemployee=(Employee)o;
//returnthis.name.compareTo(employee.name);
//}
//thrownewRuntimeException("输入的数据类型不一致");
//}
//使用泛型
@Override
publicintcompareTo(Employeeo){
returnthis.name.compareTo(o.name);
}
}

三、MyDate类

/**
*MyDate类包含:
*private成员变量year,month,day；并为每一个属性定义getter,setter
*方法；
*@author
*@create2021-01-22-15:00
*/
publicclassMyDateimplementsComparable{
privateintyear;
privateintmonth;
privateintday;
publicMyDate(){
}
publicMyDate(intyear,intmonth,intday){
this.year=year;
this.month=month;
this.day=day;
}
@Override
publicStringtoString(){
return"MyDate{"+
"year="+year+
",month="+month+
",day="+day+
'}';
}
publicintgetYear(){
returnyear;
}
publicvoidsetYear(intyear){
this.year=year;
}
publicintgetMonth(){
returnmonth;
}
publicvoidsetMonth(intmonth){
this.month=month;
}
publicintgetDay(){
returnday;
}
publicvoidsetDay(intday){
this.day=day;
}
@Override
publicintcompareTo(MyDateo){
intminusYear=this.year-o.year;
if(minusYear!=0){
returnminusYear;
}
intminusMonth=this.month-o.month;
if(minusMonth!=0){
returnminusMonth;
}
returnthis.day-o.day;
}
}

四、单元测试

（一）

@Test
publicvoidtest1(){
TreeSetset=newTreeSet<>();
set.add(newEmployee("hh",23,newMyDate(1992,4,12)));
set.add(newEmployee("ff",43,newMyDate(1956,5,4)));
set.add(newEmployee("aa",27,newMyDate(1936,8,6)));
set.add(newEmployee("gg",38,newMyDate(1992,4,4)));
Iteratoriterator=set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}

结果如下：

（二）

@Test
publicvoidtest2(){
TreeSetset=newTreeSet<>(newComparator(){
@Override
publicintcompare(Employeee1,Employeee2){
//加上泛型
MyDateb1=e1.getBirthday();
MyDateb2=e2.getBirthday();
returnb1.compareTo(b2);
//不加泛型
//if(o1instanceofEmployee&&o2instanceofEmployee){
//Employeem1=(Employee)o1;
//Employeem2=(Employee)o2;
//MyDatem1Birthday=m1.getBirthday();
//MyDatem2Birthday=m2.getBirthday();
//
//intminusYear=m1Birthday.getYear()-m2Birthday.getYear();
//if(minusYear!=0){
//returnminusYear;
//}
//intminusMonth=m1Birthday.getMonth()-m2Birthday.getMonth();
//if(minusMonth!=0){
//returnminusMonth;
//}
//intminusDay=m1Birthday.getDay()-m2Birthday.getDay();
//returnminusDay;
//
//}
//thrownewRuntimeException("传入的数据类型不一致");
}
});
set.add(newEmployee("hh",23,newMyDate(1944,12,4)));
set.add(newEmployee("ff",43,newMyDate(1957,5,4)));
set.add(newEmployee("aa",27,newMyDate(1906,12,6)));
set.add(newEmployee("gg",38,newMyDate(1906,4,4)));
Iteratoriterator=set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}