java - Hashset vs Treeset - Stack Overflow
to customize your list.
Join the Stack Overflow Community
Stack Overflow is a community of 6.4 million programmers, just like you, helping each other.
J it only takes a minute:
I've always loved trees, that nice O(n*lg(n)) and the tidiness of them. However, every software engineer I've ever known has asked me pointedly why I would use a TreeSet. From a CS background, I don't think it matters all that much which you use, and I don't care to mess around with hash functions and buckets (in the case of Java).
In which cases should I use a HashSet over a TreeSet?
2,55641420
HashSet is much faster than TreeSet (constant-time versus log-time for most operations like add, remove and contains) but offers no ordering guarantees like TreeSet.
class offers constant time performance for the basic operations (add, remove, contains and size).
it does not guarantee that the order of elements will remain constant over time
iteration performance depends on the initial capacity and the load factor of the HashSet.
It's quite safe to accept default load factor but you may want to specify an initial capacity that's about twice the size to which you expect the set to grow.
guarantees log(n) time cost for the basic operations (add, remove and contains)
guarantees that elements of set will be sorted (ascending, natural, or the one specified by you via its constructor) (implements )
doesn't offer any tuning parameters for iteration performance
offers a few handy methods to deal with the ordered set like , last(), , and
Important points:
Both guarantee duplicate-free collection of elements
It is generally faster to add elements to the HashSet and then convert the collection to a TreeSet for a duplicate-free sorted traversal.
None of these implementation are synchronized. That is if multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.
LinkedHashSet is in some sense intermediate between HashSet and TreeSet. Implemented as a hash table with a linked list running through it, however it provides insertion-ordered iteration which is not same as sorted traversal guaranteed by TreeSet.
So choice of usage depends entirely on your needs but I feel that even if you need an ordered collection then you should still prefer HashSet to create the Set and then convert it into TreeSet.
e.g. SortedSet&String& s = new TreeSet&String&(hashSet);
41.9k8134193
14.4k22423
One advantage not yet mentioned of a TreeSet is that its has greater "locality", which is shorthand for saying (1) if two entries are nearby in the order, a TreeSet places them near each other in the data structure, and (2) this placement takes advantage of the principle of locality, which says that similar data is often accessed by an application with similar frequency.
This is in contrast to a HashSet, which spreads the entries all over memory, no matter what their keys are.
When the latency cost of reading from a hard drive is thousands of times the cost of reading from cache or RAM, and when the data really is accessed with locality, the TreeSet can be a much better choice.
3,47572460
HashSet is O(1) to access elements, so it certainly does matter. But maintaining order of the objects in the set isn't possible.
TreeSet is useful if maintaining an order(In terms of values and not the insertion order) matters to you.
But, as you've noted, you're trading order for slower time to access an element: O(log n) for basic operations.
From the :
This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
235k23272453
1.HashSet allows null object.
2.TreeSet will not allow null object. If you try to add null value it will throw a NullPointerException.
3.HashSet is much faster than TreeSet.
TreeSet&String& ts = new TreeSet&String&();
ts.add(null); // throws NullPointerException
HashSet&String& hs = new HashSet&String&();
hs.add(null); // runs fine
The reason why most use HashSet is that the operations are (on average) O(1) instead of O(log n).
If the set contains standard items you will not be "messing around with hash functions" as that has been done for you.
If the set contains custom classes, you have to implement hashCode to use HashSet (although Effective Java shows how), but if you use a TreeSet you have to make it Comparable or supply a Comparator. This can be a problem if the class does not have a particular order.
I have sometimes used TreeSet (or actually TreeMap) for very small sets/maps (& 10 items) although I have not checked to see if there is any real gain in doing so.
For large sets the difference can be considerable.
Now if you need the sorted, then TreeSet is appropriate, although even then if updates are frequent and the need for a sorted result is infrequent, sometimes copying the contents to a list or an array and sorting them can be faster.
15.2k22435
If you aren't inserting enough elements to result in frequent rehashings (or collisions, if your HashSet can't resize), a HashSet certainly gives you the benefit of constant time access. But on sets with lots of growth or shrinkage, you may actually get better performance with Treesets, depending on the implementation.
Amortized time can be close to O(1) with a functional red-black tree, if memory serves me. Okasaki's book would have a better explanation than I can pull off. (Or see )
15.9k32553
HashSet implementations are, of course, much much faster -- less overhead because there's no ordering. A good analysis of the various Set implementations in Java is provided at .
The discussion there also points out an interesting 'middle ground' approach to the Tree vs Hash question. Java provides a LinkedHashSet, which is a HashSet with an "insertion-oriented" linked list running through it, that is, the last element in the linked list is also the most recently inserted into the Hash. This allows you to avoid the unruliness of an unordered hash without incurring the increased cost of a TreeSet.
3,71722663
The TreeSet is one of two sorted collections (the other being
TreeMap). It uses a Red-Black tree structure (but you knew that), and guarantees
that the elements will be in ascending order, according to natural order. Optionally,
you can construct a TreeSet with a constructor that lets you give the collection your
own rules for what the order should be (rather than relying on the ordering defined
by the elements' class) by using a Comparable or Comparator
and A LinkedHashSet is an ordered version of HashSet that
maintains a doubly-linked List across all elements. Use this class instead of HashSet
when you care about the iteration order. When you iterate through a HashSet the
order is unpredictable, while a LinkedHashSet lets you iterate through the elements
in the order in which they were inserted
A lot of answers have been given, based on technical considerations, especially around performance.
According to me, choice between TreeSet and HashSet matters.
But I would rather say the choice should be driven by conceptual considerations first.
If, for the objects your need to manipulate, a natural ordering does not make sense, then do not use TreeSet.
It is a sorted set, since it implements SortedSet. So it means you need to override function compareTo, which should be consistent with what returns function equals. For example if you have a set of objects of a class called Student, then I do not think a TreeSet would make sense, since there is no natural ordering between students. You can order them by their average grade, okay, but this is not a "natural ordering". Function compareTo would return 0 not only when two objects represent the same student, but also when two different students have the same grade. For the second case, equals would return false (unless you decide to make the latter return true when two different students have the same grade, which would make equals function have a misleading meaning, not to say a wrong meaning.)
Please note this consistency between equals and compareTo is optional, but strongly recommended. Otherwise the contract of interface Set is broken, making your code misleading to other people, thus also possibly leading to unexpected behavior.
might be a good source of information regarding this question.
Message Edit ( complete rewrite ) When order does not matter, that's when. Both should give Log(n) - it would be of utility to see if either is over five percent faster than the other. HashSet can give O(1) testing in a loop should reveal whether it is.
import java.util.HashS
import java.util.S
import java.util.TreeS
public class HashTreeSetCompare {
//It is generally faster to add elements to the HashSet and then
//convert the collection to a TreeSet for a duplicate-free sorted
//Traversal.
O(Hash + tree set) & O(tree set) ??
Really???? Why?
public static void main(String args[]) {
int size = 80000;
useHashThenTreeSet(size);
useTreeSetOnly(size);
private static void useTreeSetOnly(int size) {
System.out.println("useTreeSetOnly: ");
long start = System.currentTimeMillis();
Set&String& sortedSet = new TreeSet&String&();
for (int i = 0; i & i++) {
sortedSet.add(i + "");
//System.out.println(sortedSet);
long end = System.currentTimeMillis();
System.out.println("useTreeSetOnly: " + (end - start));
private static void useHashThenTreeSet(int size) {
System.out.println("useHashThenTreeSet: ");
long start = System.currentTimeMillis();
Set&String& set = new HashSet&String&();
for (int i = 0; i & i++) {
set.add(i + "");
Set&String& sortedSet = new TreeSet&String&(set);
//System.out.println(sortedSet);
long end = System.currentTimeMillis();
System.out.println("useHashThenTreeSet: " + (end - start));
Your Answer
Sign up or
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Post as a guest
By posting your answer, you agree to the
Not the answer you're looking for?
Browse other questions tagged
Stack Overflow works best with JavaScript enabled&&国之画&&&& &&&&&&
&& &&&&&&&&&&&&&&&&&&&&
鲁ICP备号-4
打开技术之扣，分享程序人生！Test10 声明类Student，包含3个成员变量：name、age、score，创建5个对象装入TreeSe 照成 Data structs 数据结构 238万源代码下载-
&文件名称: Test10
& & & & &&]
&&所属分类:
&&开发工具: Java
&&文件大小: 1 KB
&&上传时间:
&&下载次数: 4
&&提 供 者:
&详细说明：声明类Student，包含3个成员变量：name、age、score，创建5个对象装入TreeSet，按照成绩排序输出结果（考虑成绩相同的问题）。-Declaring class Student, contains three member variables: name, age, score, create five objects into the TreeSet, sorted according to the results output (considering the same performance problems).
文件列表(点击判断是否您需要的文件，如果是垃圾请在下面评价投诉):
&&Test10.java
&输入关键字，在本站238万海量源码库中尽情搜索：Java 容器 & 泛型（3):：HashSet、TreeSet 和 LinkedHashSet比较 - ImportNew
| 标签： ,
一、Set回顾
一个不包括重复元素（包括可变对象）的Collection，是一种无序的集合。Set不包含满 a.equals(b) 的元素对a和b，并且最多有一个null。
泥瓦匠的记忆宫殿：
1、不允许包含相同元素
2、判断对象是否相同，根据equals方法
二、HashSet
一个按着Hash算法来存储集合中的元素，其元素值可以是NULL。它不能保证元素的排列顺序。同样，HashSet是不同步的，如果需要多线程访问它的话，可以用 Collections.synchronizedSet 方法来包装它：
Set s = Collections.synchronizedSet(new HashSet(...));
同上一节一样，用迭代器的时候，也要注意 并发修改异常ConcurrentModificationException。
要注意的地方是，HashSet集合判断两个元素相等不单单是equals方法，并且必须hashCode()方法返回值也要相等。看下面的例子：
import java.util.HashS
class EuqalsObj
public boolean equals(Object obj)
class HashCodeObj
public int hashCode()
class HashSetObj
public int hashCode()
public boolean equals(Object obj)
public class HashSetTest
public static void main(String[] args)
HashSet objs = new HashSet();
objs.add(new EuqalsObj());
objs.add(new EuqalsObj());
objs.add(new HashCodeObj());
objs.add(new HashCodeObj());
objs.add(new HashSetObj());
objs.add(new HashSetObj());
System.out.println(&HashSet Elements:&);
System.out.print(&\t& + objs + &\n&);
Run 一下，控制台如下输出：
HashSet Elements:
[HashCodeObj@1, HashCodeObj@1, HashSetObj@2, EuqalsObj@1471cb25, EuqalsObj@3acff49f]
泥瓦匠根据结果，一一到来。首先，排列顺序不定。
HashSetObj 类满足我们刚刚的要求，所以集合中只有一个且它的HashCode值为2。
HashCodeObj 类虽然它们HashCode值为1，但是他们不相等。（其实当HashCode值一样，这个存储位置会采用链式结构保存两个HashCodeObj对象。）
同样,EqualsObj 类他们相等，但是他们HashCode值不等，分别为acff49f。
因此，用HashSet添加可变对象，要注意当对象有可能修改后和其他对象矛盾，这样我们无法从HashSet找到准确我们需要的对象。
三、LinkedHashList
HashSet的子类，也同样有HashCode值来决定元素位置。但是它使用链表维护元素的次序。记住两个字：有序。
有序的妙用，复制。比如泥瓦匠实现一个HashSet无序添加，然后复制一个一样次序的HashSet来。代码如下：
package com.sedion.bysocket.
import java.util.HashS
import java.util.LinkedHashS
import java.util.S
public class LinkedHashListTest
public static void main(String[] args)
/* 复制HashSet */
Set h1 = new HashSet&String&();
h1.add(&List&);
h1.add(&Queue&);
h1.add(&Set&);
h1.add(&Map&);
System.out.println(&HashSet Elements:&);
System.out.print(&\t& + h1 + &\n&);
Set h2 = copy(h1);
System.out.println(&HashSet Elements After Copy:&);
System.out.print(&\t& + h2 + &\n&);
@SuppressWarnings({ &rawtypes&, &unchecked& })
public static Set copy(Set set)
Set setCopy = new LinkedHashSet(set);
return setC
Run 一下，控制台输出：
HashSet Elements:
[Map, Queue, Set, List]
HashSet Elements After Copy:
[Map, Queue, Set, List]
可见，每个数据结构都有它存在的理由。
四、TreeSet
TreeSet使用树结构实现（红黑树），集合中的元素进行排序，但是添加、删除和包含的算法复杂度为O（log（n））。
举个例子吧，首先我们定义一个Bird类。（鸟是泥瓦匠最喜欢的动物）
class Bird
public Bird(int s)
public String toString()
return size + &&;
然后用TreeSet添加Bird类。
public class TreeSetTest
public static void main(String[] args)
TreeSet&Bird& bSet = new TreeSet&Bird&();
bSet.add(new Bird(1));
bSet.add(new Bird(3));
bSet.add(new Bird(2));
Iterator&Bird& iter = bSet.iterator();
while (iter.hasNext())
Bird bird = (Bird) iter.next();
System.out.println(bird);
Run一下,控制台输出如下：
Exception in thread &main& java.lang.ClassCastException: Bird cannot be cast to parable
at java.pare(Unknown Source)
at java.util.TreeMap.put(Unknown Source)
at java.util.TreeSet.add(Unknown Source)
at com.sedion.bysocket.collection.TreeSetTest.main(TreeSetTest.java:29)
答案很明显，TreeSet是排序的。所以Bird需要实现Comparable此接口。
parable此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序，类的 compareTo 方法被称为它的自然比较方法。
修改Bird如下：
class Bird implements Comparable&Bird&
public Bird(int s)
public String toString()
return size + &号鸟&;
public int compareTo(Bird o)
return size - o.
再次Run一下：
五、性能测试比较
针对上面三种Set集合，我们对它们的Add方法进行性能测试：
import java.util.HashS
import java.util.LinkedHashS
import java.util.R
import java.util.TreeS
class Bird implements Comparable&Bird&
public Bird(int s)
public String toString()
return size + &号鸟&;
public int compareTo(Bird o)
return size - o.
public class Set
public static void main(String[] args)
Random r = new Random();
HashSet&Bird& hashSet = new HashSet&Bird&();
TreeSet&Bird& treeSet = new TreeSet&Bird&();
LinkedHashSet&Bird& linkedSet = new LinkedHashSet&Bird&();
// start time
long startTime = System.nanoTime();
for (int i = 0; i & 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
hashSet.add(new Bird(x));
// end time
long endTime = System.nanoTime();
long duration = endTime - startT
System.out.println(&HashSet: & + duration);
// start time
startTime = System.nanoTime();
for (int i = 0; i & 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
treeSet.add(new Bird(x));
// end time
endTime = System.nanoTime();
duration = endTime - startT
System.out.println(&TreeSet: & + duration);
// start time
startTime = System.nanoTime();
for (int i = 0; i & 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
linkedSet.add(new Bird(x));
// end time
endTime = System.nanoTime();
duration = endTime - startT
System.out.println(&LinkedHashSet: & + duration);
Run一下，可以在控制台中看出：
HashSet: 2610998
TreeSet: 3195378
LinkedHashSet: 2673782
可见，TreeSet因为需要进行比较，所以性能比较差。
HashSet：equlas hashcode
LinkedHashSet：链式结构
TreeSet：比较，Comparable接口，性能较差
盲目改为fastjson。fastjson在序列化过程中，实测比jackson有30%的差距。反序列...
关于ImportNew
ImportNew 专注于 Java 技术分享。于日 11:11正式上线。是的，这是一个很特别的时刻 :)
ImportNew 由两个 Java 关键字 import 和 new 组成，意指：Java 开发者学习新知识的网站。 import 可认为是学习和吸收， new 则可认为是新知识、新技术圈子和新朋友……
新浪微博：
推荐微信号
反馈建议：@
广告与商务合作QQ：
– 好的话题、有启发的回复、值得信赖的圈子
– 写了文章？看干货？去头条！
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 活跃 & 专业的翻译小组
– 国内外的精选博客文章
– UI,网页，交互和用户体验
– JavaScript, HTML5, CSS
– 专注Android技术分享
– 专注iOS技术分享
– 专注Java技术分享
– 专注Python技术分享
& 2016 ImportNewJava 集合系列17之 TreeSet详细介绍(源码解析)和使用示例 - 如果天空不死 - 博客园
随笔 - 278
评论 - 705
这一章，我们对TreeSet进行学习。我们先对TreeSet有个整体认识，然后再学习它的源码，最后再通过实例来学会使用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包含collection
TreeSet(Collection&? extends E& collection)
// 指定TreeSet的比较器
TreeSet(Comparator&? super E& comparator)
// 创建的TreeSet包含set
TreeSet(SortedSet&E& set)
TreeSet的API
add(E object)
addAll(Collection&? extends E& collection)
contains(Object object)
pollFirst()
pollLast()
lower(E e)
floor(E e)
ceiling(E e)
higher(E e)
remove(Object object)
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的本质是一个"有序的，并且没有重复元素"的集合，它是通过实现的。TreeSet中含有一个"NavigableMap类型的成员变量"m，而m实际上是"TreeMap的实例"。
第3部分 TreeSet源码解析(基于JDK1.6.0_45)
为了更了解TreeSet的原理，下面对TreeSet源码代码作出分析。
1 package java.
3 public class TreeSet&E& extends AbstractSet&E&
implements NavigableSet&E&, Cloneable, java.io.Serializable
// NavigableMap对象
private transient NavigableMap&E,Object&
// 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) {
// 带比较器的构造函数。
public TreeSet(Comparator&? super E& comparator) {
this(new TreeMap&E,Object&(comparator));
// 创建TreeSet，并将集合c中的全部元素都添加到TreeSet中
public TreeSet(Collection&? extends E& c) {
// 将集合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中
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&)
TreeMap&E,Object& map = (TreeMap&E, Object&)
Comparator&? super E& cc = (Comparator&? super E&) parator();
Comparator&? super E& mc = parator();
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;
clone = (TreeSet&E&) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
clone.m = new TreeMap&E,Object&(m);
// java.io.Serializable的写入函数
// 将TreeSet的&比较器、容量，所有的元素值&都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
s.defaultWriteObject();
// 写入比较器
s.parator());
// 写入容量
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&
if (c==null)
tm = new TreeMap&E,Object&();
tm = new TreeMap&E,Object&(c);
// 从输入流中读取TreeSet的&容量&
int size = s.readInt();
// 从输入流中读取TreeSet的&全部元素&
tm.readTreeSet(size, s, PRESENT);
// TreeSet的序列版本号
private static final long serialVersionUID = -1671589L;
(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遍历测试程序如下：
1 import java.util.*;
* @desc TreeSet的遍历程序
* @author skywang
* @email kuiwu-
9 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 ----
---- 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
1 import java.util.*;
* @desc TreeSet的API测试
* @author skywang
* @email kuiwu-
9 public class TreeSetTest {
public static void main(String[] args) {
testTreeSetAPIs();
// 测试TreeSet的api
public static void testTreeSetAPIs() {
// 新建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]
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
阅读(...) 评论()}