Java for Beginner

TreeSet, особенности и внутреннее устройство

TreeSet — это класс в Java, представляющий собой коллекцию, которая хранит элементы в отсортированном порядке. Он является частью Java Collection Framework и имплементирует интерфейсы NavigableSet, SortedSet, и косвенно Set. Это значит, что TreeSet не допускает дубликатов и автоматически сортирует элементы при их добавлении.

Особенности TreeSet:

Автоматическая сортировка: Элементы в TreeSet автоматически сортируются в соответствии с естественным порядком (Comparable) или по переданному компаратору (Comparator).
Уникальные элементы: Как и любой другой Set, TreeSet не допускает дублирования элементов.
Балансировка: TreeSet основан на сбалансированном бинарном дереве поиска, что гарантирует логарифмическое время выполнения основных операций (добавление, удаление, поиск).
Навигация по элементам: TreeSet предоставляет методы для быстрого доступа к наименьшему и наибольшему элементам, а также позволяет эффективно находить элементы, ближайшие к заданному значению.

Внутреннее устройство TreeSet

TreeSet основан на структуре данных TreeMap, которая, в свою очередь, представляет собой красно-черное дерево — разновидность бинарного дерева поиска. Это дерево поддерживает балансировку, обеспечивая эффективное выполнение операций за время O(log n).
Каждый узел дерева имеет два потомка и родителя, а также хранит информацию о цвете (красный или черный), что помогает поддерживать балансировку дерева. Когда выполняется операция вставки или удаления, дерево перестраивается, чтобы оставаться сбалансированным.

Основные характеристики TreeSet:

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

Пример создания TreeSet:

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<String> treeSet = new TreeSet<>();
        treeSet.add("Apple");
        treeSet.add("Banana");
        treeSet.add("Cherry");

        System.out.println(treeSet);
    }
}

Этот код создаёт TreeSet, добавляет в него несколько строк и выводит их в отсортированном порядке: [Apple, Banana, Cherry].

Когда использовать TreeSet?

Когда требуется поддерживать отсортированный набор элементов: Например, для хранения уникальных слов из текста в алфавитном порядке.
Для задач, требующих быстрого доступа к минимальному или максимальному элементу: Например, когда нужно найти ближайшее к заданному значению число.
Когда нужно реализовать структуры данных с логарифмическим временем выполнения основных операций.
Однако TreeSet может быть неэффективен для больших наборов данных по сравнению с HashSet, так как операции требуют дополнительных вычислений для поддержания сортировки.

Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://www.baeldung.com/java-tree-set
https://for-each.dev/lessons/b/-java-tree-set

#Java #Training #Medium #TreeSet

Baeldung on Kotlin

A Guide to TreeSet in Java | Baeldung

A quick and practical introduction to the TreeSet in Java.

186 views05:32

Java for Beginner

Основные методы TreeSet и примеры использования

Добавление элементов:
boolean add(E e): Добавляет элемент в набор. Возвращает true, если элемент успешно добавлен (не был дубликатом).

Удаление элементов:
boolean remove(Object o): Удаляет элемент из набора. Возвращает true, если элемент был удалён.
void clear(): Удаляет все элементы из набора.

Поиск и получение элементов:
E first(): Возвращает первый (наименьший) элемент в наборе.
E last(): Возвращает последний (наибольший) элемент.
E lower(E e): Возвращает наибольший элемент, строго меньший чем переданный.
E higher(E e): Возвращает наименьший элемент, строго больший чем переданный.
E floor(E e): Возвращает наибольший элемент, меньший или равный переданному.
E ceiling(E e): Возвращает наименьший элемент, больший или равный переданному.
boolean contains(Object o): Проверяет, содержит ли набор указанный элемент.

Навигация и получение поднаборов:
SortedSet<E> headSet(E toElement): Возвращает поднабор от начала до элемента (исключительно).
SortedSet<E> tailSet(E fromElement): Возвращает поднабор от элемента (включительно) до конца.
SortedSet<E> subSet(E fromElement, E toElement): Возвращает поднабор от одного элемента до другого (от включительно, до исключительно).

Примеры использования методов:

1. Работа с элементами:

import java.util.TreeSet;

