• TreeSet解析

    目录

    一、TreeSet介绍

    二、源码分析

    1、TreeSet实现的接口

    2、TreeSet中的变量

    3、TreeSet的构造方法

    （1）同包下的构造方法

    （2）无参构造方法

    （3）带比较器的构造方法

    （4）带集合参数的构造方法

    （5）带SortMap的构造方法

    4、常用方法

    5、TreeSet的两种排序方式

    （1）实现Comparator接口，重写compare方法

     （2）实现Comparable接口，覆写compareTo()方法

    三、总结

    1、TreeSet总结

    2、 HashSet、LinkedHashSet 以及 TreeSet。

    （1）HashSet

    （2）LinkedHashSet

    （3）TreeSet

    （4）使用场景

    （5）对象的加入过程

    一、TreeSet介绍

            TreeSet是一个有序的集合，基于TreeMap实现，支持两种排序方式：自然排序和定制排序。
    TreeSet是非同步的，线程不安全的。

    二、源码分析

    1、TreeSet实现的接口

            如下图：

    观察上图：

    • AbstractSet类：该类提供了Set接口的骨架实现，通过扩展此类来实现集合的过程与通过扩展AbstractCollection实现集合的过程相同，除了此类的子类中的所有方法和构造函数都必须遵守由Set接口施加的附加约束（例如，添加方法不能允许将一个对象的多个实例添加到集合中）。
    • Navigable接口：支持一系列的导航方法。比如查找与指定目标最匹配项。
    • Serializable接口：主要用于序列化，即：能够将对象写入磁盘。与之对应的还有反序列化操作，就是将对象从磁盘中读取出来。因此如果要进行序列化和反序列化，ArrayList的实例对象就必须实现这个接口，否则在实例化的时候程序会报错（java.io.NotSerializableException）。
    • Cloneable接口：实现Cloneable接口的类能够调用clone方法，如果没有实现Cloneable接口就调用方法，就会抛出异常（java.lang.CloneNotSupportedException）。

    2、TreeSet中的变量

    • private transient NavigableMap m：存放元素的集合
    • private static final Object PRESENT = new Object()：常量，构造一个虚拟的对象PRESENT，默认为map的value值（HashSet中只需要用到键，而HashMap是key-value键值对，使用PRESENT作为value的默认填充值，解决差异问题）

    3、TreeSet的构造方法

    （1）同包下的构造方法

    1.     TreeSet(NavigableMap m) {
    2.         this.m = m;
    3.     }

    （2）无参构造方法

    1.     public TreeSet() {
    2.         this(new TreeMap());
    3.     }

    （3）带比较器的构造方法

    1.     public TreeSet(Comparatorsuper E> comparator) {
    2.         this(new TreeMap<>(comparator));
    3.     }

    （4）带集合参数的构造方法

    1.     public TreeSet(Collection c) {
    2.         this();
    3.         addAll(c);
    4.     }

    （5）带SortMap的构造方法

    1.     public TreeSet(SortedSet s) {
    2.         this(s.comparator());
    3.         addAll(s);
    4.     }

            通过上面的构造方法，可以看出TreeSet的底层是用TreeMap实现的。在构造方法中会创建一个TreeMap实例，用于存放元素，另外TreeSet是有序的，也提供了制定比较器的构造函数，如果没有提供比较器，则采用key的自然顺序进行比较大小，如果指定的比较器，则采用指定的比较器，进行key值大小的比较。

    4、常用方法

    1. //遍历方法，返回m.keyset集合
    2.     public Iterator iterator() {
    3.         return m.navigableKeySet().iterator();
    4.     }
    5.  
    6.     //逆序排序的迭代器
    7.     public Iterator descendingIterator() {
    8.         return m.descendingKeySet().iterator();
    9.     }
    10.  
    11.     /**
    12.      * @since 1.6
    13.      */
    14.     public NavigableSet descendingSet() {
    15.         return new TreeSet<>(m.descendingMap());
    16.     }
    17.  
    18.     //返回 m 包含的键值对的数量
    19.     public int size() {
    20.         return m.size();
    21.     }
    22.  
    23.     //是否为空
    24.     public boolean isEmpty() {
    25.         return m.isEmpty();
    26.     }
    27.  
    28.     //是否包含指定的key
    29.     public boolean contains(Object o) {
    30.         return m.containsKey(o);
    31.     }
    32.  
    33.     //添加元素，调用m.put方法实现
    34.     public boolean add(E e) {
    35.         return m.put(e, PRESENT)==null;
    36.     }
    37.  
    38.     //删除方法，调用m.remove()方法实现
    39.     public boolean remove(Object o) {
    40.         return m.remove(o)==PRESENT;
    41.     }
    42.  
    43.     //清除集合
    44.     public void clear() {
    45.         m.clear();
    46.     }
    47.  
    48.     //将一个集合中的所有元素添加到TreeSet中
    49.     public  boolean addAll(Collection c) {
    50.         // Use linear-time version if applicable
    51.         if (m.size()==0 && c.size() > 0 &&
    52.             c instanceof SortedSet &&
    53.             m instanceof TreeMap) {
    54.             SortedSetextends E> set = (SortedSetextends E>) c;
    55.             TreeMap map = (TreeMap) m;
    56.             Comparatorsuper E> cc = (Comparatorsuper E>) set.comparator();
    57.             Comparatorsuper E> mc = map.comparator();
    58.             if (cc==mc || (cc != null && cc.equals(mc))) {
    59.                 map.addAllForTreeSet(set, PRESENT);
    60.                 return true;
    61.             }
    62.         }
    63.         return super.addAll(c);
    64.     }
    65.  
    66.     //返回子集合，通过 m.subMap()方法实现
    67.     public NavigableSet subSet(E fromElement, boolean fromInclusive,
    68.                                   E toElement,   boolean toInclusive) {
    69.         return new TreeSet<>(m.subMap(fromElement, fromInclusive,
    70.                                        toElement,   toInclusive));
    71.     }
    72.  
    73.     //返回set的头部
    74.     public NavigableSet headSet(E toElement, boolean inclusive) {
    75.         return new TreeSet<>(m.headMap(toElement, inclusive));
    76.     }
    77.  
    78.     //返回尾部
    79.     public NavigableSet tailSet(E fromElement, boolean inclusive) {
    80.         return new TreeSet<>(m.tailMap(fromElement, inclusive));
    81.     }
    82.  
    83.     //返回子Set
    84.     public SortedSet subSet(E fromElement, E toElement) {
    85.         return subSet(fromElement, true, toElement, false);
    86.     }
    87.  
    88.     //返回set的头部
    89.     public SortedSet headSet(E toElement) {
    90.         return headSet(toElement, false);
    91.     }
    92.  
    93.     //返回set的尾部
    94.     public SortedSet tailSet(E fromElement) {
    95.         return tailSet(fromElement, true);
    96.     }
    97.     //返回m使用的比较器
    98.     public Comparatorsuper E> comparator() {
    99.         return m.comparator();
    100.     }
    101.  
    102.     //返回第一个元素
    103.     public E first() {
    104.         return m.firstKey();
    105.     }
    106.     //返回最后一个元素
    107.     public E last() {
    108.         return m.lastKey();
    109.     }
    110.  
    111.     //返回set中小于e的最大的元素
    112.     public E lower(E e) {
    113.         return m.lowerKey(e);
    114.     }
    115.  
    116.     //返回set中小于/等于e的最大元素
    117.     public E floor(E e) {
    118.         return m.floorKey(e);
    119.     }
    120.  
    121.     //返回set中大于/等于e的最大元素
    122.     public E ceiling(E e) {
    123.         return m.ceilingKey(e);
    124.     }
    125.  
    126.     //返回set中大于e的最小元素
    127.     public E higher(E e) {
    128.         return m.higherKey(e);
    129.     }
    130.  
    131.     //获取TreeSet中第一个元素，并从Set中删除该元素
    132.     public E pollFirst() {
    133.         Map.Entry e = m.pollFirstEntry();
    134.         return (e == null) ? null : e.getKey();
    135.     }
    136.  
    137.     //获取TreeSet中最后一个元素，并从Set中删除该元素
    138.     public E pollLast() {
    139.         Map.Entry e = m.pollLastEntry();
    140.         return (e == null) ? null : e.getKey();
    141.     }
    142.  
    143.     //克隆方法
    144.     public Object clone() {
    145.         TreeSet clone = null;
    146.         try {
    147.             clone = (TreeSet) super.clone();
    148.         } catch (CloneNotSupportedException e) {
    149.             throw new InternalError();
    150.         }
    151.  
    152.         clone.m = new TreeMap<>(m);
    153.         return clone;
    154.     }
    155.  
    156.     //将对象写入到输出流中。
    157.     private void writeObject(java.io.ObjectOutputStream s)
    158.         throws java.io.IOException {
    159.         // Write out any hidden stuff
    160.         s.defaultWriteObject();
    161.  
    162.         // Write out Comparator
    163.         s.writeObject(m.comparator());
    164.  
    165.         // Write out size
    166.         s.writeInt(m.size());
    167.  
    168.         // Write out all elements in the proper order.
    169.         for (E e : m.keySet())
    170.             s.writeObject(e);
    171.     }
    172.  
    173.     //从输入流中读取对象的信息
    174.     private void readObject(java.io.ObjectInputStream s)
    175.         throws java.io.IOException, ClassNotFoundException {
    176.         // Read in any hidden stuff
    177.         s.defaultReadObject();
    178.  
    179.         // Read in Comparator
    180.         Comparatorsuper E> c = (Comparatorsuper E>) s.readObject();
    181.  
    182.         // Create backing TreeMap
    183.         TreeMap tm;
    184.         if (c==null)
    185.             tm = new TreeMap<>();
    186.         else
    187.             tm = new TreeMap<>(c);
    188.         m = tm;
    189.  
    190.         // Read in size
    191.         int size = s.readInt();
    192.  
    193.         tm.readTreeSet(size, s, PRESENT);
    194.     }

    5、TreeSet的两种排序方式

    （1）实现Comparator接口，重写compare方法

    1.  
    2. import java.util.*;
    3.  
    4. class Student{
    5.     private int id;
    6.     private String name;
    7.     private int age;
    8.  
    9.     public Student(int id, String name, int age) {
    10.         this.id = id;
    11.         this.name = name;
    12.         this.age = age;
    13.     }
    14.  
    15.     public int getId() {
    16.         return id;
    17.     }
    18.  
    19.     public void setId(int id) {
    20.         this.id = id;
    21.     }
    22.  
    23.     public String getName() {
    24.         return name;
    25.     }
    26.  
    27.     public void setName(String name) {
    28.         this.name = name;
    29.     }
    30.  
    31.     public int getAge() {
    32.         return age;
    33.     }
    34.  
    35.     public void setAge(int age) {
    36.         this.age = age;
    37.     }
    38.  
    39.     @Override
    40.     public String toString() {
    41.         return "Student{" +
    42.                 "id=" + id +
    43.                 ", name='" + name + '\'' +
    44.                 ", age=" + age +
    45.                 '}';
    46.     }
    47. }
    48. class MyComparator implements Comparator{
    49.  
    50.     @Override
    51.     public int compare(Object o1, Object o2) {
    52.         Student s1 = (Student) o1;
    53.         Student s2 = (Student) o2;
    54.         return s1.getAge() - s2.getAge();
    55.     }
    56. }
    57. public class Main {
    58.     public static void main(String[] args) {
    59.         TreeSet treeSet = new TreeSet(new MyComparator());
    60.         treeSet.add(new Student(1, "tom", 23));
    61.         treeSet.add(new Student(2, "Jerry", 20));
    62.         treeSet.add(new Student(3, "Jack", 17));
    63.         treeSet.add(new Student(4, "Marry", 54));
    64.         treeSet.add(new Student(5, "Baby", 8));
    65.         Iterator iterator = treeSet.iterator();
    66.         while(iterator.hasNext()){
    67.             System.out.println(iterator.next());
    68.         }
    69.  
    70.     }
    71. }

     

     

     （2）实现Comparable接口，覆写compareTo()方法

    1. import java.util.*;
    2.  
    3. class Student implements Comparable{
    4.     private int id;
    5.     private String name;
    6.     private int age;
    7.  
    8.     public Student(int id, String name, int age) {
    9.         this.id = id;
    10.         this.name = name;
    11.         this.age = age;
    12.     }
    13.  
    14.     public int getId() {
    15.         return id;
    16.     }
    17.  
    18.     public void setId(int id) {
    19.         this.id = id;
    20.     }
    21.  
    22.     public String getName() {
    23.         return name;
    24.     }
    25.  
    26.     public void setName(String name) {
    27.         this.name = name;
    28.     }
    29.  
    30.     public int getAge() {
    31.         return age;
    32.     }
    33.  
    34.     public void setAge(int age) {
    35.         this.age = age;
    36.     }
    37.  
    38.     @Override
    39.     public String toString() {
    40.         return "Student{" +
    41.                 "id=" + id +
    42.                 ", name='" + name + '\'' +
    43.                 ", age=" + age +
    44.                 '}';
    45.     }
    46.  
    47.     @Override
    48.     public int compareTo(Object o) {
    49.         if(!(o instanceof Student)){
    50.             throw new RuntimeException("对象有问题");
    51.         }
    52.         Student s = (Student) o;
    53.         if(this.age > s.age){
    54.             return -1;
    55.         }else{
    56.             return 1;
    57.         }
    58.     }
    59. }
    60.  
    61. public class Main {
    62.     public static void main(String[] args) {
    63.         TreeSet treeSet = new TreeSet();
    64.         treeSet.add(new Student(1, "tom", 23));
    65.         treeSet.add(new Student(2, "Jerry", 20));
    66.         treeSet.add(new Student(3, "Jack", 17));
    67.         treeSet.add(new Student(4, "Marry", 54));
    68.         treeSet.add(new Student(5, "Baby", 8));
    69.         Iterator iterator = treeSet.iterator();
    70.         while(iterator.hasNext()){
    71.             System.out.println(iterator.next());
    72.         }
    73.  
    74.     }
    75. }

     

     

    三、总结

    1、TreeSet总结

    • TreeSet实际上是TreeMap实现的，所以底层结构也是红黑树。TreeSet不需要重写hashCode()和euqals()方法，因为它去重是依靠比较器来去重，因为结构是红黑树，所以每次插入都会遍历比较来寻找节点插入位置，如果发现某个节点的值是一样的那就会直接覆盖。
    • 当我们构造TreeSet时；若使用不带参数的构造函数，则TreeSet的使用自然比较器；若用户需要使用自定义的比较器，则需要使用带比较器的参数。
    • TreeSet是非线程安全的。
    • TreeSet实现java.io.Serializable的方式。当写入到输出流时，依次写入“比较器、容量、全部元素”；当读出输入流时，再依次读取。 

    2、 HashSet、LinkedHashSet 以及 TreeSet。

    （1）HashSet

    • 不能保证元素的排列顺序，顺序有可能发生变化
    • 不是同步的，非线程安全
    • 集合元素可以是null，但只能放入一个null
    • 当向HashSet结合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据 hashCode值来决定该对象在HashSet中存储位置。
    • 简单的说，HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode()方法返回值相等
    • 注意，如果要把一个对象放入HashSet中，重写该对象对应类的equals方法，也应该重写其hashCode()方法。其规则是如果两个对象通过equals方法比较返回true时，其hashCode也应该相同。另外，对象中用作equals比较标准的属性，都应该用来计算hashCode的值。

    （2）LinkedHashSet

            LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起 来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。

    • LinkedHashSet中不能有相同元素，可以有一个Null元素，元素严格按照放入的顺序排列。
    • LinkedHashSet底层数据结构由哈希表和链表组成，链表保证了元素的有序即存储和取出一致，哈希表保证了元素的唯一性。
    • LinkedHashSet添加、删除操作时间复杂度都是O(1)。

    （3）TreeSet

    • TreeSet支持两种排序方式，自然排序 和定制排序，其中自然排序为默认的排序方式。向TreeSet中加入的应该是同一个类的对象。
    • TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0
    • TreeSet是中不能有相同元素，不可以有Null元素，根据元素的自然顺序进行排序。
    • TreeSet底层的数据结构是红黑树(一种自平衡二叉查找树)
    • 添加、删除操作时间复杂度都是O(log(n))

    （4）使用场景

             HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。 

    （5）对象的加入过程

            TreeSet集合对象的加入过程： 
            TreeSet的底层是通过二叉树来完成存储的，无序的集合 
            当我们将一个对象加入treeset中，treeset会将第一个对象作为根对象，然后调用对象的compareTo方法拿第二个对象和第一个比较，当返回值等于0时，说明2个对象内容相等，treeset就不把第二个对象加入集合。返回>1时，说明第二个对象大于第一个对象，将第二个对象放在右边，返回-1时，则将第二个对象放在左边，依次类推 。

            HashSet集合对象的加入过程： 
            hashset底层是hash值的地址，它里面存的对象是无序的。 
            第一个对象进入集合时，hashset会调用object类的hashcode根据对象在堆内存里的地址调用对象重写的hashcode计算出一个hash值，然后第一个对象就进入hashset集合中的任意一个位置。 
            第二个对象开始进入集合，hashset先根据第二个对象在堆内存的地址调用对象的计算出一个hash值，如果第二个对象和第一个对象在堆内存里的地址是相同的，那么得到的hash值也是相同的，直接返回true，hash得到true后就不把第二个元素加入集合（这段是hash源码程序中的操作）。如果第二个对象和第一个对象在堆内存里地址是不同的，这时hashset类会先调用自己的方法遍历集合中的元素，当遍历到某个元素时，调用对象的equals方法，如果相等，返回true，则说明这两个对象的内容是相同的，hashset得到true后不会把第二个对象加入集合。 

  • 相关阅读:
    Linux基础知识——git简说
    git学习笔记 - 上传文件
    广西小额贷款公司名单 （截至2023年5月31日）
    [西湖论剑 2022]web部分题解（更新中ing)
    Python-模块系列-zip()函数-range()函数-sum()函数-shuffle() 随机函数
    redis 高级数据类型之 位图（bitmap） 详细介绍
    微信小程序隐藏video标签的进度条组件
    利用对话式人工智能简化运营：案例研究
    linux 系统文件目录颜色及特殊权限对应的颜色
    【Linux学习笔记】 - 项目自动化工具make/Makefile的使用
  • 原文地址：https://blog.csdn.net/weixin_47382783/article/details/126027007