TreeSet实现原理及源码分析

红太狼 2022-06-11 06:50 259阅读 0赞

类似于HashMap和HashSet之间的关系，HashSet底层依赖于HashMap实现，TreeSet底层则采用一个NavigableMap来保存TreeSet集合的元素。但实际上，由于NavigableMap只是一个接口，`因此底层依然是使用TreeMap来包含Set集合中的所有元素`。

下面是TreeSet类的部分源代码

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable { 
    
        // 使用NavigableMap的key来保存Set集合的元素
        private transient NavigableMap<E,Object> m;
        // 使用一个PRESENT作为Map集合的所有value
        private static final Object PRESENT = new Object();
    
        // 包访问权限的构造器，以指定的NavigableMap对象创建Set集合
        TreeSet(NavigableMap<E,Object> m) {
            this.m = m;马士兵
        }
    
    
        public TreeSet() {                                  // ①
            // 以自然顺序方式创建一个新的TreeMap,根据该TreeSet创建一个TreeSet
        this(new TreeMap<E,Object>());
        }
    
        public TreeSet(Comparator<? super E> comparator) {  // ②
            // 以定制顺序方式创建一个新的TreeMap,根据该TreeSet创建一个TreeSet
        // 使用该TreeMap的key来保存Set集合的元素
        this(new TreeMap<E,Object>(comparator));
        }
    
        public TreeSet(Collection<? extends E> c) {
            // 调用①号构造器创建一个TreeSet，底层以TreeMap保存集合元素
            this();
        // 向TreeSet中添加Collection集合c里的所有元素
            addAll(c);
        }
    
        public TreeSet(SortedSet<E> s) {
            // 调用②号构造器创建衣蛾TreeSet，底层以TreeMap保存集合元素
            this(s.comparator());
        // 向TreeSet中添加SortedSet集合s里的所有元素
        addAll(s);
        }
    
        public  boolean addAll(Collection<? extends E> c) {
            // Use linear-time version if applicable
            if (m.size()==0 && c.size() > 0 &&
            c instanceof SortedSet &&
                m instanceof TreeMap) {
            // 把c集合强制转换为SortedSet集合
                SortedSet<? extends E> set = (SortedSet<? extends E>) c;
            // 把m集合强制转换为TreeMap集合
                TreeMap<E,Object> map = (TreeMap<E, Object>) m;
                Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
                Comparator<? super E> mc = map.comparator();
                // 如果cc和mc两个Comparator相等
                if (cc==mc || (cc != null && cc.equals(mc))) {
                // 把Collection中所有元素添加成TreeMap集合的key
                    map.addAllForTreeSet(set, PRESENT);
                    return true;
                }
            }
        // 直接调用父类的addAll()方法来实现
            return super.addAll(c);
        }
    }

从上面代码可以看出，TreeSet的①号、②号构造器都是新建一个TreeMap作为实际存储Set元素的容器，而另外2个构造器则分别依赖于①号和②号构造器。由此可见，TreeSet底层实际使用的存储容器就是TreeMap。

与HashSet完全类似的是，TreeSet里绝大部分方法都是直接调用TreeMap的方法来实现的。

发表评论取消回复

表情：

评论列表（有 0 条评论，259人围观）

还没有评论，来说两句吧...

相关阅读

相关 TreeSet源码分析

阅读本文章之前推荐先阅读博主的关于HashSet和TreeMap的源码分析，传送地址： [HashSet源码分析，基于JDK1.8详细分析][HashSet_JDK1.8]

刺骨的言语ヽ痛彻心扉/ 2023年01月19日 03:13/ 0 赞/ 186 阅读

相关 HashMap实现原理及源码分析

当我们执行如下操作时： HashMap<String, Float> map = new HashMap<String, Float>(); map.put(

小鱼儿/ 2022年06月12日 12:08/ 0 赞/ 304 阅读

相关 TreeSet实现原理及源码分析

类似于HashMap和HashSet之间的关系，HashSet底层依赖于HashMap实现，TreeSet底层则采用一个NavigableMap来保存TreeSet集合的元素。

红太狼/ 2022年06月11日 06:50/ 0 赞/ 260 阅读

相关 TreeMap实现原理及源码分析

TreeMap是一个有序的key-value集合，基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序，或者根据创建时提供的Comparator进行

墨蓝/ 2022年06月11日 02:00/ 0 赞/ 208 阅读

相关 HashSet实现原理及源码分析

HashSet简介 HashSet是Set接口实现，它按照Hash算法来存储集合中的元素不保证元素顺序 HashSet是非同步的，如果多个线程同时访问一个

今天药忘吃喽~/ 2022年06月11日 01:58/ 0 赞/ 252 阅读

相关 WeakHashMap实现原理及源码分析

和HashMap一样，WeakHashMap 也是一个散列表，它存储的内容也是键值对(key-value)映射，而且键和值都可以是null。不过WeakHashMap的键是“弱

布满荆棘的人生/ 2022年06月09日 05:16/ 0 赞/ 267 阅读

相关 ConcurrentHashMap实现原理及源码分析

ConcurrentHashMap是Java并发包中提供的一个线程安全且高效的HashMap实现（若对HashMap的实现原理还不甚了解，可参考我的另一篇文章<HashMap实

谁践踏了优雅/ 2022年05月25日 22:21/ 0 赞/ 314 阅读

相关 ConcurrentHashMap实现原理及源码分析

原作：[https://www.cnblogs.com/chengxiao/p/6842045.html][https_www.cnblogs.com_chengxiao_p_

不念不忘少年蓝@/ 2022年05月22日 11:34/ 0 赞/ 296 阅读

相关 HashMap实现原理及源码分析

哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈

我会带着你远行/ 2022年03月07日 05:18/ 0 赞/ 345 阅读

相关 ConcurrentHashMap实现原理及源码分析

原文链接：https://www.cnblogs.com/chengxiao/p/6842045.html 转载于:https://www.cnblogs.com/Wbin0

超、凢脫俗/ 2021年11月17日 08:22/ 0 赞/ 426 阅读