Comment implémenter TreeSet en Java ? (explication détaillée)

Le contenu de cet article explique comment implémenter TreeSet en Java ? (Explication détaillée) a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. J'espère que cela vous sera utile.

HashSet est implémenté sur la base de HashMap, alors comment TreeSet est-il implémenté ? C'est exact! Comme tout le monde le pense, il est implémenté sur la base de TreeMap. Par conséquent, le code source de TreeSet est également très simple. L'essentiel est de comprendre TreeMap.

Relation d'héritage de TreeSet

Comme d'habitude, regardons d'abord la relation d'héritage de la classe TreeSet :

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

1. Sans surprise, il hérite de la classe abstraite AbstracSet pour une expansion facile

2. implémente une interface NavigableSet, similaire à l'interface NavigableMap ; et fournit diverses méthodes de navigation A

3. implémente l'interface Cloneable et peut être clonée

4. implémente l'interface Serialisable et peut être sérialisée ; 🎜>

Ici, nous examinons principalement la classe d'interface NavigableSet :

public interface NavigableSet<E> extends SortedSet<E>

Saveur familière , héritant de l'interface SortedSet. SortedSet fournit une méthode qui renvoie un comparateur :

Comparator<? super E> comparator();

, comme SortedMap, prend en charge le

tri naturel et le tri personnalisé. Le tri naturel nécessite que les éléments ajoutés au Set implémentent l'interface Comparable, et le tri personnalisé nécessite l'implémentation d'un Comparator.

Analyse du code source

Point clé

Le point clé est naturellement la façon dont TreeSet garantit que les éléments ne sont pas répétés et que les éléments sont ordonnés comme. mentionné plus tôt, il est basé sur TreeMap qui l'implémente, alors jetons un coup d'œil.

private transient NavigableMap<E,Object> m; // 保证有序
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object(); // 固定Value

En regardant le code source de TreeSet, nous avons constaté qu'il n'y avait que ces deux attributs (il y a aussi un uid, qui n'est pas compté ici) . Évidemment, m est utilisé pour sauvegarder des éléments, mais m déclare NavigableMap au lieu de TreeMap. On peut deviner que TreeMap devrait être instancié dans la méthode de construction. L'utilisation de NavigableMap ici peut rendre TreeSet plus flexible. PRESENT a la même fonction que PRESENT dans HashSet, il sert d'espace réservé pour une valeur Value fixe.

Regardez les méthodes d'ajout et de suppression :

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

La même chose que l'implémentation de HashSet, elle utilise également la valeur-clé Key-Value les paires enregistrées par Map Key ne seront pas répétées.

Constructeur

Effectivement, le TreeMap dans TreeSet est initialisé dans le constructeur.

public TreeSet() {
        this(new TreeMap<>()); // 默认自然排序的TreeMap
    }
public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator)); // 自定义比较器的TreeMap
    }
public TreeSet(Collection<? extends E> c) {
        this(); // 还是用的默认
        addAll(c); // 将元素一个一个添加到TreeMap中
    }
 public TreeSet(SortedSet<E> s) {
        this(s.comparator()); // 使用传入的SortedSet的比较器
        addAll(s); // 一个一个添加元素
    }

Un TreeMap naturellement ordonné est instancié par défaut. Bien entendu, nous pouvons personnaliser le comparateur.

Tracez la méthode addAll ici :

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; // 强转成TreeMap
            Comparator<?> cc = set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) { // 要保证set和map的比较器一样
                map.addAllForTreeSet(set, PRESENT); // TreeMap专门为TreeSet准备的方法
                return true;
            }
        }
        return super.addAll(c);
    }

La méthode

de TreeMap est appelée : addAllForTreeSet

void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
        try {
            buildFromSorted(set.size(), set.iterator(), null, defaultVal);
        } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
        }
    }

Vous devriez être familier avec buildFromSorted tel qu'il a été analysé dans l'article TreeMap. Cette méthode construit les éléments d'ensemble transmis dans un arbre rouge-noir dans lequel le nœud inférieur est rouge et les autres nœuds sont noirs.

Méthodes de navigation

Depuis que NavigableSet est implémenté, diverses méthodes de navigation sont naturellement indispensables. Leur mise en œuvre est également très simple, il suffit d’appeler directement la méthode de navigation correspondant à m. Par exemple :

public E first() {
        return m.firstKey(); // 返回第一个元素
    }
public E lower(E e) {
        return m.lowerKey(e); // 返回小于e的第一个元素
    }
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<>(m.headMap(toElement, inclusive)); // 取前几个元素构成子集
    }
public E pollFirst() { // 弹出第一个元素
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();
    }
public NavigableSet<E> descendingSet() { // 倒排Set
        return new TreeSet<>(m.descendingMap());
    }
......

Ce qu'il faut noter ici, c'est la méthode qui renvoie un sous-ensemble, par exemple : headSet. La sous-collection renvoyée peut ajouter et supprimer des éléments, mais il existe des restrictions de limites, par exemple.

        // 前面构造了一个存储Int的Set
        // 3、5、7、9
        SortedSet<Integer> subSet = intSet.headSet(8); // 最大值7，超过7越界
        for (Integer sub : subSet) {
            System.out.println(sub);
        }
        subSet.add(2);
//        subSet.add(8); // 越界了
        subSet.remove(3);
        for (Integer sub : subSet) {
            System.out.println(sub);
        }

TreeSet prend également en charge la sortie dans l'ordre inverse, car il existe une implémentation de

 : descendingIterator

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

Résumé

1. TreeSet est implémenté sur la base de TreeMap, prend en charge le tri naturel et le tri personnalisé et peut produire dans l'ordre inverse ; 🎜>

TreeSet n'autorise pas les valeurs nulles ;
TreeSet n'est pas thread-safe SortedSet s = Collections.synchronizedSortedSet(new TreeSet(.. . ));

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!