Java集合（12）——TreeSet源码解析

类图

官方文档

Java集合（12）——TreeSet源码解析

TreeSet类实现了NavigableSet接口，因此它是有顺序的Set类，可以指定一个顺序，在元素存入时，按照指定的顺序排序
其中排序的顺序有两种方式：自然排序和比较器排序
自然排序
- TreeSet类的add()方法中会把存入的对象提升为Comparable类型
- 调用对象的compareTo()方法和集合中的对象比较
- 根据compareTo()方法返回的结果进行存储
比较器排序
- 创建TreeSet的时候可以制定一个Comparator
- 如果传入了Comparator的子类对象, 那么TreeSet就会按照比较器中的顺序排序
- add()方法内部会自动调用Comparator接口中compare()方法排序
- 调用的对象是compare方法的第一个参数,集合中的对象是compare方法的第二个参数
两种排序方法的选择
- TreeSet构造函数什么都不传, 默认按照类中Comparable的顺序(没有就报错ClassCastException)
- TreeSet如果传入Comparator, 就优先按照Comparator

成员变量

Java集合（12）——TreeSet源码解析

成员方法

Java集合（12）——TreeSet源码解析

成员方法源码解析

该类的很多方法都是通过调用NavigableMap类的对应方法实现的

1. `TreeSet(NavigableMap<E,Object> m)`方法

    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

源码解析：

功能：构造一个TreeSet集合，参数为NavigableMap类型的m

2. `public TreeSet()`方法

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

源码解析：

功能：构造一个新的，空的TreeSet集合。因为TreeSet是一个有序的集合，因此在向该集合中插入元素是按照自然顺序进行插入，且插入的元素所属的类型需要实现Comparable接口，并且所有的元素都是需要可比较的。如果TreeSet中已经存储的元素是整型，插入的下一个元素是字符串类型，那么此时会抛出ClassCastException异常

3. `public TreeSet(Comparator<? super E> comparator)`方法

    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }

源码解析：

功能：将比较器comparator载入到当前TreeSet集合中，如果comparator是null，那么就会按照自然排序顺序排序
源码思路：
- 实现该功能通过创建新的TreeMap实现，且将comparator传入TreeMap构造器

4. `public TreeSet(Collection<? extends E> c)`方法

    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }

源码解析：

功能：用现有的集合c中的元素来创建新的集合TreeSet
源码思路：
- (1) 首先调用当前类的this()构造函数
- (2) 其次调用addAll(c)方法，将集合c中的元素放入当前对象中

5. `public TreeSet(SortedSet<E> s)`方法

    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }

源码解析：
- 功能：构建一个新的TreeSet集合，其中集合s中的元素放在新创建的集合中，且新集合的比较方法与集合s的比较方法相同
- 源码思路：
- （1）首先调用当前集合的构造函数，将s集合的构造器作为参数传递给当前集合的构造器
- （2）其次调用addAll方法，将集合s的元素放入新集合中

6. `public Iterator<E> iterator()`方法

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

源码解析：

功能：返回当前集合的构造器
源码思路：
- 通过调用navigableKeySet的构造器作为当前集合的构造器，这个构造器是按照元素递增的方式

7. `public Iterator<E> descendingIterator()`方法

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

源码解析：

功能：返回当前集合的构造器
- 源码思路：
- 通过调用navigableKeySet的构造器作为当前集合的构造器，这个构造器是按照元素递减的方式

8. `public NavigableSet<E> descendingSet()`方法

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

9. `public int size(`方法

    public int size() {
        return m.size();
    }

源码解析：

功能：返回集合中元素的个数
源码思路：
- 通过调用m的size()方法获得集合中元素的个数

10. `public boolean isEmpty()`方法

    public boolean isEmpty() {
        return m.isEmpty();
    }

源码解析：

功能：判断集合是否为空

11. `public boolean contains(Object o)`方法

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

源码解析：

功能：判断集合中是否包含元素o
源码思路：
- 通过调用o的containsKey方法，来判断元素o是否在集合中

12. `public boolean add(E e)`方法

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

源码解析：

