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

22 сентября 2020 г. · 8 мин. чтения

Задача: Сумма двух

Дано массив целых чисел и целая сумма. Нужно найти индексы двух чисел, сумма которых равна заданной ...

ANDROMEDA

1. Обзор

В этой статье мы рассмотрим неотъемлемую часть Java Collections Framework и одну из самых популярных реализаций Set — TreeSet .

2. Введение в `TreeSet`

Проще говоря, TreeSet — это отсортированная коллекция, которая расширяет класс AbstractSet и реализует интерфейс NavigableSet .

Вот краткий обзор наиболее важных аспектов этой реализации:

Он хранит уникальные элементы
Он не сохраняет порядок вставки элементов
Сортирует элементы в порядке возрастания
Это не потокобезопасно

В этой реализации объекты сортируются и сохраняются в порядке возрастания в соответствии с их естественным порядком . TreeSet использует самобалансирующееся бинарное дерево поиска, точнее красно - черное дерево .

Проще говоря, будучи самобалансирующимся бинарным деревом поиска, каждый узел бинарного дерева содержит дополнительный бит, который используется для определения цвета узла: красного или черного. Во время последующих вставок и удалений эти «цветные» биты помогают обеспечить более или менее сбалансированное дерево.

Итак, давайте создадим экземпляр TreeSet :

Set<String> treeSet = new TreeSet<>();

2.1. TreeSet с параметром сравнения конструктора

При желании мы можем создать TreeSet с помощью конструктора, который позволяет нам определить порядок сортировки элементов с помощью Comparable или Comparator:

Set<String> treeSet = new TreeSet<>(Comparator.comparing(String::length));

Хотя TreeSet не является потокобезопасным, его можно синхронизировать извне с помощью оболочки Collections.synchronizedSet() :

Set<String> syncTreeSet = Collections.synchronizedSet(treeSet);

Хорошо, теперь, когда у нас есть четкое представление о том, как создать экземпляр TreeSet , давайте посмотрим на доступные нам общие операции.

3. Добавить `TreeSet` `()`

Метод add() , как и ожидалось, можно использовать для добавления элементов в TreeSet . Если элемент был добавлен, метод возвращает true, иначе — false.

В контракте метода указано, что элемент будет добавлен только в том случае, если его еще нет в Set .

Давайте добавим элемент в 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() используется для проверки наличия данного элемента в данном 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() используется для удаления указанного элемента из набора, если он присутствует.

Если набор содержит указанный элемент, этот метод возвращает значение true.

Давайте посмотрим на это в действии:

@Test
public void whenRemovingElement_shouldRemoveElement() {
    Set<String> removeFromTreeSet = new TreeSet<>();
    removeFromTreeSet.add("String Added");

    assertTrue(removeFromTreeSet.remove("String Added"));
}

6. `Очистить набор деревьев ()`

Если мы хотим удалить все элементы из набора, мы можем использовать метод clear() :

@Test
public void whenClearingTreeSet_shouldClearTreeSet() {
    Set<String> clearTreeSet = new TreeSet<>();
    clearTreeSet.add("String Added");
    clearTreeSet.clear();
 
    assertTrue(clearTreeSet.isEmpty());
}

7. `Размер набора деревьев ()`

Метод size() используется для определения количества элементов, присутствующих в TreeSet . Это один из основных методов в API:

@Test
public void whenCheckingTheSizeOfTreeSet_shouldReturnThesize() {
    Set<String> treeSetSize = new TreeSet<>();
    treeSetSize.add("String Added");
 
    assertEquals(1, treeSetSize.size());
}

8. `TreeSet пуст ()`

Метод isEmpty() можно использовать, чтобы выяснить, является ли данный экземпляр TreeSet пустым или нет:

@Test
public void whenCheckingForEmptyTreeSet_shouldCheckForEmpty() {
    Set<String> emptyTreeSet = new TreeSet<>();
    
    assertTrue(emptyTreeSet.isEmpty());
}

9. `Итератор TreeSet()`

Метод 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()`

Этот метод возвращает первый элемент из TreeSet , если он не пуст. В противном случае выдается исключение NoSuchElementException .

Давайте посмотрим пример:

@Test
public void whenCheckingFirstElement_shouldReturnFirstElement() {
    TreeSet<String> treeSet = new TreeSet<>();
    treeSet.add("First");
   
    assertEquals("First", treeSet.first());
}

11. `Последний набор деревьев ()`

Аналогично приведенному выше примеру, этот метод вернет последний элемент, если набор не пуст:

@Test
public void whenCheckingLastElement_shouldReturnLastElement() {
    TreeSet<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Last");
    
    assertEquals("Last", treeSet.last());
}

12. `Подмножество TreeSet()`

Этот метод вернет элементы в диапазоне от 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. `HeadSet TreeSet ()`

Этот метод вернет элементы 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. `Набор деревьев 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 .

Задача: Сумма двух

1. Обзор​

2. Введение в TreeSet​

2.1. TreeSet с параметром сравнения конструктора​

3. Добавить TreeSet ()​

4. TreeSet содержит ()​

5. Удаление TreeSet()​

6. Очистить набор деревьев ()​

7. Размер набора деревьев ()​

8. TreeSet пуст ()​

9. Итератор TreeSet()​

10. Сначала TreeSet()​

11. Последний набор деревьев ()​

12. Подмножество TreeSet()​

13. HeadSet TreeSet ()​

14. Набор деревьев tailSet()​

15. Хранение нулевых элементов​

16. Производительность TreeSet​

17. Заключение​