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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

# java  # TreeSet  # Java集合TreeSet用法详解  # Java TreeSet 添加失败的解决  # Java TreeSet类的简单理解和使用  # java中treemap和treeset实现红黑树  # Java TreeSet实现学生按年龄大小和姓名排序的方法示例  # 详解Java中HashSet和TreeSet的区别  # java 中HashMap、HashSet、TreeMap、TreeSet判断元素相同的几种方法比较  # 浅谈java中的TreeMap 排序与TreeSet 排序  # Java基础必学TreeSet集合  # 遍历  # 迭代  # 第一个  # 实现了  # 是一个  # 不包括  # 转换为  # 先将  # 它是  # 并将  # 不带  # 将该  # 上时  # 清空  # 为空  # 数据结构  # 只会  # 不存在  # 自定义  # 不支持 

相关文章： 定制建站策划方案_专业建站与网站建设方案一站式指南  网站制作公司排行榜,四大门户网站排名？  高防网站服务器：DDoS防御与BGP线路的AI智能防护方案  青岛网站设计制作公司,查询青岛招聘信息的网站有哪些？  怎么将XML数据可视化 D3.js加载XML  在线制作视频网站免费,都有哪些好的动漫网站？  杭州银行网站设计制作流程,杭州银行怎么开通认证方式？  如何设计高效校园网站？  如何正确选择百度移动适配建站域名？  如何在万网自助建站中设置域名及备案？  如何快速登录WAP自助建站平台？  小型网站建站如何选择虚拟主机？  如何在宝塔面板创建新站点？  如何撰写建站申请书？关键要点有哪些？  大连网站制作费用,大连新青年网站，五年四班里的视频怎样下载啊？  如何用景安虚拟主机手机版绑定域名建站？  免费网站制作模板下载,除了易企秀之外还有什么H5平台可以制作H5长页面，最好是免费的？  建站与域名管理如何高效结合？  如何在万网开始建站？分步指南解析  一键制作网站软件下载安装,一键自动采集网页文档制作步骤？  高配服务器限时抢购：企业级配置与回收服务一站式优惠方案  动图在线制作网站有哪些,滑动动图图集怎么做？  如何解决ASP生成WAP建站中文乱码问题？  网站视频怎么制作,哪个网站可以免费收看好莱坞经典大片？  详解jQuery停止动画——stop()方法的使用  如何通过免费商城建站系统源码自定义网站主题与功能？  如何在西部数码注册域名并快速搭建网站？  制作营销网站公司,淘特是干什么用的？  平台云上自助建站如何快速打造专业网站？  北京网页设计制作网站有哪些,继续教育自动播放怎么设置？  ,南京靠谱的征婚网站？  香港服务器WordPress建站指南：SEO优化与高效部署策略  专业企业网站设计制作公司,如何理解商贸企业的统一配送和分销网络建设？  建站之星后台密码遗忘或太弱？如何重置与强化？  建站之星24小时客服电话如何获取？  网站制作怎么样才能赚钱,用自己的电脑做服务器架设网站有什么利弊，能赚钱吗？  建站主机是否等同于虚拟主机？  七夕网站制作视频,七夕大促活动怎么报名？  最好的网站制作公司,网购哪个网站口碑最好，推荐几个？谢谢？  如何快速搭建高效可靠的建站解决方案？  如何在自有机房高效搭建专业网站？  如何在建站宝盒中设置产品搜索功能？  网站广告牌制作方法,街上的广告牌，横幅，用PS还是其他软件做的？  长春网站建设制作公司,长春的网络公司怎么样主要是能做网站的？  建站之星安装需要哪些步骤及注意事项？  如何在橙子建站中快速调整背景颜色？  如何用PHP快速搭建CMS系统？  阿里云网站搭建费用解析：服务器价格与建站成本优化指南  如何快速查询网站的真实建站时间？  制作网站的基本流程,设计网站的软件是什么？