功能：将元素e插入到集合中
源码思路：
- 通过调用m的put方法，将e插入到集合，因为put是Map类的函数，因此不止有键还有值，但是Set只有值，所以讲Set值作为Map的键，将PRESENT作为所有Set的值

13. `public boolean remove(Object o)`方法

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

源码解析：

功能：从集合中删除元素o

14. `public void clear()`方法

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

15. `public boolean addAll(Collection<? extends E> c)`方法

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

源码解析：

功能：将集合c插入到当前集合中
源码思路：
- （1）如果当前集合没有元素，插入的集合有元素，且当前集合属于TreeSet，插入的集合属于SortedSet 集合，则进行下列操作，否则执行（6）
- （2）定义一个SortedSet类型的变量set，将集合c进行强制类型转换，转换的结果存储到变量set中
- （3）定义一个TreeMap类型的变量map，将集合m进行强制类型转换，转换的结果存储到变量map中
- （4）定义两个Comparator类型的变量，分别将c和m的构造器存储到这两个变量中
- （5）如果两个构造器地址相等，或者两个构造器地址不相等但是值相等，则调用map的addAllForTreeSet方法，将参数的值传入到新集合中，返回true
- （6）调用父类的addAll方法

16. `public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,E toElement, boolean toInclusive)`方法

    public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,E toElement,   boolean toInclusive) {    
        return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                       toElement,   toInclusive));
    }

源码解析：

功能：返回当前集合大于fromElement小于toElement的集合元素，其中fromInclusive是boolean，值为true，表示包含fromElement，为false表示不包含fromElement；toInclusive同理

17. `public NavigableSet<E> headSet(E toElement, boolean inclusive)`方法

    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<>(m.headMap(toElement, inclusive));
    }

源码解析：

功能：返回当前集合小于toElement的元素，inclusive为true，包含等于toElement的元素，为false，不包含等于toElement的元素
源码思路：调用m的headMap方法实现

18. `public NavigableSet<E> tailSet(E fromElement, boolean inclusive)`方法

    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
        return new TreeSet<>(m.tailMap(fromElement, inclusive));
    }

源码解析：

功能：返回当前集合大于toElement的元素，inclusive为true，包含等于toElement的元素，为false，不包含等于toElement的元素

19. `public SortedSet<E> subSet(E fromElement, E toElement)`方法

    public SortedSet<E> subSet(E fromElement, E toElement) {
        return subSet(fromElement, true, toElement, false);
    }

源码解析：

功能：返回当前集合中大于等于fromElement小于 toElement的元素
源码思路：
- 调用subSet方法，该方法一个四个参数，两个Boolean值确定了。

20. `public SortedSet<E> headSet(E toElement)`方法

    public SortedSet<E> headSet(E toElement) {
        return headSet(toElement, false);
    }

源码解析：

功能：返回当前集合中小于toElement的元素
源码思路：
- 调用headSet方法实现，将Boolean值设置为假，即不包含等于toElement的元素

21. `public SortedSet<E> tailSet(E fromElement)`方法

    public SortedSet<E> tailSet(E fromElement) {
        return tailSet(fromElement, true);
    }

源码解析：

功能：返回当前集合中大于等于fromElement的元素
源码思路：
- 调用tailSet方法实现，将Boolean值设置为假，即包含等于fromElement的元素

22. `public Comparator<? super E> comparator()`方法

    public Comparator<? super E> comparator() {
        return m.comparator();
    }

源码解析：

功能：返回比较器

23. `public E first()`方法

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

源码解析：

功能：返回集合中的第一个元素值
源码思路：
- 通过调用NevigatableMap类的firstKey实现

24. `public E last()`方法

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

源码解析：

功能：返回集合中的最后一个元素值
源码思路：
- 通过调用NevigatableMap类的lastKey实现

25. `public E lower(E e)`方法

    public E lower(E e) {
        return m.lowerKey(e);
    }

源码解析：

功能：返回集合中小于e的最近一个元素，如果没有比e小的元素，则返回null

26. `public E floor(E e)`方法

    public E floor(E e) {
        return m.floorKey(e);
    }

