Chapitre d'amélioration Java (28) ------TreeSet

Tout comme HashSet est implémenté sur la base de HashMap, TreeSet est également implémenté sur la base de TreeMap. Dans "Java Improvement Chapter (27) -----TreeMap", LZ a expliqué en détail le mécanisme d'implémentation de TreeMap. Si vous avez lu cet article de blog en détail ou si vous avez une compréhension plus détaillée de TreeMap, alors l'implémentation de TreeSet est. utile pour vous. C'est aussi simple que de boire de l'eau.

1. Définition de TreeSet

Nous savons que TreeMap est un arbre binaire ordonné, donc de la même manière, TreeSet est également ordonné, et sa fonction est de fournir une collection Set ordonnée. Grâce au code source, nous savons que TreeSet est basé sur AbstractSet, qui implémente les interfaces NavigableSet, Cloneable et Serialisable. Parmi eux, AbstractSet fournit l'implémentation principale de l'interface Set, minimisant ainsi le travail requis pour implémenter cette interface. NavigableSet est une extension de SortedSet avec des méthodes de navigation qui signalent la correspondance la plus proche pour une cible de recherche donnée, ce qui signifie qu'elle prend en charge une gamme de méthodes de navigation. Par exemple, recherchez la meilleure correspondance pour une cible spécifiée. Cloneable prend en charge le clonage et Serialised prend en charge la sérialisation.

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

En même temps, les variables suivantes sont définies dans TreeSet.

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

Sa méthode de construction :

//默认构造方法，根据其元素的自然顺序进行排序
    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 Main Méthodes

1, add : Ajouter l'élément spécifié à cet ensemble (si l'élément n'existe pas déjà dans l'ensemble).

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

2 addAll : ajoutez tous les éléments de la collection spécifiée à cet ensemble.

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. plafond : renvoie le plus petit élément de cet ensemble qui est supérieur ou égal à l'élément donné si ; il n'existe pas un tel élément, renvoie null.

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

4. effacer : Supprimez tous les éléments de cet ensemble.

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

5. clone : ​​​​Renvoie une copie superficielle de l'instance TreeSet. C'est une copie superficielle.

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. comparateur : renvoie le comparateur qui trie les éléments de cet ensemble ; si cet ensemble utilise l'ordre naturel de ses éléments, renvoie null.

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

7. contient : Si cet ensemble contient l'élément spécifié, renvoie vrai.

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）！