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

Автор оригинала: baeldung.

1. Обзор

В этой статье мы будем смотреть на неотъемлемую часть Java Коллекции Framework и один из самых популярных Установить реализации – TreeSet .

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

Проще говоря, TreeSet это отсортированная коллекция, которая расширяет АбстрактСет класса и реализует Навигационаясеть интерфейс.

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

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

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

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

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

Set treeSet = new TreeSet<>();

2.1. TreeSet со конструктором-компаратором Param

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

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

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

Set syncTreeSet = Collections.synchronizedSet(treeSet);

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

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

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

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

Давайте добавим элемент в TreeSet :

@Test
public void whenAddingElement_shouldAddElement() {
    Set treeSet = new TreeSet<>();

    assertTrue(treeSet.add("String Added"));
 }

добавить метод чрезвычайно важен, так как детали реализации метода иллюстрируют, как TreeSet работает внутренне , как он использует Тримэп положить метод хранения элементов:

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

Переменная м относится к внутреннему резервному TreeMap (Обратите внимание, что TreeMap реализует НавигацияМап ):

private transient NavigableMap m;

Таким образом, TreeSet внутренне зависит от поддержки Навигационая карта который инициализируется с экземпляром TreeMap когда экземпляр TreeSet создается:

public TreeSet() {
    this(new TreeMap());
}

Подробнее об этом можно найти в этой статье .

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

содержит () метод используется для проверки, присутствует ли данный элемент в данном TreeSet . Если элемент найден, он возвращается верно, в противном случае ложный.

Посмотрим на содержит () в действии:

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

    assertTrue(treeSetContains.contains("String Added"));
}

5. TreeSet удалить ()

тем удалить () метод используется для удаления указанного элемента из набора, если он присутствует.

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

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

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

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

6. TreeSet ясно ()

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

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

7. Размер TreeSet ()

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

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

8. TreeSet isEmpty ()

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

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

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

итератор () метод возвращает итератор, итерирующий в порядке возрастания над элементами в набор. Эти итераторы не быстро .

Мы можем наблюдать восходящий порядок итерации здесь:

@Test
public void whenIteratingTreeSet_shouldIterateTreeSetInAscendingOrder() {
    Set treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator itr = treeSet.iterator();
    while (itr.hasNext()) {
        System.out.println(itr.next());
    }
}

Кроме того, TreeSet позволяет нам итерировать через Установить в порядке убывания.

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

@Test
public void whenIteratingTreeSet_shouldIterateTreeSetInDescendingOrder() {
    TreeSet treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator itr = treeSet.descendingIterator();
    while (itr.hasNext()) {
        System.out.println(itr.next());
    }
}

тем итератор бросает ПараллельноМодификацияИсключение i f набор изменяется в любое время после того, как итератор создается любым способом, за исключением удалить () метод.

Давайте создадим тест для этого:

@Test(expected = ConcurrentModificationException.class)
public void whenModifyingTreeSetWhileIterating_shouldThrowException() {
    Set treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator itr = treeSet.iterator();
    while (itr.hasNext()) {
        itr.next();
        treeSet.remove("Second");
    }
}

Кроме того, если бы мы использовали метод удаления итератора, то мы бы не столкнулись с исключением:

@Test
public void whenRemovingElementUsingIterator_shouldRemoveElement() {
 
    Set treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator 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 treeSet = new TreeSet<>();
    treeSet.add("First");
   
    assertEquals("First", treeSet.first());
}

11. TreeSet последний ()

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

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

12. Подсеть TreeSet ()

Этот метод будет возвращать элементы, начиная от отЭлемент toЭлемент. Обратите внимание, что отЭлемент является инклюзивным и toЭлемент является эксклюзивным:

@Test
public void whenUsingSubSet_shouldReturnSubSetElements() {
    SortedSet treeSet = new TreeSet<>();
    treeSet.add(1);
    treeSet.add(2);
    treeSet.add(3);
    treeSet.add(4);
    treeSet.add(5);
    treeSet.add(6);
    
    Set expectedSet = new TreeSet<>();
    expectedSet.add(2);
    expectedSet.add(3);
    expectedSet.add(4);
    expectedSet.add(5);

    Set subSet = treeSet.subSet(2, 6);
 
    assertEquals(expectedSet, subSet);
}

13. Глава TreeSet ()

Этот метод вернет элементы TreeSet которые меньше указанного элемента:

@Test
public void whenUsingHeadSet_shouldReturnHeadSetElements() {
    SortedSet treeSet = new TreeSet<>();
    treeSet.add(1);
    treeSet.add(2);
    treeSet.add(3);
    treeSet.add(4);
    treeSet.add(5);
    treeSet.add(6);

    Set subSet = treeSet.headSet(6);
 
    assertEquals(subSet, treeSet.subSet(1, 6));
}

14. Хвост TreeSet()

Этот метод вернет элементы TreeSet которые больше или равны указанному элементу:

@Test
public void whenUsingTailSet_shouldReturnTailSetElements() {
    NavigableSet treeSet = new TreeSet<>();
    treeSet.add(1);
    treeSet.add(2);
    treeSet.add(3);
    treeSet.add(4);
    treeSet.add(5);
    treeSet.add(6);

    Set subSet = treeSet.tailSet(3);
 
    assertEquals(subSet, treeSet.subSet(3, true, 6, true));
}

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

До Java 7 можно было добавить нулевой элементы пустого TreeSet.

Тем не менее, это было сочтено ошибкой. Поэтому TreeSet больше не поддерживает добавление недействительный.

Когда мы добавляем элементы в TreeSet, элементы сортируются в соответствии с их естественным порядком или в соответствии с компаратор. Таким образом, нулевой, по сравнению с существующими элементами, приводит к NullPointerЭксцепция с нулевой не может сравниться с любым значением:

@Test(expected = NullPointerException.class)
public void whenAddingNullToNonEmptyTreeSet_shouldThrowException() {
    Set treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add(null);
}

Элементы, вставленные в TreeSet должны либо реализовать Сопоставимые интерфейс или, по крайней мере, быть принятым указанным компаратором. Все такие элементы должны быть взаимосопоставимыми, т.е. e1.compareTo(e2) или comparator.compare (e1, e2) не должны бросать ClassCastException .

Рассмотрим пример:

class Element {
    private Integer id;

    // Other methods...
}

Comparator comparator = (ele1, ele2) -> {
    return ele1.getId().compareTo(ele2.getId());
};

@Test
public void whenUsingComparator_shouldSortAndInsertElements() {
    Set 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 (журнал n) время в то время как операции, такие как n элементы в отсортированом порядке требуют О(н) Время.

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

Принцип локальности — это термин для явления, в котором те же значения, или связанные с ними места хранения, часто доступны, в зависимости от шаблона доступа к памяти.

Когда мы говорим местности:

• Аналогичные данные часто доступны приложению с аналогичной частотой
• Если две записи находятся поблизости, учитывая заказ, TreeSet помещает их рядом друг с другом в структуре данных, и, следовательно, в памяти

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

В случае, если данные должны быть прочитаны с жесткого диска (который имеет большую задержку, чем данные, читаемые из кэша или памяти), то предпочитают TreeSet так как она имеет большую локализацию

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

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

Как всегда, фрагменты кода можно найти более на GitHub .