Java常用数据结构之Set之TreeSet

栏目: 数据库 · 发布时间: 5年前

内容简介:上篇文章我们分析了HashSet,它是基于HashMap实现的,那TreeSet会是怎么实现的呢?没错!和大家想的一样,它是基于按照惯例,先来看TreeSet类的继承关系:这里主要看NavigableSet接口类:

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

TreeSet的继承关系

按照惯例,先来看TreeSet类的继承关系:

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
复制代码
  1. 毫不意外的继承了抽象类AbstracSet,方便扩展;
  2. 实现了一个NavigableSet接口,和NavigableMap接口类似,提供了各种导航方法;
  3. 实现了Cloneable接口,可以克隆;
  4. 实现了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值进行占位的。

再看 addremove 方法:

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();
    }
复制代码

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

CSS权威指南(第三版)

CSS权威指南(第三版)

[美] Eric A.Meyer / 侯妍、尹志忠 / 中国电力出版社 / 2007-10 / 58.00

你是否既想获得丰富复杂的网页样式,同时又想节省时间和精力?本书为你展示了如何遵循CSS最新规范(CSS2和CSS2.1)将层叠样式表的方方面面应用于实践。 通过本书提供的诸多示例,你将了解如何做到仅在一处建立样式表就能创建或修改整个网站的外观,以及如何得到HTML力不能及的更丰富的表现效果。 资深CSS专家Eric A.Meyer。利用他独有的睿智和丰富的经验对属性、标记、标记属性和实......一起来看看 《CSS权威指南(第三版)》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具