TreeSet实现原理及源码分析

红太狼 2022-06-11 06:50 237阅读 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 条评论，237人围观）

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

相关阅读

相关 TreeSet源码分析

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

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

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

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

偏执的太偏执、/ 2022年06月15日 01:10/ 0 赞/ 264 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[HashMap实现原理及源码分析][HashMap] 　　哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memca

柔光的暖阳◎/ 2022年03月08日 14:50/ 0 赞/ 270 阅读

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

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

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

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

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

傷城~/ 2021年09月26日 04:26/ 0 赞/ 466 阅读