Коллекции в Java

Глава 1. Введение в коллекции

Основные характеристики коллекций: время доступа (Big O), хранение уникальных элементов, упорядоченность и сортировка

Big O (или O-нотация) — это математическая нотация, которая описывает, как растет время выполнения операции (или использование памяти) в зависимости от размера данных (n — количество элементов). Она оценивает "наихудший случай" и помогает сравнивать эффективность коллекций.

Основные обозначения Big O:
- O(1): Постоянное время — операция не зависит от размера (например, доступ по индексу в массиве).
- O(log n): Логарифмическое время — быстро растет, но эффективно (например, поиск в отсортированном дереве).
- O(n): Линейное время — пропорционально размеру (например, перебор списка).
- O(n log n): Для сортировки (например, TreeSet).
- O(n²): Квадратичное — медленно для больших n (избегайте).

Для коллекций Big O применяется к основным операциям: добавление (add), удаление (remove), поиск (contains/get), вставка.

Почему важно: Выбор коллекции влияет на производительность. Для миллионов элементов O(1) лучше O(n).


Хранение уникальных элементов

Коллекции различаются по тому, позволяют ли они дубликаты элементов.

Коллекции с уникальными элементами:
- Интерфейс Set<E>: Не позволяет дубликаты. Если добавить существующий элемент, он игнорируется (add() возвращает false).
- Пример: HashSet, TreeSet, LinkedHashSet.
- Нюанс: Уникальность определяется методом equals() и hashCode() (для HashSet). Переопределите их для custom классов.

Коллекции с дубликатами:
- Интерфейс List<E>: Позволяет дубликаты и хранит их в порядке вставки.
- Пример: ArrayList, LinkedList.
- Queue<E> и Deque<E>: Могут позволять дубликаты, в зависимости от реализации.

- Map<K, V>: Ключи уникальны (как Set), значения могут дублироваться.

Пример кода для уникальности:

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

public class Main {
    public static void main(String[] args) {
        // Set: Уникальные элементы
        Set<String> uniqueNames = new HashSet<>();
        uniqueNames.add("Алексей");
        uniqueNames.add("Алексей");  // Игнорируется
        System.out.println(uniqueNames.size());  // 1

        // List: Дубликаты разрешены
        List<String> names = new ArrayList<>();
        names.add("Алексей");
        names.add("Алексей");
        System.out.println(names.size());  // 2
    }
}

- Нюанс: Для custom объектов в Set переопределите equals() и hashCode(), иначе дубликаты возможны (сравнение по ссылке).

#Java #для_новичков #beginner #Collections #BigO

Упорядоченность элементов

Упорядоченность — это сохранение порядка элементов (по вставке или сортировке).

Коллекции с порядком вставки:
- List<E>: Всегда упорядочены по индексу (порядок добавления).
- Пример: ArrayList, LinkedList.
- LinkedHashSet<E>: Set с порядком вставки.
- LinkedHashMap<K, V>: Map с порядком вставки.

Коллекции без порядка:
- HashSet<E>: Не гарантирует порядок (зависит от хэша).
- HashMap<K, V>: Не упорядочен.

Отсортированные коллекции: Подробнее в разделе о сортировке.

Пример:

import java.util.HashSet;
import java.util.LinkedHashSet;

public class Main {
    public static void main(String[] args) {
        // HashSet: Без порядка
        Set<String> hashSet = new HashSet<>();
        hashSet.add("Яблоко");
        hashSet.add("Банан");
        hashSet.add("Апельсин");
        System.out.println(hashSet);  // Может быть [Банан, Яблоко, Апельсин] — непредсказуемо

        // LinkedHashSet: Порядок вставки
        Set<String> linkedSet = new LinkedHashSet<>();
        linkedSet.add("Яблоко");
        linkedSet.add("Банан");
        linkedSet.add("Апельсин");
        System.out.println(linkedSet);  // [Яблоко, Банан, Апельсин] — сохраняет порядок
    }
}

- Нюанс: Порядок в HashSet может меняться при ресайзе (rehashing), так что не полагайтесь на него.


Сортировка элементов

Сортировка — это автоматическое упорядочивание элементов по какому-то критерию (натуральный порядок или Comparator).

Отсортированные коллекции:
- SortedSet<E> (подинтерфейс Set): Уникальные, отсортированные элементы.
- Реализация: TreeSet<E> — использует красно-черное дерево.
- SortedMap<K, V> (подинтерфейс Map): Отсортированные ключи.
- Реализация: TreeMap<K, V>.

Как работает сортировка:
- Элементы должны быть Comparable<E> (метод compareTo()) для натурального порядка (числа по возрастанию, строки по алфавиту).
- Или используйте Comparator при создании: new TreeSet<>(comparator).
- Нюанс: Добавление/поиск — O(log n), так как дерево балансировано.

Пример TreeSet:

import 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);
        System.out.println(numbers);  // [1, 3, 5] — отсортировано

        // Custom 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]
    }
}

- Нюанс: TreeSet не позволяет null (NullPointerException), так как сравнивает элементы.
Для сортировки существующих коллекций используйте Collections.sort(List list) или List.sort(Comparator).


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

- Big O в практике: Для малого n (сотни элементов) разница мала, но для миллионов — критична (выберите HashSet для быстрого contains).
- Уникальность: Set для словарей, List для списков с повторами.
- Упорядоченность: Linked* для сохранения вставки, Tree* для автосортировки.
- Сортировка: TreeSet/Map для постоянной сортировки; Collections.sort() для разовой.
- Ошибки: Null в TreeSet — NPE; дубли в Set — игнор.
- Ресурсы: Java API docs для java.util.


#Java #для_новичков #beginner #Collections #BigO