目录

  • 一.前言
  • 二.剥析流程
    • 2.1 类图
    • 2.2 属性
    • 2.3 构造方法
    • 2.4 添加单个元素
    • 2.5 移除单个元素
    • 2.6 查找单个元素
    • 2.7 查找接近的元素
    • 2.8 获得首尾的元素
    • 2.9 清空
    • 2.10 克隆
    • 2.11 序列化
    • 2.12 反序列化
    • 2.13 获得迭代器
    • 2.14 转换成 Set/Collection
    • 2.15 查找范围的元素
  • 三.总结

一.前言

TreeSet是基于红黑树实现的Set集合，它具有以下特点：

  1. 有序性：TreeSet是有序的，它按照元素的自然排序进行排序，或者按照指定的Comparator进行排序。

  2. 不允许重复元素：与HashSet一样，TreeSet也不允许重复元素，如果试图将一个已经存在的元素添加到TreeSet中，那么添加操作将会被忽略。

  3. 支持高效的插入、删除、查找操作：由于TreeSet是基于红黑树实现的，因此它的插入、删除、查找等操作的时间复杂度为O(logn)，具有良好的时间性能。

  4. 不支持随机访问：由于TreeSet是基于红黑树实现的，因此它不支持随机访问，不能通过下标来访问集合中的元素。如果需要随机访问集合中的元素，可以使用ArrayList或LinkedList等数据结构。

  5. 线程不安全：TreeSet是非线程安全的，如果多个线程同时操作同一个TreeSet对象，可能会导致集合数据结构被破坏，因此在多线程环境下需要考虑对TreeSet进行同步操作。

总之，TreeSet是一个有序、不允许重复元素、支持高效插入、删除、查找操作的集合，适合需要按照一定顺序访问元素的场景。

二.剥析流程

2.1 类图

TreeSet 实现的接口、继承的类，如下图所示：类图

  • 实现 java.util.NavigableSet 接口，并继承 java.util.AbstractSet 抽像类。
  • 实现 java.io.Serializable 接口。
  • 实现 java.lang.Cloneable 接口。

2.2 属性

TreeSet 只有一个属性，那就是 m 。代码如下：

private transient NavigableMap<E,Object> m;

  • m 的 key ，存储 HashSet 的每个 key 。

  • map 的 value ，因为 TreeSet 没有 value 的需要，所以使用一个统一的 PRESENT 即可。代码如下：

    // Dummy value to associate with an Object in the backing Mapprivate static final Object PRESENT = new Object();

2.3 构造方法

TreeSet 一共有 5 个构造方法，代码如下：

TreeSet(NavigableMap<E,Object> m) {this.m = m;}public TreeSet() {this(new TreeMap<>());}public TreeSet(Comparator<" />super E> comparator) {this(new TreeMap<>(comparator));}public TreeSet(Collection<? extends E> c) {this();// 批量添加addAll(c);}public TreeSet(SortedSet<E> s) {this(s.comparator());// 批量添加addAll(s);}
  • 在构造方法中，会创建 TreeMap 对象，赋予到 m 属性。

2.4 添加单个元素

add(E e) 方法，添加单个元素。代码如下：

public boolean add(E e) {return m.put(e, PRESENT)==null;}
  • m 的 value 值，就是我们看到的 PRESENT 。

addAll(Collection c) 方法，批量添加。代码如下：

publicboolean 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;if (Objects.equals(set.comparator(), map.comparator())) {map.addAllForTreeSet(set, PRESENT);return true;}}// 情况二return super.addAll(c);}
  • 在实现上，和 TreeMap 的批量添加是一样的，对于情况一，会进行优化。

2.5 移除单个元素

remove(Object o) 方法，移除 o 对应的 value ，并返回是否成功。代码如下：

public boolean remove(Object o) {return m.remove(o)==PRESENT;}

2.6 查找单个元素

#contains(Object key) 方法，判断 key 是否存在。代码如下：

public boolean contains(Object o) {return m.containsKey(o);}

2.7 查找接近的元素

