转载

Java常用数据结构之Set之TreeSet

上篇文章我们分析了HashSet，它是基于HashMap实现的，那TreeSet会是怎么实现的呢？没错！和大家想的一样，它是基于 TreeMap 实现的。所以，TreeSet的源码也很简单，主要还是理解TreeMap。

TreeSet的继承关系

按照惯例，先来看TreeSet类的继承关系：

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

毫不意外的继承了抽象类AbstracSet，方便扩展；
实现了一个NavigableSet接口，和NavigableMap接口类似，提供了各种导航方法；
实现了Cloneable接口，可以克隆；
实现了Serializable接口，可以序列化；

这里主要看NavigableSet接口类：

public interface NavigableSet<E> extends SortedSet<E>
复制代码

熟悉的味道，继承SortedSet接口。SortedSet则提供了一个返回比较器的方法：

Comparator<? super E> comparator();
复制代码

和SortedMap一样，支持 自然排序 和 自定义排序 。自然排序要求添加到Set中的元素实现Comparable接口，自定义排序要求实现一个Comparator比较器。

源码分析

关键点

关键点自然是TreeSet如何保证元素不重复以及元素有序的，前面说了它是基于TreeMap实现的，那我们来看看吧。

private transient NavigableMap<E,Object> m; // 保证有序

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object(); // 固定Value
复制代码

纵观TreeSet源码，发现只有这两个属性（还有个uid，这里就不算了）。很明显， m 是用来保存元素的，但 m 声明的是 NavigableMap 而不是 TreeMap 。可以猜测， TreeMap 应该是在构造方法里实例化的，这里使用 NavigableMap 可以让TreeSet更加灵活。 PRESENT 和HashSet中的 PRESENT 作用一样，作为固定Value值进行占位的。

再看 add 和 remove 方法：

public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
    
public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }
复制代码

和HashSet的实现一样，也是利用了Map保存的Key-Value键值对的Key不会重复的特点。

构造函数

果然，TreeSet中的TreeMap是在构造函数中初始化的。

public TreeSet() {
        this(new TreeMap<>()); // 默认自然排序的TreeMap
    }

public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator)); // 自定义比较器的TreeMap
    }
    
public TreeSet(Collection<? extends E> c) {
        this(); // 还是用的默认
        addAll(c); // 将元素一个一个添加到TreeMap中
    }
 
 public TreeSet(SortedSet<E> s) {
        this(s.comparator()); // 使用传入的SortedSet的比较器
        addAll(s); // 一个一个添加元素
    }   
复制代码

默认实例化了一个自然排序的TreeMap，当然，我们可以自定义比较器。

这里跟踪下 addAll 方法：

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) {
            SortedSet<? extends E> set = (SortedSet<? extends E>) c;
            TreeMap<E,Object> map = (TreeMap<E, Object>) m; // 强转成TreeMap
            Comparator<?> cc = set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) { // 要保证set和map的比较器一样
                map.addAllForTreeSet(set, PRESENT); // TreeMap专门为TreeSet准备的方法
                return true;
            }
        }
        return super.addAll(c);
    }
复制代码

调用了TreeMap的 addAllForTreeSet 方法：

void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
        try {
            buildFromSorted(set.size(), set.iterator(), null, defaultVal);
        } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
        }
    }
复制代码

看到 buildFromSorted ，应该很熟悉，在TreeMap的文章中分析过。该方法将传入的集合元素构造成了一棵最底层的结点为红色，而其他结点都是黑色的红黑树。

导航方法

既然实现了 NavigableSet ，那各种导航方法自然少不了。它们的实现也很简单，直接调用 m 对应的导航方法即可。例如：

public E first() {
        return m.firstKey(); // 返回第一个元素
    }
    
public E lower(E e) {
        return m.lowerKey(e); // 返回小于e的第一个元素
    }
    
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<>(m.headMap(toElement, inclusive)); // 取前几个元素构成子集
    }
    
public E pollFirst() { // 弹出第一个元素
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();
    }

public NavigableSet<E> descendingSet() { // 倒排Set
        return new TreeSet<>(m.descendingMap());
    }

......
复制代码

这里需要注意的是返回子集合的方法，例如： headSet 。返回的子集合是可以添加和删除元素的，但是有 边界限制 ，举个栗子。

// 前面构造了一个存储Int的Set
        // 3、5、7、9
        SortedSet<Integer> subSet = intSet.headSet(8); // 最大值7，超过7越界
        for (Integer sub : subSet) {
            System.out.println(sub);
        }

        subSet.add(2);
//        subSet.add(8); // 越界了
        subSet.remove(3);
        for (Integer sub : subSet) {
            System.out.println(sub);
        }
复制代码

TreeSet也是支持逆序输出的，因为有 descendingIterator 的实现：

public Iterator<E> descendingIterator() {
        return m.descendingKeySet().iterator();
    }
复制代码

原文 https://juejin.im/post/5bfb6d8ff265da610e7fc2da

正文到此结束

所属分类： Java 编程技术

本文标签： UI build HashMap map final id cat value Collection key IO tk https 实例文章 HashSet git App ACE zab 源码 CEO 删除构造方法 java 代码 http equals
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

Java常用数据结构之Set之TreeSet

TreeSet的继承关系

源码分析

关键点

构造函数

导航方法

热门推荐

相关文章

说给你听

本文目录

随机标签

书籍教程

近期评论

网站信息

其他链接

关于本站

问题交流