Java中的TreeSet

1.源码如下：

TreeSet
A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural 
ordering, or by a Comparator provided at set creation time, depending on which constructor is
used. 
This implementation provides guaranteed log(n) time cost for the basic operations 
(add, remove and contains). 

Note that the ordering maintained by a set (whether or not an explicit comparator is provided)
must be consistent with equals if it is to correctly implement the Set interface. 
(See Comparable or Comparator for a precise definition of consistent with equals.) 
This is so because the Set interface is defined in terms of the equals operation, 
but a TreeSet instance performs all element comparisons using its compareTo (or compare) method,
so two elements that are deemed equal by this method are, from the standpoint of the set, equal.
The behavior of a set is well-defined even if its ordering is inconsistent with equals;
it just fails to obey the general contract of the Set interface. 

Note that this implementation is not synchronized. If multiple threads access a tree set
concurrently, and at least one of the threads modifies the set, it must be synchronized 
externally. This is typically accomplished by synchronizing on some object that naturally
encapsulates the set. If no such object exists, the set should be "wrapped" using the
Collections.synchronizedSortedSet method. This is best done at creation time, to prevent
accidental unsynchronized access to the set: 

   SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
The iterators returned by this class's iterator method are fail-fast: if the set is modified at
any time after the iterator is created, in any way except through the iterator's own remove 
method, the iterator will throw a ConcurrentModificationException. Thus, in the face of 
concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, 
non-deterministic behavior at an undetermined time in the future. 

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally 
speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent 
modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. 
Therefore, it would be wrong to write a program that depended on this exception for its 
correctness: the fail-fast behavior of iterators should be used only to detect bugs. 

This class is a member of the Java Collections Framework.

Since: 
1.2 
See Also: 
Collection, Set, HashSet, Comparable, Comparator, TreeMap, Serialized Form 

2.译注：

【TreeSet是】基于TreeMap的NavigableSet实现。元素按照他们的自然顺序来排序，否则根据set创建时所使用的构造器设定的Compactor排序。【非常重要】
对于基础的操作（增加，移动，是否包含），TreeSet提供了保证log(n)的时间复杂度。

注意：如果想要正确的实现Set接口，set包含的排序（无论是否提供一个显式的compactor）必须和equals相一致。请参阅Comparable或者Comparator去获得一个与equals相同的精确定义。

3.关键点

• 实现TreeSet的关键点是：往treeSet中写入的对象需要重写comparator()方法
  1.自然排序
  2.比较器排序
  
  • TreeSet底层是红黑树。
  • TreeSet是Set，所以其不会存储重复数据。

4.面试题

示例1

 package grammar;

import java.util.Iterator;
import java.util.TreeSet;

public class TestTreeSet {
    private static TreeSet<Integer> treeset = new TreeSet();

    public static void main(String[] args) {
        testOne();
    }

    public static void testOne(){
        treeset.add(11);
        treeset.add(4);
        treeset.add(8);
        treeset.add(5);
        treeset.add(20);
        //可以看到这个是默认有序的
        Iterator iterator = treeset.iterator();
        while(iterator.hasNext()){
            System.out.print(iterator.next()+" ");
        }
    }
}

输出结果是：4 5 8 11 20

示例2

• TestTreeSet类

package grammar;

import java.util.Iterator;
import java.util.TreeSet;

public class TestTreeSet {
    private static TreeSet<Student> treeset = new TreeSet();

    private static int maxSize = 10;
    public static void main(String[] args) {
        testOne();
    }

    public static void testOne(){
        Student students []  = new Student[maxSize];

        for(int i = 0;i< 10;i++){
            int randomNumber  = (int)(Math.random()*10);
            System.out.println("randonNumber is :"+randomNumber);
            students[i] = new Student(randomNumber);//实例化Student对象
            treeset.add(students[i]);
        }

        //可以看到这个是默认有序的
        Iterator iterator = treeset.iterator();
        while(iterator.hasNext()){
            System.out.print(iterator.next()+" ");//获取的是一个引用，如果不重写toString()方法，
            //将会输出hashcode值
        }
    }
}

• Student类

//Comparable后面一定不能少了<Student>这个泛型，否则后面一直会是Object类型的o，而不是Student型的变量
class Student implements Comparable<Student>{
    int age;
    String name;

    //实现这个接口时，需要重定义这个compareTo方法
    @Override
    public int compareTo(Student student) {
        if(this.age > student.age) return 1;
        else if(this.age < student.age) return -1;
        else return 0;
    }
    public Student(){

    }

    public Student(int age){
        this.age = age;
    }

    @Override
    //重写不能改变方法的参数，返回值类型。比如说，这里的age是int型，但是你不能返回int型变量，而是返回age+""，
    //从而修改成一个字符串返回
    public String toString(){
        return this.age+"";
    }
}

运行结果：

randonNumber is :7
randonNumber is :1
randonNumber is :6
randonNumber is :6
randonNumber is :1
randonNumber is :7
randonNumber is :0
randonNumber is :6
randonNumber is :9
randonNumber is :3
0 1 3 6 7 9 

5.总结