在 NavigableSet 中，定义了四个查找接近的元素：

  • #lower(E e) 方法，小于 e 的 key
  • #floor(E e) 方法，小于等于 e 的 key
  • #higher(E e) 方法，大于 e 的 key
  • #ceiling(E e) 方法，大于等于 e 的 key

我们一起来看看哈。

// TreeSet.javapublic E lower(E e) {return m.lowerKey(e);}public E floor(E e) {return m.floorKey(e);}public E ceiling(E e) {return m.ceilingKey(e);}public E higher(E e) {return m.higherKey(e);}

2.8 获得首尾的元素

first() 方法，获得首个 key 。代码如下：

public E first() {return m.firstKey();}

  • pollFirst() 方法，获得并移除首个 key 。代码如下：

    public E pollFirst() {Map.Entry<E,?> e = m.pollFirstEntry();return (e == null) ? null : e.getKey();}

last() 方法，获得尾部 key 。代码如下：

public E last() {return m.lastKey();}

  • pollLast() 方法，获得并移除尾部 key 。代码如下：

    public E pollLast() {Map.Entry<E,?> e = m.pollLastEntry();return (e == null) ? null : e.getKey();}

2.9 清空

clear() 方法，清空。代码如下：

public void clear() {m.clear();}

2.10 克隆

clone() 方法，克隆 TreeSet 。代码如下：

public Object clone() {// 克隆创建 TreeSet 对象TreeSet<E> clone;try {clone = (TreeSet<E>) super.clone();} catch (CloneNotSupportedException e) {throw new InternalError(e);}// 创建 TreeMap 对象，赋值给 clone 的 m 属性clone.m = new TreeMap<>(m);return clone;}

2.11 序列化

writeObject(ObjectOutputStream s) 方法，序列化 TreeSet 对象。代码如下：

@java.io.Serialprivate void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {// Write out any hidden stuff// 写入非静态属性、非 transient 属性s.defaultWriteObject();// Write out Comparator// 写入比较器s.writeObject(m.comparator());// Write out size// 写入 key-value 键值对数量s.writeInt(m.size());// Write out all elements in the proper order.// 写入具体的 key-value 键值对for (E e : m.keySet())s.writeObject(e);}

2.12 反序列化

#readObject(ObjectInputStream s) 方法，反序列化成 TreeSet 对象。代码如下：

// TreeSet.java@java.io.Serialprivate void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {// Read in any hidden stuff// 读取非静态属性、非 transient 属性s.defaultReadObject();// Read in Comparator// 读取比较器@SuppressWarnings("unchecked")Comparator c = (Comparator) s.readObject();// Create backing TreeMap// 创建 TreeMap 对象TreeMap tm = new TreeMap(c);m = tm;// Read in size// 读取 key-value 键值对数量int size = s.readInt();// 读取具体的 key-value 键值对tm.readTreeSet(size, s, PRESENT);}// TreeMap.javavoid readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)throws java.io.IOException, ClassNotFoundException {buildFromSorted(size, null, s, defaultVal);}

2.13 获得迭代器

// TreeSet.javapublic Iterator iterator() { // 正序 Iterator 迭代器return m.navigableKeySet().iterator();}public Iterator descendingIterator() { // 倒序 Iterator 迭代器return m.descendingKeySet().iterator();}

2.14 转换成 Set/Collection

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

2.15 查找范围的元素

// subSet 组public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,E toElement, boolean toInclusive) {return new TreeSet<>(m.subMap(fromElement, fromInclusive, toElement, toInclusive));}public SortedSet<E> subSet(E fromElement, E toElement) {return subSet(fromElement, true, toElement, false);}// headSet 组public NavigableSet<E> headSet(E toElement, boolean inclusive) {return new TreeSet<>(m.headMap(toElement, inclusive));}public SortedSet<E> headSet(E toElement) {return headSet(toElement, false);}// tailSet 组public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {return new TreeSet<>(m.tailMap(fromElement, inclusive));}public SortedSet<E> tailSet(E fromElement) {return tailSet(fromElement, true);}

三.总结

TreeSet 是基于 TreeMap 的 Set 实现类