TreeSet集合的add()方法的源码解析

用TreeSet存储Integer类型数据并遍历

  20,18,23,22,17,24,19,18,24

 1 package cn.itcast_05;
 2 
 3 import java.util.TreeSet;
 4 
 5 /*
 6  * TreeSet:能够对元素按照某种规则进行排序。
 7  *         排序有两种方式(具体那种方式取决于使用TreeSet的构造方法)
 8  *             A:自然排序
 9  *             B:比较器排序
10  * 
11  * TreeSet集合的特点:排序和唯一
12  * 
13  * 通过观察TreeSet的add()方法,我们知道最终要看TreeMap的put()方法。
14  */
15 public class TreeSetDemo {
16     public static void main(String[] args) {
17         // 创建集合对象
18         // TreeSet的无参构造:自然顺序进行排序
19         TreeSet<Integer> ts = new TreeSet<Integer>();
20 
21         // 创建元素并添加进集合
22         // 20,18,23,22,17,24,19,18,24
23         // Integer i1 = new Integer(200);
24         // ts.add(i1);
25         ts.add(20); // 自动装箱
26         ts.add(18);
27         ts.add(23);
28         ts.add(22);
29         ts.add(17);
30         ts.add(24);
31         ts.add(19);
32         ts.add(18);
33         ts.add(24);
34 
35         // 遍历集合
36         for (Integer i : ts) {
37             System.out.println(i);
38         }
39     }
40 }

TreeSet集合的add()方法的源码

---------------------------------------
interface Collection {
    ...
}

interface Set extends Collection {
    ...
}
---------------------------------------
class TreeSet implements Set {
    ...
    private static final Object PRESENT = new Object();
    private transient NavigableMap<E,Object> m;
    
    public TreeSet() {
         this(new TreeMap<E,Object>());
    }

    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
    ...
}
---------------------------------------
class TreeMap implements NavigableMap {
    ...
    public V put(K key, V value) {
       Entry<K,V> t = root; // 先造根,TreeSet集合底层数据结构是红黑树(是一个自平衡的二叉树)
       if (t == null) {
           compare(key, key); // type (and possibly null) check

           root = new Entry<>(key, value, null);
           size = 1;
           modCount++;
           return null;
       }
       
       int cmp;
       Entry<K,V> parent;
       // split comparator and comparable paths
       Comparator<? super K> cpr = comparator; // 因为用的是TreeSet的无参构造方法,是自然排序,没有用到comparator比较器
       if (cpr != null) {                      // 所以此时的comparator = null,则程序执行else里面的代码
           do {
               parent = t;
               cmp = cpr.compare(key, t.key);
               if (cmp < 0)
                   t = t.left;
               else if (cmp > 0)
                   t = t.right;
               else
                   return t.setValue(value);
           } while (t != null);
       } else {
           if (key == null)
               throw new NullPointerException();
           Comparable<? super K> k = (Comparable<? super K>) key; // 此接口Comparable强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序,类的 compareTo 方法被称为它的自然比较方法。。
           do {                                                   // 举例中我们使用的是包装类Intrger,而Integer类实现了Comparable接口。此例子是向上转型。
               parent = t;
               cmp = k.compareTo(t.key); // 类的 compareTo 方法被称为它的自然比较方法。
               if (cmp < 0)              // int compareTo(T o) 比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象,则分别返回负整数、零或正整数。 
                   t = t.left;
               else if (cmp > 0)
                   t = t.right;
               else
                   return t.setValue(value);
           } while (t != null);
       }
       
       Entry<K,V> e = new Entry<>(key, value, parent);
       if (cmp < 0)
           parent.left = e;
       else
           parent.right = e;
       fixAfterInsertion(e);
       size++;
       modCount++;
       return null;
   }
   ...
}
---------------------------------------
    由上可知:真正的比较是依赖于元素的compareTo()方法,而这个方法compareTo()是定义在 Comparable接口里面的(抽象方法)。
    所以,你要想重写该方法,就必须是先实现 Comparable接口。这个接口表示的就是自然排序。
---------------------------------------

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏别先生

java中集合类中Collection接口中的Set接口的常用方法熟悉

1:Set集合由Set接口和Set接口的实现类组成,Set接口继承了Collection接口,因为包含Collection接口的所有方法。 2:由于Set接口中...

220100
来自专栏一直在跳坑然后爬坑

Kotlin之“ArrayList”

30320
来自专栏博岩Java大讲堂

Java集合--Set(深入学习)

414100
来自专栏韦弦的偶尔分享

Swift 有效的括号 - LeetCode

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

20920
来自专栏老马说编程

(38) 剖析ArrayList / 计算机程序的思维逻辑

从本节开始,我们探讨Java中的容器类,所谓容器,顾名思义就是容纳其他数据的,计算机课程中有一门课叫数据结构,可以粗略对应于Java中的容器类,我们不会介绍所有...

22850
来自专栏老马说编程

(44) 剖析TreeSet / 计算机程序的思维逻辑

41节介绍了HashSet,我们提到,HashSet有一个重要局限,元素之间没有特定的顺序,我们还提到,Set接口还有另一个重要的实现类TreeSet,它是有序...

22490
来自专栏机器学习从入门到成神

Java之使用增强for循环和迭代器遍历

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

23110
来自专栏陈树义

3.Java集合总结系列:Set接口及其实现

一、Set接口 Set 接口与 List 接口相比没有那么多操作方法,比如: 1、List 接口能直接设置或获取某个元素的值,而Set接口不能。 2、List ...

40550
来自专栏desperate633

Java的HashMap中的常用方法总结遍历HashMap打印HashMap根据HashMap的value进行排序

HashMap在编程中是一个非常有用的工具,使用的频率很高,所以本文简单总结一下hashmap的常用方法

10410
来自专栏小筱月

java map遍历、排序,根据value获取key

若要取 map 中 value 的最大值 或 与之对应的 key(整型或浮点型):可利用list

1.1K20

扫码关注云+社区

领取腾讯云代金券