源码解析：

功能：返回集合中小于e的最近一个元素，如果没有比e小的元素，则返回null

27. `public E ceiling(E e)`方法

    public E ceiling(E e) {
        return m.ceilingKey(e);
    }

源码解析：

功能：返回集合中大于e的最近一个元素，如果没有比e大的元素，则返回null

28. `public E higher(E e)`方法

    public E higher(E e) {
        return m.higherKey(e);
    }

源码解析：

功能：返回集合中大于e的最近一个元素，如果没有比e大的元素，则返回null

29. `public E pollFirst()`方法

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

源码解析：

功能：返回集合的第一个元素信息
源码思路：
- 通过调用NevigatableMap的pollFirstEntry方法，返回第一个元素的实体信息，将其存入Map类的Entry的变量e中，然后返回e的getKey方法

30. `public E pollLast()`方法

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

源码解析：

功能：返回集合的最后一个元素信息

示例代码

public class TreeSetTest {
    public static void main(String[] args) {
        //4. public TreeSet(Collection<? extends E> c)方法
        Collection c = new HashSet();
        c.add(10);
        c.add(4);
        c.add(1);
        System.out.println(c); //输出：[1,4,10]
        TreeSet s = new TreeSet(c);
        System.out.println(s); //输出：[1,4,10]

        //5. public Iterator<E> iterator()方法
        Iterator iterator_ascending = s.iterator();
        while(iterator_ascending.hasNext()){
            System.out.print(iterator_ascending.next() + ",");  //输出：1,4,10,
        }
        System.out.println();

        //6. public Iterator<E> descendingIterator()方法
        Iterator iterator_descending = s.descendingIterator();
        while(iterator_descending.hasNext()) {
            System.out.print(iterator_descending.next() + ","); //输出：10,4,1,
        }
        System.out.println();

        // 16. public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,E toElement, boolean toInclusive) 
        TreeSet ts1 = new TreeSet();
        ts1 = (TreeSet) s.subSet(4, false, 10, true);
        System.out.println(ts1); //输出：[10]

        //17. public NavigableSet<E> headSet(E toElement, boolean inclusive)
        TreeSet ts2 = new TreeSet();
        ts2 = (TreeSet) s.headSet(4, true);
        System.out.println(ts2); //输出：[1,4]

        //18. public NavigableSet<E> tailSet(E fromElement, boolean inclusive)方法
        TreeSet ts3 = new TreeSet();
        s = new TreeSet(c);
        ts3 = (TreeSet) s.tailSet(3, true);
        System.out.println(ts3); //输出：[4,10]

        //23.public E first()方法
        s = new TreeSet(c);
        System.out.println(s.first());

        //25.public E lower(E e)
        TreeSet ts4 = new TreeSet();
        ts4 = new TreeSet(c);
        System.out.println("ts4.lower(9):" + ts4.lower(9)); //输出：4

        //26. public E floor(E e) 方法
        System.out.println("ts4.floor(6):" + ts4.floor(6)); //输出：4

        //27. public E ceiling(E e)方法
        System.out.println("ts4.ceiling(9)" + ts4.ceiling(9));//输出：10

        //28. public E higher(E e)方法
        System.out.println("ts4.higher(9)" + ts4.higher(9));//输出：10

    }
}

感谢

https://www.cnblogs.com/yzssoft/p/7127894.html

秒客网

Java集合（12）——TreeSet源码解析

类图

官方文档

成员变量

成员方法

成员方法源码解析

1. `TreeSet(NavigableMap<E,Object> m)`方法

2. `public TreeSet()`方法

3. `public TreeSet(Comparator<? super E> comparator)`方法

4. `public TreeSet(Collection<? extends E> c)`方法

5. `public TreeSet(SortedSet<E> s)`方法

6. `public Iterator<E> iterator()`方法

7. `public Iterator<E> descendingIterator()`方法

8. `public NavigableSet<E> descendingSet()`方法

9. `public int size(`方法

10. `public boolean isEmpty()`方法

11. `public boolean contains(Object o)`方法

