С чего начинаются коллекции

# Основы Java Collections

Коллекции в Java — это фреймворк для хранения и манипулирования группами объектов. Они являются ключевым компонентом Java и позволяют работать с набором элементов эффективно и удобно.

Иерархия Collections Framework

Все коллекции построены на основе двух главных интерфейсов:

1. Collection<E>

Основной интерфейс, от которого наследуются большинство коллекций. Определяет базовые операции:

// Основные методы Collection
public interface Collection<E> extends Iterable<E> {
    boolean add(E e);
    boolean remove(Object o);
    boolean contains(Object o);
    int size();
    boolean isEmpty();
    Iterator<E> iterator();
    boolean addAll(Collection<? extends E> c);
    void clear();
}

2. Map<K,V>

Отдельная иерархия для хранения пар ключ-значение:

public interface Map<K,V> {
    V put(K key, V value);
    V get(Object key);
    V remove(Object key);
    boolean containsKey(Object key);
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K,V>> entrySet();
}

Три основные ветви Collection

List<E>

Упорядоченная коллекция, позволяет доступ по индексу.

// ArrayList — динамический массив
List<String> list = new ArrayList<>();
list.add("Java");      // O(1) amortized
list.add(0, "Python"); // O(n) — сдвиг элементов
String first = list.get(0); // O(1)

// LinkedList — двусвязный список
List<String> linked = new LinkedList<>();
linked.add("Java");    // O(1)
linked.get(0);        // O(n) — нужно пройти по ссылкам
linked.remove(0);     // O(1) на первом элементе, O(n) в середине

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

• ArrayList: частый доступ по индексу, редкие вставки в начало/середину
• LinkedList: частые вставки/удаления в начале, редкий прямой доступ

Set<E>

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

// HashSet — быстрый поиск, случайный порядок
Set<Integer> set = new HashSet<>();
set.add(1);
set.add(1);  // не добавится
set.contains(1); // O(1) в среднем

// TreeSet — упорядоченный, медленнее
Set<Integer> tree = new TreeSet<>();
tree.add(3);
tree.add(1);
tree.add(2); // автоматически отсортирован [1, 2, 3]

// LinkedHashSet — сохраняет порядок добавления
Set<Integer> linked = new LinkedHashSet<>();

Queue<E>

Очередь для обработки элементов в определённом порядке.

// FIFO (First In First Out)
Queue<String> queue = new LinkedList<>();
queue.offer("first");  // добавить в конец (enqueue)
queue.poll();          // удалить и вернуть из начала (dequeue)
queue.peek();          // посмотреть, не удаляя

// Deque — двусторонняя очередь
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("x");   // добавить в начало
deque.addLast("y");    // добавить в конец
deque.removeFirst();   // удалить из начала
deque.removeLast();    // удалить из конца

// PriorityQueue — приоритетная очередь
Queue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);
pq.poll(); // вернёт 1 (наименьший элемент)

Map коллекции

// HashMap — быстрый, случайный порядок
Map<String, Integer> map = new HashMap<>();
map.put("John", 30);
map.get("John");       // O(1) в среднем
map.containsKey("John"); // O(1) в среднем

// TreeMap — упорядоченный по ключам
Map<String, Integer> tree = new TreeMap<>();
tree.put("Zoe", 25);
tree.put("Alice", 30); // отсортируется по ключам

// LinkedHashMap — сохраняет порядок добавления
Map<String, Integer> linked = new LinkedHashMap<>();

Итератор

Основной способ обхода коллекций:

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

// Способ 1: Iterator (безопасен для удаления)
Iterator<String> it = list.iterator();
while(it.hasNext()) {
    String item = it.next();
    if(item.equals("B")) {
        it.remove(); // безопасно
    }
}

// Способ 2: for-each
for(String item : list) {
    System.out.println(item);
}

// Способ 3: stream
list.forEach(System.out::println);

Сложность операций

*O(1) amortized — иногда O(n) при расширении массива

Выбор коллекции

1. ArrayList — по умолчанию для списков
2. HashSet — для уникальных элементов без порядка
3. HashMap — для пар ключ-значение
4. LinkedList — редко, для частых вставок в начало
5. TreeSet/TreeMap — если нужен порядок и операции по диапазону
6. PriorityQueue — для приоритетной обработки

Synchronized коллекции

Для многопоточности:

// Старый способ (не рекомендуется)
List<String> syncList = Collections.synchronizedList(new ArrayList<>());

// Современный подход
List<String> concurrentList = new CopyOnWriteArrayList<>();
Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();