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包含collectionTreeSet(Collection
      collection)// 指定TreeSet的比较器TreeSet(Comparator
      comparator)// 创建的TreeSet包含setTreeSet(SortedSet
     
       set)
     

TreeSet的API

boolean                   add(E object)boolean                   addAll(Collection
      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
          comparator()Iterator
     
                     iterator()Iterator
      
                      descendingIterator()SortedSet
       
                      headSet(E end)NavigableSet
        
                    descendingSet()NavigableSet
         
                     headSet(E end, boolean endInclusive)SortedSet
          
            subSet(E start, E end)NavigableSet
           
             subSet(E start, boolean startInclusive, E end, boolean endInclusive)NavigableSet
            
              tailSet(E start, boolean startInclusive)SortedSet
             
               tailSet(E start)
             
            
           
          
         
        
       
      
     

说明：

(01) TreeSet是有序的Set集合，因此支持add、remove、get等方法。

(02) 和NavigableSet一样，TreeSet的导航方法大致可以区分为两类，一类时提供元素项的导航方法，返回某个元素；另一类时提供集合的导航方法，返回某个集合。

lower、floor、ceiling 和 higher 分别返回小于、小于等于、大于等于、大于给定元素的元素，如果不存在这样的元素，则返回 null。

TreeSet源码分析

　　对于TreeSet而言，它是基于TreeMap实现的，TreeSet底层使用TreeMap来保存所有元素，因此TreeSet的实现比较简单，相关TreeSet的操作，基本上都是直接调用底层TreeMap的相关方法来完成，

　　TreeSet的源代码如下：

 

/* * @(#)TreeSet.java	1.37 06/05/10 * * Copyright 2006 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */package java.util;/** * @param 
     
       the type of elements maintained by this set * * @author  Josh Bloch * @version 1.37, 05/10/06 * @see	    Collection * @see	    Set * @see	    HashSet * @see     Comparable * @see     Comparator * @see	    TreeMap * @since   1.2 */public class TreeSet
      
        extends AbstractSet
       
            implements NavigableSet
        
         , Cloneable, java.io.Serializable{    /**     * NavigableMap对象     */    private transient NavigableMap
         
           m;    // TreeSet是通过TreeMap实现的，    // PRESENT是键-值对中的值。    private static final Object PRESENT = new Object();    /**     * 将TreeMap赋值给 "NavigableMap对象m"     */    TreeSet(NavigableMap
          
            m) { this.m = m; } /** * 不带参数的构造函数。创建一个空的TreeMap */ public TreeSet() { this(new TreeMap
           
            ()); } /** * 带比较器的构造函数。 */ public TreeSet(Comparator
             comparator) { this(new TreeMap
            
             (comparator)); } /** * 创建TreeSet，并将集合c中的全部元素都添加到TreeSet中 */ public TreeSet(Collection
              c) { this(); addAll(c); } /** * 创建TreeSet，并将s中的全部元素都添加到TreeSet中 */ public TreeSet(SortedSet
             
               s) { this(s.comparator()); addAll(s); } /** * 返回TreeSet的顺序排列的迭代器。 * 因为TreeSet是TreeMap实现的，所以这里实际上时返回TreeMap的“键集”对应的迭代器 */ public Iterator
              
                iterator() { return m.navigableKeySet().iterator(); } /** * 返回TreeSet的逆序排列的迭代器。 * 因为TreeSet是TreeMap实现的，所以这里实际上时返回TreeMap的“键集”对应的迭代器 */ public Iterator
               
                 descendingIterator() { return m.descendingKeySet().iterator(); } /** * 返回NavigableSet
                
                 类型的TreeSet */ public NavigableSet
                 
                   descendingSet() { return new TreeSet(m.descendingMap()); } /** * 返回大小 */ public int size() { return m.size(); } /** * 是否为空 */ public boolean isEmpty() { return m.isEmpty(); } /** * 是否包含o */ public boolean contains(Object o) { return m.containsKey(o); } /** * 添加元素e */ public boolean add(E e) { return m.put(e, PRESENT)==null; } /** * 删除元素o */ public boolean remove(Object o) { return m.remove(o)==PRESENT; } /** * 清空集合 */ public void clear() { m.clear(); } /** * 将集合c中的全部元素添加到TreeSet中 */ public boolean addAll(Collection
                   c) { // Use linear-time version if applicable if (m.size()==0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) { SortedSet
                   set = (SortedSet
                  ) c; TreeMap
                  
                    map = (TreeMap
                   
                    ) m; Comparator
                     cc = (Comparator
                    ) set.comparator(); Comparator
                     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
                    
                      subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new TreeSet
                     
                      (m.subMap(fromElement, fromInclusive, toElement, toInclusive)); } /** * 返回Set的头部，范围是：从头部到toElement。 * inclusive是是否包含toElement的标志 */ public NavigableSet
                      
                        headSet(E toElement, boolean inclusive) { return new TreeSet
                       
                        (m.headMap(toElement, inclusive)); } /** * 返回Set的尾部，范围是：从fromElement到结尾。 * inclusive是是否包含fromElement的标志 */ public NavigableSet
                        
                          tailSet(E fromElement, boolean inclusive) { return new TreeSet
                         
                          (m.tailMap(fromElement, inclusive)); } /** * 返回子Set。范围是：从fromElement(包括)到toElement(不包括)。 */ public SortedSet
                          
                            subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); } /** * 返回Set的头部，范围是：从头部到toElement(不包括)。 */ public SortedSet
                           
                             headSet(E toElement) { return headSet(toElement, false); } /** * 返回Set的尾部，范围是：从fromElement到结尾(不包括)。 */ public SortedSet
                            
                              tailSet(E fromElement) { return tailSet(fromElement, true); } // 返回Set的比较器 public Comparator
                              comparator() { return m.comparator(); } /** * 返回Set的第一个元素 */ public E first() { return m.firstKey(); } /** * 返回Set的最后一个元素 */ public E last() { return m.lastKey(); } // NavigableSet API methods /** * 返回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 = m.pollFirstEntry(); return (e == null)? null : e.getKey(); } /** * 获取最后一个元素，并将该元素从TreeMap中删除。 */ public E pollLast() { Map.Entry
                              
                                e = m.pollLastEntry(); return (e == null)? null : e.getKey(); } /** * 克隆一个TreeSet，并返回Object对象 */ public Object clone() { TreeSet
                               
                                 clone = null; try { clone = (TreeSet
                                
                                 ) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } clone.m = new TreeMap
                                 
                                  (m); return clone; } /** * java.io.Serializable的写入函数 * * 将TreeSet的“比较器、容量，所有的元素值”都写入到输出流中 */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden stuff 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
                                   c = (Comparator
                                  ) s.readObject(); // Create backing TreeMap TreeMap
                                  
                                    tm; if (c==null) tm = new TreeMap
                                   
                                    (); else tm = new TreeMap
                                    
                                     (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的方式。当写入到输出流时，依次写入“比较器、容量、全部元素”；当读出输入流时，再依次读取。