Руководство Java TreeSet
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, прежде чем продолжить эту статью.
- Collection
- Set
- SortedSet
- NavigableSet
- ConcurrentSkipListSet
- HashSet
- LinkedHashSet
- CopyOnWriteArraySet
- EnumSet
Характеристики 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, а также инструкции по навигации и поиску элементов.
- NavigableSet
- SortedSet
- Comparator
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
- Руководство Java PriorityBlockingQueue
- Руководство Java Collections Framework
- Руководство Java SortedSet
- Руководство Java List
- Руководство Java Iterator
- Руководство Java NavigableSet
- Руководство Java ListIterator
- Руководство Java ArrayList
- Руководство Java CopyOnWriteArrayList
- Руководство Java LinkedList
- Руководство Java Set
- Руководство Java TreeSet
- Руководство Java CopyOnWriteArraySet
- Руководство Java Queue
- Руководство Java Deque
- Руководство Java IdentityHashMap
- Руководство Java WeakHashMap
- Руководство Java Map
- Руководство Java SortedMap
- Руководство Java NavigableMap
- Руководство Java HashMap
- Руководство Java TreeMap
- Руководство Java PriorityQueue
- Руководство Java BlockingQueue
- Руководство Java ArrayBlockingQueue
- Руководство Java TransferQueue
Show More