Какие классы и интерфейсы используешь из Java Collections

Java Collections Framework

Java Collections Framework — это набор интерфейсов и классов для эффективного хранения, управления и обработки групп объектов. Это один из наиболее часто используемых компонентов Java, и глубокое понимание особенностей каждой коллекции критично для качественного кода.

Основная иерархия

Iterable
    └── Collection
        ├── List
        │   ├── ArrayList
        │   ├── LinkedList
        │   └── Vector (legacy)
        ├── Set
        │   ├── HashSet
        │   ├── LinkedHashSet
        │   ├── TreeSet
        │   └── EnumSet
        ├── Queue
        │   ├── PriorityQueue
        │   ├── Deque
        │   │   ├── ArrayDeque
        │   │   └── LinkedList
        │   └── BlockingQueue (concurrent)
        └── Other
Map (отдельно от Collection!)
    ├── HashMap
    ├── LinkedHashMap
    ├── TreeMap
    ├── WeakHashMap
    ├── IdentityHashMap
    ├── EnumMap
    └── ConcurrentHashMap

List — упорядоченные коллекции

ArrayList — most common

List<String> names = new ArrayList<>();
names.add("Alice");           // O(1) amortized
names.get(0);                  // O(1)
names.remove(0);               // O(n) - requires shift
names.add(5, "Bob");           // O(n) - requires shift

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

• Частый доступ по индексу (get)
• Редкие операции удаления из середины
• Нужна динамическая реизменяемость

Реализация: динамический массив с увеличением на 50% при переполнении

LinkedList — двусвязный список

List<String> items = new LinkedList<>();
items.add("A");               // O(1)
items.addFirst("B");          // O(1) Deque
items.removeFirst();           // O(1)
for (String item : items) {}  // O(n) linear iteration

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

• Частое добавление/удаление в начало/конец (Deque)
• Редкие операции по индексу
• Очередь (Queue) или Стек (Deque)

Проблемы:

• Доступ по индексу O(n) — медленный
• Больше памяти на указатели

Set — уникальные элементы

HashSet — сбалансированная скорость

Set<String> users = new HashSet<>();
users.add("Alice");            // O(1) average
users.contains("Alice");       // O(1) average
users.remove("Alice");         // O(1) average

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

• Проверка наличия элемента (contains)
• Удаление дубликатов
• Порядок не важен

Внимание: порядок элементов не гарантирован

LinkedHashSet — с сохранением порядка

Set<String> ordered = new LinkedHashSet<>();
ordered.add("Charlie");
ordered.add("Alice");
ordered.add("Bob");
// Итерация в порядке добавления: Charlie -> Alice -> Bob

TreeSet — отсортированные элементы

Set<Integer> numbers = new TreeSet<>();
numbers.add(3);
numbers.add(1);
numbers.add(2);
// Итерация в порядке сортировки: 1, 2, 3

// Операции диапазона
Set<Integer> range = ((TreeSet<Integer>) numbers).subSet(1, 3); // [1, 2]

Сложность: все операции O(log n)

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

• Нужна отсортированность
• Диапазонные запросы (subSet, headSet, tailSet)
• Сравнительно небольшие наборы (медленнее HashSet)

Queue — очередь FIFO

PriorityQueue — приоритет

Queue<Task> tasks = new PriorityQueue<>((t1, t2) -> 
    Integer.compare(t1.priority, t2.priority));
tasks.add(new Task("urgent", 1));
tasks.add(new Task("normal", 3));

Task next = tasks.poll();  // вернёт task с priority 1

ArrayDeque — FIFO/LIFO, лучше чем LinkedList как Stack

Deque<String> stack = new ArrayDeque<>();
stack.push("A");            // O(1)
stack.push("B");
String top = stack.pop();   // O(1), returns "B"

Deque<String> queue = new ArrayDeque<>();
queue.addLast("1");
queue.addLast("2");
String first = queue.removeFirst(); // O(1), returns "1"

Map — пары ключ-значение

HashMap — most common

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 95);     // O(1) average
scores.get("Alice");          // O(1) average
scores.getOrDefault("Bob", 0); // O(1), returns 0

// Java 8+
scores.merge("Alice", 5, Integer::sum); // 95 + 5 = 100
scores.computeIfAbsent("Charlie", k -> 80);

Внимание: не потокобезопасна, порядок элементов не гарантирован

LinkedHashMap — с порядком вставки

Map<String, Integer> lru = new LinkedHashMap<String, Integer>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > 100;  // LRU cache реализация
    }
};

TreeMap — отсортирована по ключам

Map<Integer, String> sorted = new TreeMap<>();
sorted.put(3, "three");
sorted.put(1, "one");
// Итерация в порядке ключей: 1, 3

// Диапазонные операции
Map<Integer, String> range = sorted.subMap(1, 3);

ConcurrentHashMap — потокобезопасная

Map<String, Integer> concurrent = new ConcurrentHashMap<>();
concurrent.putIfAbsent("key", 1); // O(1) atomically
concurrent.computeIfPresent("key", (k, v) -> v + 1);

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

• Многопоточное приложение
• Нет необходимости в synchronized блоках
• Лучше, чем Collections.synchronizedMap()

Практические примеры

// Поиск дубликатов
public boolean hasDuplicates(List<Integer> numbers) {
    return new HashSet<>(numbers).size() != numbers.size();
}

// Top K элементов
public List<Integer> topK(List<Integer> nums, int k) {
    Queue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) minHeap.poll();
    }
    return new ArrayList<>(minHeap);
}

// Frequency counter
Map<String, Integer> frequency = new HashMap<>();
for (String word : words) {
    frequency.merge(word, 1, Integer::sum);
}

// Сортировка map по значениям
frequency.entrySet().stream()
    .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
    .forEach(e -> System.out.println(e.getKey() + ": " + e.getValue()));

Выбор правильной коллекции

Важные методы

// Collections утилиты
Collections.sort(list);              // сортировка
Collections.reverse(list);           // обращение
Collections.shuffle(list);           // перемешивание
Collections.binarySearch(list, key); // поиск (list должна быть отсортирована)
Collections.unmodifiableList(list);  // неизменяемая копия
Collections.synchronizedMap(map);    // потокобезопасная обёртка

// Stream API (Java 8+)
list.stream()
    .filter(x -> x > 5)
    .map(x -> x * 2)
    .collect(Collectors.toList());

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