HashSet 和TreeSet的区别源码分析

Stack overFlow上有句话：
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.
https://stackoverflow.com/questions/1463284/hashset-vs-treeset

HashSet
HashSet is faster than TreeSet,但是没办法像TreeSet一样提供有序集合。
HashSet 基本操作（add remove contains） 时长是固定的
1）implement Set 集合，
2） backed by a hash table (actually a HashMap instance).--由hash表支持，
实际是hashMap
3）不能保证元素的排列顺序，顺序有可能发生变化
4）不是同步的，解决方案：
Set s = Collections.synchronizedSet(new HashSet(...));
5）集合元素可以是null,但只能放入一个null

Treeset
1）而Treeset 则是 log(n) time cost for the basic operations (add, remove and
contains).
2）Treeset 是SortedSet唯一实现 支持2种排序方式，自然排序和定制排序
向TreeSet中加入的应该是同一个类的对象。

TreeSet排序特征：
1）TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，
或者通过CompareTo方法比较没有返回0

2）自然排序是根据元素集合的大小，即元素本身具备自然顺序；如果定制排序，即元素本身没有自然顺序，那么该元素所属的类必须要实现Comparable接口，把元素的比较规则定义在compareTo(T o)方法上。（需实现Comparator compare To(obj1, obj2) 方法）

3）如果比较的元素comoare to返回0 ，则认为是一致的元素，不会添加入集合。

4）往Treeset 中添加元素时，如果所属类没有自然顺序，且元素所属的类也没有实现 Comparable 接口，那么就要在创建Treeset时传入比较器；如果所属的类既实现了Comparable接口，又在创建Treeset时传入了自定义的Comparotor，那么，优先排序Comparotor。
例如：
自定义的元素 Students

public class Students implements Comparable {
    private String name;
    public int id;
    private int no;

    public Students(String name, int no) {
        this.name = name;
        this.no = no;
    }

    public Students(String name,  int no,int id) {
        this.name = name;
        this.id = id;
        this.no = no;
    }

    public String toString() {
        return "studentNo" + no + " " + "name" + name +" id"+id;
    }

    @Override
    public int compareTo(@NonNull Object o) {
        Log.e("treeset compareTo--", "");
        Students students = (Students) o;
        int result = no > students.no ? 1 : (no == students.no ? 0 : -1);
        if (result == 0) {
            result = name.compareTo(students.name);
        }
        return result;

    }
}

自定义的Comparator

public class MyComparator implements Comparator<Students> {
    @Override
    public int compare(Students o1, Students o2) {
        return (o1.id - o2.id);
    }
}

TreeSet 中添加元素

//创建一个比较器
        MyComparator myComparator =new MyComparator();
        TreeSet treeSet1 =new TreeSet(myComparator);
        treeSet1.add(new Students("zs",3,2));
        treeSet1.add(new Students("ss",5,1));
        treeSet1.add(new Students("fs",4,5));
        treeSet1.add(new Students("ls",6,3));
        treeSet1.add(new Students("bs",8,4));

结果输出：

treeset排序.jpeg

可见，是comparator优先级 最先。

Treeset 默认是对字符串String 排序的，因为String已经实现了Comparable接口。
字符串的比较规则：

情况一： 找到第一个不同的字符进行比较,大就是大 ("abf" > "abcasdfasdfa")

情况二： 如果没有不同的字符,那么哪个字符串长就是哪个 ("abcd" > "adc")

HashSet 和TreeSet 的要点：
1）Both guarantee duplicate-free collection of elements
保证元素不重复
2）It is generally faster to add elements to the HashSet and then convert the
collection to a TreeSet for a duplicate-free sorted traversal.
hashset添加元素比较快，所以一般先向HashSet添加元素，再转化为
Treeset有序集合
eg.
SortedSet<String> s = new TreeSet<String>(hashSet);
3）None of these implementations 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.
2个都是线程安全的，当多个线程同时访问，且至少一个线程要改变集合
时，要外部手动加入同步
4）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.
LinkedHashMap介于 HashSet TreeSet 之间，实现的是一个贯穿有linklist的
hashtable,它提供的是插入顺序迭代，和Treeset保证的排序遍历不同。

Treeset的源码：
是继承 TreeMap的put和get() add() 方法分析：