欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java之 TreeSet的详细使用说明

程序员文章站 2022-06-27 20:23:19
第1部分 treeset介绍treeset简介treeset 是一个有序的集合,它的作用是提供有序的set集合。它继承于abstractset抽象类,实现了navigableset,...

第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关系如下图:

Java之 TreeSet的详细使用说明

从图中可以看出:

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

结果如下:

Java之 TreeSet的详细使用说明

(二)

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

结果如下:

Java之 TreeSet的详细使用说明

以上为个人经验,希望能给大家一个参考,也希望大家多多支持。如有错误或未考虑完全的地方,望不吝赐教。

相关标签: Java TreeSet