12. `public boolean add(E e)`方法

13. `public boolean remove(Object o)`方法

14. `public void clear()`方法

15. `public boolean addAll(Collection<? extends E> c)`方法

16. `public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,E toElement, boolean toInclusive)`方法

17. `public NavigableSet<E> headSet(E toElement, boolean inclusive)`方法

18. `public NavigableSet<E> tailSet(E fromElement, boolean inclusive)`方法

19. `public SortedSet<E> subSet(E fromElement, E toElement)`方法

20. `public SortedSet<E> headSet(E toElement)`方法

21. `public SortedSet<E> tailSet(E fromElement)`方法

22. `public Comparator<? super E> comparator()`方法

23. `public E first()`方法

24. `public E last()`方法

25. `public E lower(E e)`方法

26. `public E floor(E e)`方法

27. `public E ceiling(E e)`方法

28. `public E higher(E e)`方法

29. `public E pollFirst()`方法

30. `public E pollLast()`方法

示例代码

感谢

相关文章

Java集合（12）——TreeSet源码解析

类图

官方文档

成员变量

成员方法

成员方法源码解析

1. TreeSet(NavigableMap<E,Object> m)方法

2. public TreeSet()方法

3. public TreeSet(Comparator<? super E> comparator)方法

4. public TreeSet(Collection<? extends E> c)方法

5. public TreeSet(SortedSet<E> s)方法

6. public Iterator<E> iterator()方法

7. public Iterator<E> descendingIterator()方法

8. public NavigableSet<E> descendingSet()方法

9. public int size(方法

10. public boolean isEmpty()方法

11. public boolean contains(Object o)方法

12. public boolean add(E e)方法

13. public boolean remove(Object o)方法

14. public void clear()方法

15. public boolean addAll(Collection<? extends E> c)方法

16. public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,E toElement, boolean toInclusive)方法

17. public NavigableSet<E> headSet(E toElement, boolean inclusive)方法

18. public NavigableSet<E> tailSet(E fromElement, boolean inclusive)方法

19. public SortedSet<E> subSet(E fromElement, E toElement)方法

20. public SortedSet<E> headSet(E toElement)方法

21. public SortedSet<E> tailSet(E fromElement)方法

22. public Comparator<? super E> comparator()方法

23. public E first()方法

24. public E last()方法

25. public E lower(E e)方法

26. public E floor(E e)方法

27. public E ceiling(E e)方法

28. public E higher(E e)方法

29. public E pollFirst()方法

30. public E pollLast()方法

示例代码

感谢

相关文章

1. `TreeSet(NavigableMap<E,Object> m)`方法

2. `public TreeSet()`方法

3. `public TreeSet(Comparator<? super E> comparator)`方法

4. `public TreeSet(Collection<? extends E> c)`方法

5. `public TreeSet(SortedSet<E> s)`方法

6. `public Iterator<E> iterator()`方法

7. `public Iterator<E> descendingIterator()`方法

8. `public NavigableSet<E> descendingSet()`方法

9. `public int size(`方法

10. `public boolean isEmpty()`方法

11. `public boolean contains(Object o)`方法

12. `public boolean add(E e)`方法

13. `public boolean remove(Object o)`方法

14. `public void clear()`方法

15. `public boolean addAll(Collection<? extends E> c)`方法

16. `public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,E toElement, boolean toInclusive)`方法

17. `public NavigableSet<E> headSet(E toElement, boolean inclusive)`方法

18. `public NavigableSet<E> tailSet(E fromElement, boolean inclusive)`方法

19. `public SortedSet<E> subSet(E fromElement, E toElement)`方法

20. `public SortedSet<E> headSet(E toElement)`方法

21. `public SortedSet<E> tailSet(E fromElement)`方法

22. `public Comparator<? super E> comparator()`方法

23. `public E first()`方法

24. `public E last()`方法

25. `public E lower(E e)`方法

26. `public E floor(E e)`方法

27. `public E ceiling(E e)`方法

28. `public E higher(E e)`方法

29. `public E pollFirst()`方法

30. `public E pollLast()`方法