Java集合学习（十七） TreeSet详细介绍（源码解析）和使用示例

Java集合学习（十七） TreeSet详细介绍（源码解析）和使用示例2014-08-03 cnblogs skywang12345这一章，我们对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的继承关系

java.lang.Objectjava.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关系如下图：

TreeSet的构造函数

// 默认构造函数。使用该构造函数，TreeSet中的元素按照自然排序进行排列。TreeSet（） // 创建的TreeSet包含collectionTreeSet（Collection<？ extends E> collection） // 指定TreeSet的比较器TreeSet（Comparator<？ super E> comparator） // 创建的TreeSet包含setTreeSet（SortedSet<E> set）

TreeSet的API

boolean add（E object）boolean addAll（Collection<？ extends E> collection）voidclear（）Objectclone（）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的原理，下面对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（）; // 不带参数的构造函数。创建一个空的TreeMappublic 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中的对象opublic boolean remove（Object o） {return m.remove（o）==PRESENT;} // 清空TreeSetpublic void clear（） {m.clear（）;} // 将集合c中的全部元素添加到TreeSet中publicboolean addAll（Collection<？ extends E> c） {// Use linear-time version if applicableif （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 stuffs.defaultReadObject（）; // 从输入流中读取TreeSet的“比较器”Comparator<？ super E> c = （Comparator<？ super E>） s.readObject（）; TreeMap<E,Object> tm;if （c==null）tm = new TreeMap<E,Object>（）;elsetm = 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;}

总结：