TreeSet与HashSet类似,不过TreeSet是一个有序集合(sorted collection),在对集合进行遍历时,每个值将自动的按照TreeSet内部排序的顺序呈现。当前TreeSet实现使用的是红黑树(red-black tree,详细介绍可以参照《算法导论》一书),每次将一个元素添加到树中时,都被放置在正确的排序位置上,因此,迭代器总是以排好序的顺序访问每个元素。
将一个元素添加到树中比添加到散列表中慢,但是比添加到数组或者链表中正确位置上要快很多。例如如果树中包含n个元素,查找新元素的正确位置平均需要log2n次比较,也就是如果树中包含1000个元素,添加一个新元素大约需要比较10次即可。
对象的比较
TreeSet如何知道元素怎么排列呢?树集假定插入的元素实现了Comparable接口,这个接口有一个定义的方法:
public interface Comparable<T> { int compareTo(T other); }
有些标准的Java平台类实现类Comparable接口,例如String类,这个类的compareTo方法依据字典序(有时称为词典序)对字符串进行比较。如果要插入自定义的对象,就必须通过实现Comparable接口自定义排列顺序。在Object类中,没有提供compareTo接口的默认实现。
例如下面的代码展示了如何用部件编号对Item对象进行排序:
class Item implements Compareble<Item> { public int compareTo(Item other) { return partNumber - other.partNumber; //需要确保结果不会溢出 } ...... }
对于一个给定的类,只能实现这个接口一次,如果在一个集合中需要按照部件编号进行排序,在另一个集合中却要按照描述信息进行排序,该怎么办呢?另外,如果需要对一个类的对象进行排序,而这个类的创建者有没有实现Comparable接口,又该怎么办呢?以上两种情况下,可以通过将Comparator对象传递给TreeSet构造器来告诉树集使用不同的比较方法,Comparator接口声明了一个带有两个显式参数的compare方法。
public interface Comparator<T> { int compare(T a,T b); }
如果按照描述信息进行排序,就直接定义一个实现Comparator接口的类:
class ItemComparator implements Comparator<Item> { public int compare(Item a, Item b) { String descrA = a.getDescription(); String descrB = b.getDescription(); return descrA.compareTo(descrB); } }
然后将这个类的对象传递给树集的构造器:
ItemComparator comp = new ItemComparator(); SortedSet<Item> sortByDescription = new TreeSet<Item>(comp);
如果构造了一棵带有比较器的树,就可以在需要比较两个元素时使用这个对象。
注意,这个比较器没有任何数据,它只是比较方法的持有器。有时将这种对象称为函数对象(function object)。函数对象通常被定义为“瞬时的”,即匿名内部类的实例:
SortedSet<Item> sortByDescription = new TreeSet<Item>(new Comparator<Item>() { public int compare(Item a, Item b) { String descrA = a.getDescription(); String descrB = b.getDescription(); return descrA.compareTo(descrB); } });
注:从Java SE6开始,TreeSet类实现了NavigableSet接口,这个接口增加了几个便于定位元素以及反向遍历的方法,具体可参见API注释。
下面例子中创建了两个Item对象的树集,第一个按照编号排序,是对象的默认顺序,第二个通过使用一个定制的比较器来按照描述信息排序。代码如下:
package com.chensl.collection; import java.util.*; /** This program sorts a set of item by comparing their descriptions. */ public class TreeSetTest { public static void main(String[] args) { SortedSet<Item> parts = new TreeSet<Item>(); parts.add(new Item("Toaster", 1234)); parts.add(new Item("Widget", 4562)); parts.add(new Item("Modem", 9912)); System.out.println(parts); SortedSet<Item> sortByDescription = new TreeSet<Item>(new Comparator<Item>() { public int compare(Item a, Item b) { String descrA = a.getDescription(); String descrB = b.getDescription(); return descrA.compareTo(descrB); } }); sortByDescription.addAll(parts); System.out.println(sortByDescription); } } /** An item with a description and a part number. */ class Item implements Comparable<Item> { /** Constructs an item. @param aDescription the item's description @param aPartNumber the item's part number */ public Item(String aDescription, int aPartNumber) { description = aDescription; partNumber = aPartNumber; } /** Gets the description of this item. @return the description */ public String getDescription() { return description; } public String toString() { return "[descripion=" + description + ", partNumber=" + partNumber + "]"; } public boolean equals(Object otherObject) { if (this == otherObject) return true; if (otherObject == null) return false; if (getClass() != otherObject.getClass()) return false; Item other = (Item) otherObject; return description.equals(other.description) && partNumber == other.partNumber; } public int hashCode() { return 13 * description.hashCode() + 17 * partNumber; } public int compareTo(Item other) { return partNumber - other.partNumber; } private String description; private int partNumber; }
发表评论
-
Java添加UTF-7字符集支持(转)
2014-08-16 16:20 815这段时间在做PushServer时,需要对编码过的邮件标题及 ... -
问题记录
2012-05-02 20:58 451. 如何使java打印byte类型数据? 如: / ... -
利用java反射机制实现IoC容器
2011-07-05 17:44 0P717 -- P719 -
网址资源保存
2011-05-18 18:20 90xwork 下载地址: http://release.ope ... -
JAVA工具类(暂保存草稿,如果发表的话需要分别修改验证工具类内容)
2010-09-15 00:02 0(暂保存草稿,如果发表的话需要分别修改验证工具类内容) ... -
Collection之映射表(Maps)
2010-09-07 11:08 1323映射表(map)用来存放键/值对,如果提供了键,就能够找到值, ... -
Collection之双端队列与优先级队列(Priority queue)
2010-09-06 10:28 1939双端队列 在Java SE6中,引入了Deque接口,并由A ... -
Collection之散列表(hash table)
2010-09-04 22:10 871链表和数组中元素是按一定次序进行排列的,散列表不在意元素的顺序 ... -
Collection之数组列表
2010-09-02 17:52 846数组列表(ArrayList)和上文中介绍的链表(Li ... -
Collection之链表
2010-09-02 11:00 870在Java语言中,所有的链表都是双向链接的(doubly li ... -
Concrete Collection集合概要
2010-09-02 00:22 749Java类库中的具体的集合: ArrayList 一种可以 ... -
泛型代码与虚拟机
2010-08-31 22:27 825虚拟机没有泛型对象,所有对象都属于普通类,使用当前Sun的编译 ... -
JAVA集合接口
2010-08-31 16:49 1246集合接口,JAVA集合类库 ... -
JAVA静态成员和静态内部类
2010-08-29 10:45 2146静态类(static class)即定义了静态方法,静 ... -
Java数据结构和算法--树(转)
2010-08-25 18:16 700(1)二叉树 class Tree { cl ...
相关推荐
文档摘录 文档摘录文档摘录文档摘录文档摘录文档摘录文档摘录
介绍TreeSet集合用法,向TreeSet集合中添加类的对象,此类需实现Comparable接口,有实例,供需要的朋友下载学习。
NULL 博文链接:https://elvin-chu.iteye.com/blog/1942033
毕向东Java基础视频教程-集合框架(TreeSet练习).
HashSet和TreeSet_围墙之外.rar
TreeSet 是 Java 中的一个集合类,它实现了 SortedSet 接口,并且使用红黑树作为底层数据结构。TreeSet 具有以下主要特点: 排序性:TreeSet 中的元素是有序的,默认按照元素的自然顺序进行排序。或者,可以在创建 ...
使用TreeSet和Comparator,编写TreeSetTest2类,要求对TreeSet中的元素1-元素10进行排列,排序逻辑为奇数在前偶数在后,奇数按照升序排列,偶数按照降序排列。 如果需要的话可以下载,有写成文章的。有写了一点中文...
treemap treeset hashset hashmap 简要介绍
用JAVA集合TreeSet写的求并集算法
Java数据结构--13.Java8数据结构TreeSet 前⾔ ,上⼀篇中对 Set 接⼝最终实现类 HashSet 与 LinkedHashSet 做了介绍与分析,本篇将对另⼀种 Set 接⼝的最终实现类 TreeSet 进⾏ 介绍与分析。 先来看下 TreeSet 完整...
Java SE程序 TreeSet类中自定义CompareTo类Java SE程序 TreeSet类中自定义CompareTo类Java SE程序 TreeSet类中自定义CompareTo类Java SE程序 TreeSet类中自定义CompareTo类Java SE程序 TreeSet类中自定义CompareTo类...
public int compare(String o1,String o2) { return o1.length()-o2.length();... TreeSet ts = new TreeSet(com); ts.add("string"); ts.add("char"); ts.add("nothing�"); System.out.println(ts);
在TreeSet中添加自定义对象,能更好地帮助理解TreeSet
通过TreeSet类直接对学生成绩实现了排序功能,不必要进行相关额外的排序来实现!
主要为大家详细介绍了java中treemap和treeset实现红黑树,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
HashSet和TreeSet的区别
图书馆管理 1.描述一个图书馆 2.进书,借书卡办理 3.借书,还书 4.查询某书的借出记录 5.查询借书卡的借出记录 6.显示图书列表(按借出次数排序)
用TreeSet添加字符串,按照字符串首字母字母顺序和字符串长度顺序排序
JAVA集合框架之List、Map、Set之间的选择~小案例分析:http://blog.csdn.net/qq_23473123/article/details/51240739