Java之 TreeSet的详细使用说明

第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

补充：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
 * @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 类

/**
 * 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;
 }
}

四、单元测试

（一）

@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());
  }
 }

结果如下：

（二）

 @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());
  }
 }