1. TreeSet简介
TreeSet是Set的实现类之一,是不可重复集合,非线程安全的。
TreeSet是SortedSet的唯一实现类,实现了元素的自动排序,排序不是以插入的顺序排序,而是默认以元素的大小进行自动排序,也可以指定排序方式来按照定制排序。
TreeSet底层排序通过红黑树实现,红黑树是一种排序二叉树,具体介绍可参考:https://www.jianshu.com/p/69f11fc9ea38
2. TreeSet继承关系
TreeSet自AbstractSet,实现了NacigableSet、Cloneable、java.io.Serializable接口。
AbstractSet继承自AbstractCollection,实现了Set接口,此类并没有重写 AbstractCollection 类中的任何实现(包括add()方法)。它仅仅添加了 equals 和 hashCode 的实现。
NavigableSet扩展了 SortedSet,具有了为给定搜索目标报告最接近匹配项的导航方法。方法 lower、floor、ceiling 和 higher 分别返回小于、小于等于、大于等于、大于给定元素的元素,如果不存在这样的元素,则返回 null。
实现了Cloneable接口:可以调用Object.clone方法返回该对象的浅拷贝。
实现了 java.io.Serializable 接口:可以启用其序列化功能,能通过序列化去传输。
3. TreeSet实现
1. 核心属性
//底层通过Map存储数据 private transient NavigableMap<E,Object> m; //不可改变的空对象,用来作为底层map的value private static final Object PRESENT = new Object();
2. 构造函数
//只有同包类可访问,用来指定底层存储的map类型 TreeSet(NavigableMap<E,Object> m) { this.m = m; } //无参构造,默认以TreeMap进行数据存储 public TreeSet() { this(new TreeMap<E,Object>()); } //以TreeMap进行数据存储,传入一个比较器,用来定制排序 public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); } //以TreeMap进行数据存储,传入一个集合存储TreeMap public TreeSet(Collection<? extends E> c) { this(); addAll(c); } //传入一个SortedSet s,复用s的比较器,并把s内的元素全部添加进来 public TreeSet(SortedSet<E> s) { this(s.comparator()); addAll(s); }
3. 核心方法
//判断set是否为空 public boolean isEmpty() { return m.isEmpty(); } //判断set中是否包含元素o public boolean contains(Object o) { return m.containsKey(o); } //添加一个元素 public boolean add(E e) { //调用底层TreeMap的put方法,key存放元素e,value存入不可改变的空对象PRESENT //put方法保存成功会返回null,否则返回value值 return m.put(e, PRESENT)==null; } //将元素o从set中移除 public boolean remove(Object o) { return m.remove(o)==PRESENT; } //清空set public void clear() { m.clear(); } //添加一个集合 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; Comparator<?> cc = set.comparator(); Comparator<? super E> mc = map.comparator(); //当传入集合是SortedSet并且比较器和底层TreeMap的比较器一致时,直接调用TreeMap的添加函数addAllForTreeSet //否则通过迭代器遍历一次调用add方法进行添加 if (cc==mc || (cc != null && cc.equals(mc))) { map.addAllForTreeSet(set, PRESENT); return true; } } return super.addAll(c); } //返回一个子集合 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new TreeSet<>(m.subMap(fromElement, fromInclusive, toElement, toInclusive)); } //返回set的头部 public NavigableSet<E> headSet(E toElement, boolean inclusive) { return new TreeSet<>(m.headMap(toElement, inclusive)); } //返回set的尾部 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { return new TreeSet<>(m.tailMap(fromElement, inclusive)); } //返回一个子集合 public SortedSet<E> subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); } //返回m使用的比较器 public Comparator<? super E> comparator() { return m.comparator(); } //返回第一个元素 public E first() { return m.firstKey(); } //返回最后一个元素 public E last() { return m.lastKey(); } //返回set中小于e的最大的元素 public E lower(E e) { return m.lowerKey(e); } //返回set中小于/等于e的最大元素 public E floor(E e) { return m.floorKey(e); } //返回set中大于/等于e的最大元素 public E ceiling(E e) { return m.ceilingKey(e); } //返回set中大于e的最小元素 public E higher(E e) { return m.higherKey(e); } //获取TreeSet中第一个元素,并从Set中删除该元素 public E pollFirst() { Map.Entry<E,?> e = m.pollFirstEntry(); return (e == null) ? null : e.getKey(); } //获取TreeSet中最后一个元素,并从Set中删除该元素 public E pollLast() { Map.Entry<E,?> e = m.pollLastEntry(); return (e == null) ? null : e.getKey(); } //克隆方法 public Object clone() { TreeSet<E> clone = null; try { clone = (TreeSet<E>) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } clone.m = new TreeMap<>(m); return clone; } //将对象写入到输出流中。 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden stuff s.defaultWriteObject(); // Write out Comparator s.writeObject(m.comparator()); // Write out size s.writeInt(m.size()); // Write out all elements in the proper order. for (E e : m.keySet()) s.writeObject(e); } //从输入流中读取对象的信息 private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden stuff s.defaultReadObject(); // Read in Comparator Comparator<? super E> c = (Comparator<? super E>) s.readObject(); // Create backing TreeMap TreeMap<E,Object> tm; if (c==null) tm = new TreeMap<>(); else tm = new TreeMap<>(c); m = tm; // Read in size int size = s.readInt(); tm.readTreeSet(size, s, PRESENT); }