«1. Обзор
В этой статье мы рассмотрим неотъемлемую часть Java Collections Framework и одну из самых популярных реализаций Set — TreeSet.
2. Введение в TreeSet
Проще говоря, TreeSet — это отсортированная коллекция, которая расширяет класс AbstractSet и реализует интерфейс NavigableSet.
Вот краткий обзор наиболее важных аспектов этой реализации:
-
Хранит уникальные элементы Не сохраняет порядок вставки элементов Сортирует элементы в возрастающем порядке Не является потокобезопасным
В В этой реализации объекты сортируются и сохраняются в порядке возрастания в соответствии с их естественным порядком. TreeSet использует самобалансирующееся бинарное дерево поиска, точнее красно-черное дерево.
Проще говоря, будучи самобалансирующимся бинарным деревом поиска, каждый узел бинарного дерева содержит дополнительный бит, который используется для определения цвета узла: красного или черного. Во время последующих вставок и удалений эти биты «цвета» помогают гарантировать, что дерево останется более или менее сбалансированным.
Итак, давайте создадим экземпляр TreeSet:
Set<String> treeSet = new TreeSet<>();2.1. TreeSet с Constructor Comparator Param
При желании мы можем создать TreeSet с помощью конструктора, который позволяет нам определить порядок сортировки элементов с помощью Comparable или Comparator:
Set<String> treeSet = new TreeSet<>(Comparator.comparing(String::length));Хотя TreeSet не является потоком -safe, его можно синхронизировать извне с помощью оболочки Collections.synchronizedSet():
Set<String> syncTreeSet = Collections.synchronizedSet(treeSet);Хорошо, теперь, когда у нас есть четкое представление о том, как создать экземпляр TreeSet, давайте посмотрим на общие операции, которые у нас есть. доступный.
3. TreeSet add()
Метод add(), как и ожидалось, можно использовать для добавления элементов в TreeSet. Если элемент был добавлен, метод возвращает true, иначе — false.
В контракте метода указано, что элемент будет добавлен только в том случае, если его еще нет в наборе.
Давайте добавим элемент в TreeSet:
@Test
public void whenAddingElement_shouldAddElement() {
Set<String> treeSet = new TreeSet<>();
assertTrue(treeSet.add("String Added"));
}Метод add чрезвычайно важен, так как детали реализации этого метода иллюстрируют внутреннюю работу TreeSet, как он использует метод put TreeMap для хранения элементов: ~ ~~
public boolean add(E e) {
return m.put(e, PRESENT) == null;
}Переменная m относится к внутренней резервной карте TreeMap (обратите внимание, что TreeMap реализует NavigateableMap):
private transient NavigableMap<E, Object> m;Таким образом, TreeSet внутренне зависит от резервной карты NavigableMap, которая инициализируется экземпляром TreeMap, когда экземпляр Создается TreeSet:
public TreeSet() {
this(new TreeMap<E,Object>());
}Подробнее об этом можно прочитать в этой статье.
4. TreeSet contains()
Метод contains() используется для проверки наличия данного элемента в данном TreeSet. Если элемент найден, он возвращает true, в противном случае — false.
Давайте посмотрим на функцию contains() в действии:
@Test
public void whenCheckingForElement_shouldSearchForElement() {
Set<String> treeSetContains = new TreeSet<>();
treeSetContains.add("String Added");
assertTrue(treeSetContains.contains("String Added"));
}5. TreeSet remove()
Метод remove() используется для удаления указанного элемента из набора, если он присутствует.
Если набор содержит указанный элемент, этот метод возвращает значение true.
Давайте посмотрим на это в действии:
@Test
public void whenRemovingElement_shouldRemoveElement() {
Set<String> removeFromTreeSet = new TreeSet<>();
removeFromTreeSet.add("String Added");
assertTrue(removeFromTreeSet.remove("String Added"));
}6. TreeSet clear()
Если мы хотим удалить все элементы из набора, мы можем использовать метод clear():
@Test
public void whenClearingTreeSet_shouldClearTreeSet() {
Set<String> clearTreeSet = new TreeSet<>();
clearTreeSet.add("String Added");
clearTreeSet.clear();
assertTrue(clearTreeSet.isEmpty());
}~~ ~ 7. TreeSet size()
Метод size() используется для определения количества элементов, присутствующих в TreeSet. Это один из основных методов API:
@Test
public void whenCheckingTheSizeOfTreeSet_shouldReturnThesize() {
Set<String> treeSetSize = new TreeSet<>();
treeSetSize.add("String Added");
assertEquals(1, treeSetSize.size());
}8. TreeSet isEmpty()
Метод isEmpty() можно использовать для определения того, является ли данный экземпляр TreeSet пустым или нет:
@Test
public void whenCheckingForEmptyTreeSet_shouldCheckForEmpty() {
Set<String> emptyTreeSet = new TreeSet<>();
assertTrue(emptyTreeSet.isEmpty());
}~ ~~ 9. TreeSet iterator()
Метод iterator() возвращает итератор, выполняющий итерацию в возрастающем порядке по элементам набора. Эти итераторы отказоустойчивы.
Мы можем наблюдать восходящий порядок итерации здесь:
@Test
public void whenIteratingTreeSet_shouldIterateTreeSetInAscendingOrder() {
Set<String> treeSet = new TreeSet<>();
treeSet.add("First");
treeSet.add("Second");
treeSet.add("Third");
Iterator<String> itr = treeSet.iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
}Кроме того, TreeSet позволяет нам перебирать множество в убывающем порядке.
Давайте посмотрим на это в действии:
@Test
public void whenIteratingTreeSet_shouldIterateTreeSetInDescendingOrder() {
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("First");
treeSet.add("Second");
treeSet.add("Third");
Iterator<String> itr = treeSet.descendingIterator();
while (itr.hasNext()) {
System.out.println(itr.next());
}
}Итератор выдает исключение ConcurrentModificationException, если набор модифицируется в любое время после создания итератора любым способом, кроме как с помощью метода remove() итератора.
Создадим для этого тест:
@Test(expected = ConcurrentModificationException.class)
public void whenModifyingTreeSetWhileIterating_shouldThrowException() {
Set<String> treeSet = new TreeSet<>();
treeSet.add("First");
treeSet.add("Second");
treeSet.add("Third");
Iterator<String> itr = treeSet.iterator();
while (itr.hasNext()) {
itr.next();
treeSet.remove("Second");
}
}
«
@Test
public void whenRemovingElementUsingIterator_shouldRemoveElement() {
Set<String> treeSet = new TreeSet<>();
treeSet.add("First");
treeSet.add("Second");
treeSet.add("Third");
Iterator<String> itr = treeSet.iterator();
while (itr.hasNext()) {
String element = itr.next();
if (element.equals("Second"))
itr.remove();
}
assertEquals(2, treeSet.size());
}«В качестве альтернативы, если бы мы использовали метод удаления итератора, то мы бы не столкнулись с исключением: несинхронизированной одновременной модификации.
Подробнее об этом можно узнать здесь.
10. TreeSet first()
Этот метод возвращает первый элемент из TreeSet, если он не пустой. В противном случае выдается исключение NoSuchElementException.
Рассмотрим пример:
@Test
public void whenCheckingFirstElement_shouldReturnFirstElement() {
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("First");
assertEquals("First", treeSet.first());
}11. TreeSet last()
Аналогично приведенному выше примеру, этот метод вернет последний элемент, если набор не пуст:
@Test
public void whenCheckingLastElement_shouldReturnLastElement() {
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("First");
treeSet.add("Last");
assertEquals("Last", treeSet.last());
}12 .TreeSet subSet()
Этот метод возвращает элементы в диапазоне от fromElement до toElement. Обратите внимание, что fromElement является инклюзивным, а toElement — исключающим:
@Test
public void whenUsingSubSet_shouldReturnSubSetElements() {
SortedSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add(2);
treeSet.add(3);
treeSet.add(4);
treeSet.add(5);
treeSet.add(6);
Set<Integer> expectedSet = new TreeSet<>();
expectedSet.add(2);
expectedSet.add(3);
expectedSet.add(4);
expectedSet.add(5);
Set<Integer> subSet = treeSet.subSet(2, 6);
assertEquals(expectedSet, subSet);
}13. TreeSet headSet()
Этот метод вернет элементы TreeSet, которые меньше указанного элемента:
@Test
public void whenUsingHeadSet_shouldReturnHeadSetElements() {
SortedSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add(2);
treeSet.add(3);
treeSet.add(4);
treeSet.add(5);
treeSet.add(6);
Set<Integer> subSet = treeSet.headSet(6);
assertEquals(subSet, treeSet.subSet(1, 6));
}14. TreeSet tailSet ()
Этот метод вернет элементы TreeSet, которые больше или равны указанному элементу:
@Test
public void whenUsingTailSet_shouldReturnTailSetElements() {
NavigableSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add(2);
treeSet.add(3);
treeSet.add(4);
treeSet.add(5);
treeSet.add(6);
Set<Integer> subSet = treeSet.tailSet(3);
assertEquals(subSet, treeSet.subSet(3, true, 6, true));
}15. Хранение нулевых элементов
До Java 7 можно было добавлять нулевые элементы в пустой TreeSet.
Однако это было сочтено ошибкой. Поэтому TreeSet больше не поддерживает добавление null.
Когда мы добавляем элементы в TreeSet, элементы сортируются в соответствии с их естественным порядком или в порядке, указанном компаратором. Следовательно, добавление нулевого значения при сравнении с существующими элементами приводит к исключению NullPointerException, поскольку нуль нельзя сравнивать ни с каким значением:
@Test(expected = NullPointerException.class)
public void whenAddingNullToNonEmptyTreeSet_shouldThrowException() {
Set<String> treeSet = new TreeSet<>();
treeSet.add("First");
treeSet.add(null);
}Элементы, вставленные в TreeSet, должны либо реализовывать интерфейс Comparable, либо, по крайней мере, быть приняты указанным компаратором . Все такие элементы должны быть взаимно сопоставимы, т. е. e1.compareTo(e2) или comparator.compare(e1, e2) не должны вызывать ClassCastException.
Давайте рассмотрим пример:
class Element {
private Integer id;
// Other methods...
}
Comparator<Element> comparator = (ele1, ele2) -> {
return ele1.getId().compareTo(ele2.getId());
};
@Test
public void whenUsingComparator_shouldSortAndInsertElements() {
Set<Element> treeSet = new TreeSet<>(comparator);
Element ele1 = new Element();
ele1.setId(100);
Element ele2 = new Element();
ele2.setId(200);
treeSet.add(ele1);
treeSet.add(ele2);
System.out.println(treeSet);
}16. Производительность TreeSet
По сравнению с HashSet производительность TreeSet ниже. Такие операции, как добавление, удаление и поиск, занимают O(log n) времени, в то время как такие операции, как печать n элементов в отсортированном порядке, требуют O(n) времени.
TreeSet должен быть нашим основным выбором, если мы хотим, чтобы наши записи были отсортированы, поскольку TreeSet может быть доступен и пройден либо в восходящем, либо в нисходящем порядке, а производительность восходящих операций и представлений, вероятно, будет выше, чем у нисходящих. те.
Принцип локальности — это термин, обозначающий явление, при котором часто осуществляется доступ к одним и тем же значениям или связанным с ними местам хранения в зависимости от шаблона доступа к памяти.
Когда мы говорим о местоположении:
-
Приложения часто обращаются к похожим данным с одинаковой частотой. Если две записи находятся рядом с заданным порядком, TreeSet помещает их рядом друг с другом в структуре данных и, следовательно, в памяти
TreeSet является структурой данных с большей локальностью, поэтому мы можем сделать вывод в соответствии с принципом локальности, что мы должны отдать предпочтение TreeSet, если у нас мало памяти и если мы хотим получить доступ к относительно близким элементам. друг к другу в соответствии с их естественным порядком.
В случае, если данные должны быть прочитаны с жесткого диска (который имеет большую задержку, чем данные, прочитанные из кэша или памяти), отдайте предпочтение TreeSet, поскольку он имеет большую локальность
17. Заключение
В этой статье мы сосредоточьтесь на понимании того, как использовать стандартную реализацию TreeSet в Java. Мы увидели его цель и то, насколько он эффективен в отношении удобства использования, учитывая его способность избегать дубликатов и сортировать элементы.
Как всегда, фрагменты кода можно найти на GitHub.