자바 개선 장(28) ------TreeSet

HashSet이 HashMap을 기반으로 구현된 것처럼 TreeSet도 TreeMap을 기반으로 구현됩니다. "Java 개선 장(27) -----TreeMap"에서 LZ는 TreeMap의 구현 메커니즘을 자세히 설명했습니다. 이 블로그 게시물을 자세히 읽었거나 TreeMap에 대해 더 자세히 이해했다면 TreeSet의 구현은 다음과 같습니다. 그것은 당신에게 물을 마시는 것만큼 간단합니다.

1. TreeSet 정의

우리는 TreeMap이 정렬된 이진 트리라는 것을 알고 있으므로 마찬가지로 TreeSet도 정렬되어 있으며 그 기능은 정렬된 Set 컬렉션을 제공하는 것입니다. 소스 코드를 통해 우리는 TreeSet이 NavigableSet, Cloneable 및 Serialized 인터페이스를 구현하는 AbstractSet을 기반으로 한다는 것을 알고 있습니다. 그중 AbstractSet은 Set 인터페이스의 백본 구현을 제공하므로 이 인터페이스를 구현하는 데 필요한 작업을 최소화합니다. NavigableSet은 주어진 검색 대상과 가장 가까운 일치 항목을 보고하는 탐색 방법을 갖춘 SortedSet의 확장입니다. 즉, 다양한 탐색 방법을 지원합니다. 예를 들어 지정된 대상과 가장 일치하는 항목을 찾습니다. Cloneable은 복제를 지원하고 Serialized는 직렬화를 지원합니다.

public class TreeSet<E> extends AbstractSet<E>    implements NavigableSet<E>, Cloneable, java.io.Serializable

동시에 TreeSet에는 다음과 같은 변수가 정의되어 있습니다.

private transient NavigableMap<E,Object> m;        
//PRESENT会被当做Map的value与key构建成键值对
 private static final Object PRESENT = new Object();

구성 방식 :

//默认构造方法，根据其元素的自然顺序进行排序
    public TreeSet() {        this(new TreeMap<E,Object>());
    }    
    //构造一个包含指定 collection 元素的新 TreeSet，它按照其元素的自然顺序进行排序。
    public TreeSet(Comparator<? super E> comparator) {            this(new TreeMap<>(comparator));
    }    
    //构造一个新的空 TreeSet，它根据指定比较器进行排序。
    public TreeSet(Collection<? extends E> c) {        this();
        addAll(c);
    }    
    //构造一个与指定有序 set 具有相同映射关系和相同排序的新 TreeSet。
    public TreeSet(SortedSet<E> s) {        this(s.comparator());
        addAll(s);
    }
    
    TreeSet(NavigableMap<E,Object> m) {        this.m = m;
    }

2. TreeSet의 주요 메소드

1. add: 지정된 요소를 이 세트에 추가합니다(요소가 세트에 아직 없는 경우).

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

2. 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;
            Comparator<? super E> cc = (Comparator<? super E>) 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);
    }

3. ceiling: 주어진 요소보다 크거나 같은 가장 작은 요소를 반환합니다. 해당 요소가 없으면 null을 반환합니다.

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

clear: 이 세트의 모든 요소를 ​​제거합니다.

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

5. clone: ​​​​TreeSet 인스턴스의 얕은 복사본을 반환합니다. 얕은 사본입니다.

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;
    }

6. 비교기: 이 집합의 요소를 정렬하는 비교기를 반환합니다. 이 집합이 해당 요소의 자연 순서를 사용하는 경우 null을 반환합니다.

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

7. 포함: 이 세트에 지정된 요소가 포함되어 있으면 true를 반환합니다.

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

8、descendingIterator：返回在此 set 元素上按降序进行迭代的迭代器。

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

9、descendingSet：返回此 set 中所包含元素的逆序视图。

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

10、first：返回此 set 中当前第一个（最低）元素。

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

11、floor：返回此 set 中小于等于给定元素的最大元素；如果不存在这样的元素，则返回 null。

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

12、headSet：返回此 set 的部分视图，其元素严格小于 toElement。

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

13、higher：返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。

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

14、isEmpty：如果此 set 不包含任何元素，则返回 true。

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

15、iterator：返回在此 set 中的元素上按升序进行迭代的迭代器。

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

16、last：返回此 set 中当前最后一个（最高）元素。

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

17、lower：返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。

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

18、pollFirst：获取并移除第一个（最低）元素；如果此 set 为空，则返回 null。

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

19、pollLast：获取并移除最后一个（最高）元素；如果此 set 为空，则返回 null。

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

20、remove：将指定的元素从 set 中移除（如果该元素存在于此 set 中）。

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

21、size：返回 set 中的元素数（set 的容量）。

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

22、subSet：返回此 set 的部分视图

/**
     * 返回此 set 的部分视图，其元素范围从 fromElement 到 toElement。     */
     public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
             E toElement,   boolean toInclusive) {             return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                  toElement,   toInclusive));
     }     
     /**
      * 返回此 set 的部分视图，其元素从 fromElement（包括）到 toElement（不包括）。      */
     public SortedSet<E> subSet(E fromElement, E toElement) {         return subSet(fromElement, true, toElement, false);
     }

23、tailSet：返回此 set 的部分视图

/**
     * 返回此 set 的部分视图，其元素大于（或等于，如果 inclusive 为 true）fromElement。     */
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {        return new TreeSet<>(m.tailMap(fromElement, inclusive));
    }    
    /**
     * 返回此 set 的部分视图，其元素大于等于 fromElement。     */
    public SortedSet<E> tailSet(E fromElement) {        return tailSet(fromElement, true);
    }

三、最后

由于TreeSet是基于TreeMap实现的，所以如果我们对treeMap有了一定的了解，对TreeSet那是小菜一碟，我们从TreeSet中的源码可以看出，其实现过程非常简单，几乎所有的方法实现全部都是基于TreeMap的。

以上就是Java提高篇（二八）------TreeSet的内容，更多相关内容请关注PHP中文网（www.php.cn）！