public class TreeSetDemo {
    public static void main(String[] args) {
        TreeSet<Integer> numbers = new TreeSet<>();
        numbers.add(5);
        numbers.add(2);
        numbers.add(10);
        numbers.add(1);

        System.out.println("Наименьший элемент: " + numbers.first());
        System.out.println("Наибольший элемент: " + numbers.last());
        System.out.println("Наибольший элемент, меньший 10: " + numbers.lower(10));
    }
}
Вывод:
Наименьший элемент: 1
Наибольший элемент: 10
Наибольший элемент, меньший 10: 5

2. Получение поднаборов:

import java.util.TreeSet;

public class TreeSetSubSetExample {
    public static void main(String[] args) {
        TreeSet<String> treeSet = new TreeSet<>();
        treeSet.add("Apple");
        treeSet.add("Banana");
        treeSet.add("Cherry");
        treeSet.add("Date");
        treeSet.add("Fig");

        System.out.println("Поднабор до 'Cherry': " + treeSet.headSet("Cherry"));
        System.out.println("Поднабор от 'Banana': " + treeSet.tailSet("Banana"));
    }
}
Вывод:
Поднабор до 'Cherry': [Apple, Banana]
Поднабор от 'Banana': [Banana, Cherry, Date, Fig]

#Java #Training #Medium #TreeSet

❤1

167 views14:19

Java for Beginner

Коллекции в Java

Глава 3. Set — множества

Реализации: HashSet, LinkedHashSet, TreeSet.

Применение множеств: удаление дубликатов, проверка уникальности

Интерфейс Set<E> имеет несколько реализаций в JCF, каждая оптимизирована под разные сценарии. Все они обеспечивают уникальность элементов, но отличаются по порядку, сортировке и времени операций.

HashSet<E>

Описание: HashSet — самая распространенная реализация Set, основанная на хэш-таблице (HashMap внутри). Она хранит элементы в "корзинах" (buckets) на основе их хэш-кода, что обеспечивает быстрый поиск и добавление.

Особенности:
Уникальность: Да, дубликаты игнорируются.
Порядок: Нет гарантированного порядка (зависит от хэша, может меняться при ресайзе).
Сортировка: Нет.
Null: Разрешен один null.
Big O: Средний случай — O(1) для add, remove, contains (константное время). Worst-case — O(n) при коллизиях хэшей, но редко с хорошим hashCode().

Внутренняя работа: Элементы хранятся как ключи в HashMap (значения — dummy объект). Хэш-код определяет бакет, equals() — проверку уникальности.

Нюансы:
Зависит от hashCode() и equals(): Плохо реализованные методы приводят к коллизиям и снижению производительности.
Ресайз: При заполнении >75% (load factor) таблица удваивается, что может занять O(n) времени.
Thread-safety: Не безопасен для многопоточности — используйте Collections.synchronizedSet(new HashSet<>()).
Память: Занимает больше, чем ArrayList, из-за хэш-таблицы.

Пример кода:

javaimport java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> fruits = new HashSet<>();
        fruits.add("Яблоко");
        fruits.add("Банан");
        fruits.add("Яблоко");  // Игнорируется

        System.out.println(fruits.contains("Банан"));  // true
        fruits.remove("Яблоко");

        for (String fruit : fruits) {
            System.out.println(fruit);  // Порядок непредсказуем, например: Банан
        }
    }
}

Вывод: contains вернет true, размер 1 после удаления, порядок случайный.

LinkedHashSet<E>

Расширение HashSet с двусвязным списком для сохранения порядка вставки. Внутри — HashMap с LinkedHashMap-логикой.

Особенности:
Уникальность: Да.
Порядок: Сохраняет порядок вставки (insertion order).
Сортировка: Нет.
Null: Разрешен один null.
Big O: O(1) для add/remove/contains (как HashSet), но с overhead на ссылки списка.

Внутренняя работа: Каждый элемент имеет ссылки prev/next для списка, плюс хэш-таблица для уникальности.

Нюансы:
Больше памяти, чем HashSet (из-за ссылок).
Итерация: O(n), но предсказуема по порядку вставки.
Полезен для кэшей с LRU (least recently used), но для простого порядка — эффективен.
Thread-safety: Нет, как у HashSet.

Пример кода:

javaimport java.util.LinkedHashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> fruits = new LinkedHashSet<>();
        fruits.add("Яблоко");
        fruits.add("Банан");
        fruits.add("Апельсин");

        for (String fruit : fruits) {
            System.out.println(fruit);  // Яблоко, Банан, Апельсин — порядок вставки
        }
    }
}

