java 集合之TreeSet详解

首先说明一下，之前看了一下文章提出TreeSet在添加第一个元素的时候是不比较大小的，这种说发是错误的，在第一次添加的时候比较的是第一个对象本省返回的参数是0，下面我们用程序验证一下：

首先由一个Student的内部类：

里面有两个参数，年龄和名称我们后期自定义排序也是用得到的。然后我们把这个对象添加到TreeSet中，构建一个无参数的TreeSet。

这样添加我们是能看到程序报错:

然后我们写一个自定义的比较器Comparator来验证一下传入的第一个参数具体比较的对象：

在比较器中加一个断点，验证一下在第一次添加的时候比较的是什么：

通过断点我们可以看到

o1和o2是一样的因此第一个元素在录入到TreeSet中的时候比较的是他本身并且输出num=0，控制台输出：

下面来详细介绍一下TreeSet，首先定义我们从jdk1.8中看一下TreeSet是一个什么东西：

A NavigableSet实现基于TreeMap 。 的元件使用其有序natural ordering ，或由Comparator集合创建时提供，这取决于所使用的构造方法。

此实现提供了基本的操作（保证的log（n）时间成本add ， remove和contains ）。

TreeSet是一个不同步的非线程安全的二叉树。

Set<String> s2 = new TreeSet<>();

源码中是这样是实现的：构建一个按自然排序的空树集。必须实现Comparable接口。创建的是一个new TreeMap。

跟进到TreeMap中，创建一个新的空的tree map ,用作自然排序。所有的key的插入这个map必须实现Comparable接口。

用于维护元素的比较器。如果为null，则keys用的是自然排序。

上面简单介绍了一下创建一个TreeSet，等于创建一个空的自然排序的TreeMap容器。

容器提供了两种排序的方法，一种自然排序当comparator为空的时候，构建无参构造函数的时候默认的一种排序方式，下面看一下在往容器中添加值的时候是如何保证容器的顺序的，看一下源码中add方法。

TreeSet的添加方法实现了map的put方法，其中key为我们添加的变量值，value为定值Object对象。

后面跟进看一下具体的put方法，里面是如何实现对参数key的自然排序的。

我们来分析一下具体的实现通过添加几个随机数字分析下面先来粘贴一下源码根据源码和具体值来分析：

上面为具体实现的源码信息，我们来添加几个值分析一下：1,7,8,9,3,2

（1）添加这个1的时候由于是第一次添加Entry<K,V> t = root; 此时t=null;

        if (t == null) {
            compare(key, key); // type (and possibly null) check《1》
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;

          }

进入这个方法，由此《1》处可以看出第一次在TreeSet中添加值的时候，元素对比的是key自身。那么两个key目前的值为1，跟进compare(key, key);这个方法我们看一下具体比较的算法。

此时由于我们构造函数用的是无参数的没有指定比较器所以comparator比较器为空 

((Comparable<? super K>)k1).compareTo((K)k2)走的是这个 return 0；

然后直接新添加一条数据到Entry<k,v>中，并记录size = 1，且记录对树进行结构修改的次数++。

那么我们来思考一个问题？此时的root等于什么？

是的，此时root中存储的是我们刚刚录入的那个元素，k=1,value=new Object();的一个定值。

此时的树结构为：

（2）当我们添加7这个值的时候，put这个函数是怎么运行的呢？下面我们分析一下：

添加7的时候此时Entry<k,v> = root; root = 1;

此时t!=null;定义int cmp; 和 上层父类Entry<K,V> parent;由于我们构造的是无参数的构造函数，所以Comparator<? super K> cpr = comparator; comparator为null，走else这个代码块：

里面有个判断key为空的判断，如果key为空抛出异常，所以添加的key元素不能为空。

Comparable<? super K> k = (Comparable<? super K>) key;此时k=7，且t=1,t.key = 1;

cmp = k.compareTo(t.key); 这个比较的是 7 > 1，大于0，返回的cmp为1，也就是在根目录1的Reght右边：

此时树结构为：

+

（3）那么我们在添加一个8，看一下此时put函数是如何执行：

此时我们看一下root的值

key=1，根目录为1   在1的右边有一个值7

此时我们传入的8为Comparable<? super K> k = (Comparable<? super K>) key;此时k=8，且t.key = 1;

cmp = k.compareTo(t.key) = 正数在  根目录1的右边。此时树结构为：

       

此时结构的右边有7，那么还要跟7做一个比对cmp = k.compareTo(t.key) ，此时k=8 t.key = 7，cmp也是一个正数，在7的右边，此时最后的树结构为：

也就是后面这种

我们具体看一下程序中root的值，如下：

此时key = 7 , left = 1 ,right = 8。此时添加数字8进入树结构。

（4）然后我们添加一个数字6到树结构中，看一下具体put函数是如何运行的：

那么此时Comparable<? super K> k = (Comparable<? super K>) key;我们传入的参数key=6 。

cmp = k.compareTo(t.key); cmp = 6和7对比，6<7返回一个负数，cmp < 0 ,在7的left左边。此时的树结构为：

此时左边还有一个1，在跟1比较，cmp返回一个正数大于0，所以在1的右边，最终定型为：6在7的左边在1的右边。

（5）后面我们添加一个5数字，看一下put函数具体运行：

先看一下目前的root的值信息：

key = 7, left = 1  right = 8 

此时Comparable<? super K> k = (Comparable<? super K>) key; key = 我们传入的参数 5.

第一次对比：cmp = k.compareTo(t.key); = 5和7对比 5>7返回负数在7的left

第二次对比：cmp = k.compareTo(t.key); = 5和1对比 5>1返回正数在1的right

然后我们看一下1的树机构：

此时1的树结构如图为：

此时由于第二次返回了right在1的右边有6需要进行第三次对比

第三次对比：cmp = k.compareTo(t.key); = 5和6对比 5>6返回负数在6的left 左边

此时root中的结构为：

key为根目录，此时key = 7 left = 5  right = 8 为第一层树结构：

其中5位跟目录还有二层树结构，最终形成树结构为：

我们读取数据的时候从遵循一个左中右的读取顺序为：1,5,6,7,8 自然排序为升序。

总结：此过程讲解的是TreeSet的自然排序的一个过程以及比对的具体源码实现方案，其中有讲解错误的地方，还评论指出。

其中有key不能为空的原因。后续会在其他文章中讲解自定义排序。还有哪些方面需要总结的也欢迎评论指出。