betacode

Руководство Java TreeSet

  1. TreeSet
  2. Как TreeSet хранит данные?
  3. Examples
  4. TreeSet с элементом null

1. TreeSet

В этой статье мы рассмотрим класс TreeSet, который является реализацией (implementation) интерфейса NavigableSet и находится в наборе связанных классов и интерфейсов Java (Java Collection Framework).
public class TreeSet<E> extends AbstractSet<E>
                    implements NavigableSet<E>, Cloneable, java.io.Serializable
В основном, в этой статье мы узнаем характеристики of TreeSet и то, как он хранит элементы. Вы должны изучить основые понятия о Set, прежде чем продолжить эту статью.
Характеристики of TreeSet:
Set<E>
SortedSet<E>
NavigableSet<E>
TreeSet<E>
Повторяющиеся элементы не допускаются. Если вы намеренно добавите повторяющийся элемент, это действие будет проигнорировано.
Допускается не более одного элемента null.
Допускается не более одного элемента null, и значение null допускается только в том случае, если имеется подходящий Comparator .
Порядок элементов не гарантируется.
Сортирует элементы по возрастанию в соответствии с их естественным порядком или с помощью предоставленного Comparator.
Наследует характеристики от интерфейса SortedSet. Все элементы of TreeSet должны быть типа Comparable (сопоставимого), или вы должны предоставить Comparator (компаратор) для TreeSet для сравнения элементов друг с другом. В противном случае будет вызвано исключение ClassCastException. Comparator предоставляется в момент создания объекта TreeSet с помощью одного из его конструкторов.
Конструкторы of TreeSet:
TreeSet​(Comparator<? super E> comparator)   

// Using the same ordering as the specified sortedSet.
TreeSet​(SortedSet<E> sortedSet)    

TreeSet()     

TreeSet​(Collection<? extends E> c)

2. Как TreeSet хранит данные?

TreeSet<E> управляет внутренним объектом TreeMap<E,Object> - internalMap. Все операции на TreeSet выполняются на internalMap. Кроме того, как мы знаем, TreeMap хранит свои данные в древовидной структуре, что является причиной названия TreeSet.
Для удобства понимания посмотрите исходный код класса java.util.TreeSet, вы увидите, что он действует как делегат объекта TreeMap, которым он управляет.
java.util.TreeSet class
public class TreeSet<E> extends AbstractSet<E>
                   implements NavigableSet<E>, Cloneable, java.io.Serializable {

    private static final Object PRESENT = new Object();
    
    private transient TreeMap<E,Object> internalMap;
    
    public boolean add(E e) {
        return this.internalMap.put(e, PRESENT)==null;
    }
    
    public boolean remove(Object o) {
        return this.internalMap.remove(o)==PRESENT;
    }
    
    public void clear() {
        this.internalMap.clear();
    }
    
     public E first() {
        return this.internalMap.firstKey();
    }
     
    public E last() {
        return this.internalMap.lastKey();
    }
    // Other methods..
}
TreeMap хранит свои данные в древовидной структуре, которая описана в моей статье ниже. Прочитайте это, если вам интересно.

3. Examples

Как мы все знаем, класс Integer реализует interface Comparable, поэтому объекты Integer c можно сравнивать друг с другом. TreeSet с элементами типа Integer не нуждается в предоставлении Comparator.
TreeSetEx1.java
package org.o7planning.treeset.ex;

import java.util.TreeSet;

public class TreeSetEx1 {

    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        //
        set.add(5);
        set.add(3);
        set.add(9);
        set.add(7);
        set.add(1);
        set.add(11);

        System.out.println(set);
    }
}
Output:
[1, 3, 5, 7, 9, 11]
Например: Используйте пользовательский Comparator для изменения порядка элементов.
TreeSet_reverseOrder_ex1.java
package org.o7planning.treeset.ex;

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSet_reverseOrder_ex1 {

    public static void main(String[] args) {
        Comparator<Integer> reverseOrderComparator = Comparator.reverseOrder();
        
        TreeSet<Integer> set = new TreeSet<>(reverseOrderComparator);
        //
        set.add(5);
        set.add(3);
        set.add(9);
        set.add(7);
        set.add(1);
        set.add(11);

        System.out.println(set);
    }
}
Output:
[11, 9, 7, 5, 3, 1]
См.Дополнительные примеры использования пользовательского Comparator в TreeSet, а также инструкции по навигации и поиску элементов.

4. TreeSet с элементом null

TreeSet допускает элемент null только в том случае, если он снабжен Comparator, поддерживающим сравнение элемента null с другими элементами.
TreeSet_nullElement_ex1.java
package org.o7planning.treeset.ex;

import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSet_nullElement_ex1 {

    public static void main(String[] args) {
        // Comparator.nullsFirst
        // Comparator.nullsLast
        Comparator<String> comparator = Comparator.nullsFirst(Comparator.naturalOrder());

        // Create a SortedSet object.
        SortedSet<String> map = new TreeSet<String>(comparator);

        map.add("B");
        map.add("A");
        map.add("F");
        map.add(null);
        map.add("D");
        map.add("E");

        System.out.println(map);
    }
}
Output:
[null, A, B, D, E, F]
Например: Напишите пользовательский Comparator, который поддерживает сравнение элемента null с другими элементами:
TreeSet_nullElement_ex2.java
package org.o7planning.treeset.ex;

import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSet_nullElement_ex2 {

    public static void main(String[] args) {
        Comparator<String> comparator = new StringNullComparator();

        // Create a SortedSet object.
        SortedSet<String> map = new TreeSet<String>(comparator);

        map.add("B");
        map.add("A");
        map.add("F");
        map.add(null);
        map.add("D");
        map.add("E");

        System.out.println(map);
    }
}

// The comparator supports null comparison.
class StringNullComparator implements Comparator<String> {

    @Override
    public int compare(String o1, String o2) {
        if (o1 == o2) {
            return 0; // o1 = o2
        }
        if (o1 == null) {
            return -1; // o1 < o2
        }
        if (o2 == null) {
            return 1; // o1 > o2
        }
        return o1.compareTo(o2);
    }
}
Output:
[null, A, B, D, E, F]

Руководства Java Collections Framework

Show More

Новейшие статьи

    Show More