Вывод: Элементы в том порядке, в котором добавлены.

#Java #для_новичков #beginner #Collections #HashSet #LinkedHashSet #TreeSet

👍3

45 views08:58

Java for Beginner

TreeSet<E>

Реализация SortedSet<E>, основанная на красно-черном дереве. Автоматически сортирует элементы.

Особенности:
Уникальность: Да.
Порядок: Нет (игнорирует порядок вставки), но отсортирован по натуральному порядку или Comparator.
Сортировка: Да, всегда отсортирован.
Null: Не разрешен (NullPointerException при сравнении).
Big O: O(log n) для add/remove/contains (дерево балансировано).

Внутренняя работа: Элементы хранятся в узлах дерева, сравниваются через Comparable.compareTo() или Comparator.

Нюансы:
Элементы должны реализовывать Comparable<E> или предоставить Comparator при создании: new TreeSet<>(comparator).
Для custom классов: Реализуйте Comparable или Comparator, иначе ClassCastException.
Итерация: O(n), в отсортированном порядке.
Дополнительные методы: first(), last(), headSet(E to), tailSet(E from) — для подмножеств.
Thread-safety: Нет, используйте Collections.synchronizedSortedSet(new TreeSet<>()).
Память: Больше, чем HashSet, из-за структуры дерева.

Пример кода:

javaimport java.util.TreeSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Integer> numbers = new TreeSet<>();
        numbers.add(5);
        numbers.add(1);
        numbers.add(3);

        for (Integer num : numbers) {
            System.out.println(num);  //отсортировано
        }

        // С Comparator для обратного порядка
        Set<Integer> reverseNumbers = new TreeSet<>((a, b) -> b - a);
        reverseNumbers.add(5);
        reverseNumbers.add(1);
        reverseNumbers.add(3);
        System.out.println(reverseNumbers);  // [5, 3, 1]
    }
}

Вывод: Элементы всегда отсортированы.

Применение множеств: Удаление дубликатов и проверка уникальности

Множества идеальны для задач, где нужна уникальность без дубликатов.

Удаление дубликатов:
Преобразуйте List или массив в Set — дубликаты автоматически удалятся.
Нюанс: Порядок может потеряться (используйте LinkedHashSet для сохранения).

Пример кода:

javaimport java.util.ArrayList;
import java.util.List;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        List<String> duplicates = new ArrayList<>();
        duplicates.add("Яблоко");
        duplicates.add("Банан");
        duplicates.add("Яблоко");

        Set<String> unique = new HashSet<>(duplicates);
        System.out.println(unique);  // [Банан, Яблоко]

        // С сохранением порядка
        Set<String> orderedUnique = new LinkedHashSet<>(duplicates);
        System.out.println(orderedUnique);  // [Яблоко, Банан]
    }
}

Вывод: Уникальные элементы, без дубликатов.

Проверка уникальности:
Используйте contains() для быстрой проверки наличия (O(1) в HashSet).
Или add() — если false, элемент уже есть.
Нюанс: Для больших данных Set эффективнее, чем перебор List (O(n)).

Пример кода:

javaimport java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> users = new HashSet<>();
        users.add("user1");

        if (users.contains("user2")) {
            System.out.println("Пользователь существует");
        } else {
            users.add("user2");
            System.out.println("Новый пользователь добавлен");
        }

        if (!users.add("user1")) {
            System.out.println("Дубликат не добавлен");  // add возвращает false
        }
    }
}

Вывод: Проверка и добавление без дубликатов.

Полезные советы для новичков

HashSet по умолчанию: Для большинства случаев уникальности.
Custom классы: Всегда реализуйте equals() и hashCode() (используйте IDE: Generate → equals() and hashCode()).
Comparator в TreeSet: Для custom сортировки: new TreeSet<>((a, b) -> a.compareTo(b)).
Удаление дубликатов: Удобно для списков из файлов или БД.
Память: TreeSet дороже по памяти, HashSet — оптимален.
Ошибки: ClassCastException в TreeSet без Comparable; ConcurrentModificationException при модификации во время итерации (используйте Iterator.remove()).

#Java #для_новичков #beginner #Collections #HashSet #LinkedHashSet #TreeSet

👍2

55 views08:58

About

Blog

Apps

Platform