内容简介:上篇文章我们分析了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 复制代码
- 毫不意外的继承了抽象类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(); } 复制代码
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Understanding Machine Learning
Shai Shalev-Shwartz、Shai Ben-David / Cambridge University Press / 2014 / USD 48.51
Machine learning is one of the fastest growing areas of computer science, with far-reaching applications. The aim of this textbook is to introduce machine learning, and the algorithmic paradigms it of......一起来看看 《Understanding Machine Learning》 这本书的介绍吧!