TreeSet 源码分析

TreeSet 源码分析-TreeMap 复用

TreeSet 大致的结构和 HashSet 相似，底层组合的是 TreeMap，所以继承了 TreeMap key 能够排序的功能，迭代的时候，也可以按照 key 的排序顺序进行迭代。

TreeSet 的 add 方法源码：

public boolean add(E e) {    return m.put(e, PRESENT)==null;}

可以看到，底层直接使用的是 HashMap 的 put 方法。

迭代 TreeSet 中的元素的源代码：

public Iterator<E> descendingIterator() {    return m.keySet().iterator();}

迭代 TreeSet 中的元素，那应该也是像 add 那样，直接使用 HashMap 已有的迭代能力

这种是思路一的实现方式，TreeSet 组合 TreeMap，直接选择 TreeMap 的底层能力进行包装，但 TreeSet 实际执行的思路却完全相反，我们看源码：

public interface NavigableSet<E> extends SortedSet<E> {    Iterator<E> iterator();    E lower(E e);}  

NavigableSet 接口定义了迭代的一些规范，和一些取值的特殊方法。TreeSet 实现了该方法表示 TreeSet 本身已经定义了迭代的规范

public Iterator<E> iterator() {    return m.navigableKeySet().iterator();}

TreeSet 中定义了接口的规范，而 TreeMap 负责去实现。

TreeSet 排序

TreeSet 中有自然排序和比较器排序两种，其中：

1. 自然排序：TreeSet 的 add()方法会把存储的对象转型为 Comparable 类型，然后调用对象的 compareTo()方法和集合中的对象比较。根据 compareTo()方法返回的结果进行存储。

2. 比较器排序：创建 TreeSet 的时候指定 Comparator，如果传入了 Comparator 的子类实现对象,TreeSet 内部就会自动调用 compare()方法排序。

添加元素

    public  boolean addAll(Collection<? extends E> c) {        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();            if (cc==mc || (cc != null && cc.equals(mc))) {                map.addAllForTreeSet(set, PRESENT);                return true;            }        }        return super.addAll(c);    }

if (m.size()==0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) 判断当前集合有没有元素且当前集合是否属于 TreeSet、插入的集合是否属于 SortedSet 集合

SortedSet<? extends E> set = (SortedSet<? extends E>) c; 定义一个 SortedSet 类型的变量 set，将集合 c 进行强制类型转换

TreeMap<E,Object> map = (TreeMap<E, Object>) m; 定义一个 TreeMap 类型的变量 map，将集合 m 进行强制类型转换

Comparator<?> cc = set.comparator(); Comparator<? super E> mc = map.comparator();定义两个 Comparator 类型的变量，分别将 c 和 m 的构造器存储到这两个变量中

if (cc==mc || (cc != null && cc.equals(mc)))判断两个构造器地址是否相等

return super.addAll(c); 调用父类的 addAll 方法

总结

TreeSet 组合 TreeMap 实现的两种思路：

1. TreeSet 直接使用 TreeMap 的某些功能，包装成新的 api。

2. TreeSet 定义自己的 api 和接口规范，而让 TreeMap 去实现。