自学内容网 自学内容网
自学内容网 > 正文

TreeSet源码解析和设计思路

🕗 发布于 2024-03-18 13:42 java  后端  

TreeSet

一、继承体系

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

在Java JDK 1.8中，TreeSet类的源码继承结构如下：

  1. java.util.TreeSet<E>：
    TreeSet是基于有序树的集合类，它实现了NavigableSet接口，提供了基于红黑树的集合实现。
    通过继承AbstractSet和实现NavigableSet接口，TreeSet获得了Set接口的基本实现，并获得了导航集特定操作的支持。
    TreeSet还实现了Cloneable接口和Serializable接口，支持克隆和序列化。

  2. java.util.AbstractSet<E>：
    AbstractSet是实现了Set接口的抽象类，它进一步扩展了AbstractCollection，提供了Set接口的部分实现。
    AbstractSet中包含了Set接口的相关方法的实现，简化了具体Set实现类的开发。

  3. java.util.AbstractCollection<E>：
    AbstractCollection是实现了Collection接口的抽象类，定义了一些集合操作的通用实现。
    AbstractCollection提供了大部分Collection接口的实现，使得继承它的子类（如AbstractList、AbstractSet等）可以更方便地实现集合类。

TreeSet通过继承AbstractSet和实现NavigableSet接口，结合了抽象类和接口的优势，提供了基于有序树的集合实现，并支持克隆和序列化功能。

二、TreeSet全局变量分析

   /**
     * The backing map.
     */
    private transient NavigableMap<E,Object> m;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

  1. private transient NavigableMap<E, Object> m;

    • 通过使用NavigableMap作为底层数据结构，TreeSet实现了有序集合的特性，并提供了诸如查找最小/最大元素、子集操作等导航集（NavigableSet）的功能。

  2. private static final Object PRESENT = new Object();

    • 这是一个私有的静态常量，用于作为m中的值的占位符。由于TreeSet底层使用NavigableMap来存储元素，而NavigableMap实际上是基于TreeMap实现的，TreeMap要求键值对都是存储的，不能只存储键而不存储值，因此需要一个占位符来占据值的位置。
    • 在TreeSet中，所有元素都被存储为NavigableMap的键，而值则被设置为PRESENT，从而在实际存储过程中，值并不会真正占据内存空间，作为值的占位符。

三、初始化对象

    TreeSet(NavigableMap<E,Object> m) {        
         this.m = m;
    }
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }
    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }

  1. public TreeSet()：

    • 创建一个空的TreeSet，使用默认的自然顺序进行排序。此构造函数要求集合中插入的所有元素都必须实现Comparable接口，并且这些元素必须是相互可比较的。

  2. public TreeSet(Comparator<? super E> comparator)：

    • 这个构造函数创建一个空的TreeSet，根据指定的比较器进行排序。要求插入到集合中的所有元素必须能够通过指定的比较器相互比较。

  3. public TreeSet(Collection<? extends E> c)：

    • 这个构造函数创建一个包含指定集合中元素的新TreeSet，按照元素的自然顺序排序。要求集合中插入的所有元素都必须实现Comparable接口，并且这些元素必须是相互可比较的。

  4. public TreeSet(SortedSet s)：

    • 这个构造函数创建一个包含与指定排序集相同元素和相同排序方式的新TreeSet。
    • 使用指定排序集的比较器来初始化新的TreeSet，并将指定排序集中的所有元素添加到新集合中。

四、add添加方法

 public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

组合TreeMap的put方法

五、TreeSet的优点

  1. 有序性：

    • TreeSet是基于红黑树实现的有序集合，可以保持元素的顺序排列。这使得在遍历、查询范围或搜索最小/最大元素时更高效。

  2. 唯一性：

    • TreeSet中不允许重复元素存在，确保所有元素都是唯一的。如果有出现重复，默认覆盖

  3. 可导航性：

    • 作为NavigableSet接口的实现类，TreeSet提供了很多导航集操作。例如，获取子集、查找最接近给定元素的元素等。

  4. 基于比较器的排序：

    • 可以根据自然顺序或指定的比较器对元素进行排序，使得TreeSet能够适应不同的排序需求。

六、TreeSet的缺点

  1. 内存占用：

    • 由于TreeSet是基于红黑树实现的，每个节点都需要额外的空间来存储左右子节点和颜色信息，可能会占用较多的内存空间。

  2. 不支持并发：

    • TreeSet不是线程安全的，如果在多线程环境下同时修改TreeSet，可能会导致不确定的结果。需要显式地使用诸如Collections.synchronizedSortedSet()等方法来使其支持并发操作。

  3. 要求元素可比较：

    • 在默认情况下，TreeSet要求插入的元素必须实现Comparable接口，或者在构造函数中提供比较器。这限制了不能直接存储不可比较的对象。

七、HashSet和TreeSet的总结

相同点

  1. 不允许重复元素：

    • 无论是 HashSet 还是 TreeSet，它们都不允许集合中存在重复的元素，确保了集合中的元素唯一性。

  2. 都不是线程安全的：

    • HashSet 和 TreeSet 都不是线程安全的，如果在多线程环境下使用，需要额外考虑线程安全性。

不同点

  1. 底层数据结构不同：

    • HashSet 使用哈希表来存储元素，具有 O(1) 的平均时间复杂度；而 TreeSet 基于红黑树实现，具有 O(log n) 的时间复杂度。

  2. 元素排序方式不同：

    • HashSet 不维护元素的顺序，元素在集合中是无序存放的；而 TreeSet 根据元素的自然顺序或指定的比较器维护元素的有序性。

原文地址：https://blog.csdn.net/weixin_44716935/article/details/136799351

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024