Какие знаешь типы коллекций?

Типы коллекций в Java

Ява предоставляет богатый набор коллекций (Collections Framework) для работы с группами объектов. Все коллекции находятся в пакете java.util и построены на иерархии интерфейсов.

Иерархия Collections Framework

Iterable
└── Collection
    ├── List (упорядоченные, дубликаты разрешены)
    │   ├── ArrayList
    │   ├── LinkedList
    │   └── Vector (устаревший)
    ├── Set (уникальные элементы, без упорядочения)
    │   ├── HashSet
    │   ├── LinkedHashSet
    │   └── TreeSet
    └── Queue (очередь, FIFO)
        ├── PriorityQueue
        └── Deque (двусторонняя очередь)

Map (ключ-значение, отдельная иерархия)
├── HashMap
├── LinkedHashMap
├── TreeMap
└── Hashtable (устаревший)

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

ArrayList — динамический массив, базовая реализация:

List<String> list = new ArrayList<>();
list.add("Java");      // Добавление
list.add(1, "Python"); // Вставка по индексу
list.get(0);           // Получение O(1)
list.remove(0);        // Удаление O(n)

// Особенности:
// - Быстрый доступ по индексу O(1)
// - Медленные вставки/удаления в начале/середине O(n)
// - Thread-safe версия: Collections.synchronizedList()

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

List<String> list = new LinkedList<>();
list.add("first");
list.addFirst("zero");  // O(1) добавление в начало
list.addLast("last");   // O(1) добавление в конец
list.removeFirst();     // O(1) удаление из начала
list.removeLast();      // O(1) удаление из конца

// Особенности:
// - O(1) добавление/удаление в начале/конце
// - O(n) доступ по индексу
// - Используется как очередь или дек

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

HashSet — быстрое добавление и проверка наличия:

Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.add(1);     // Не добавится
set.contains(1); // true, O(1)
set.remove(1);  // O(1)

// Особенности:
// - Основан на HashMap
// - Нет гарантии порядка элементов
// - O(1) add, remove, contains
// - Требует хорошей реализации hashCode() и equals()

TreeSet — упорядоченное хранилище:

Set<Integer> set = new TreeSet<>();
set.add(5);
set.add(2);
set.add(8);
// Элементы отсортированы: [2, 5, 8]

set.first();    // 2
set.last();     // 8
set.headSet(5); // {2} — элементы < 5
set.tailSet(5); // {5, 8} — элементы >= 5

// Особенности:
// - Упорядочено по компаратору (натурально или кастомно)
// - O(log n) add, remove, contains
// - Требует реализации Comparable или Comparator

LinkedHashSet — предсказуемый порядок:

Set<Integer> set = new LinkedHashSet<>();
set.add(5);
set.add(2);
set.add(8);
// Порядок вставки: [5, 2, 8]

// Особенности:
// - Хранит порядок вставки
// - O(1) операции (как HashSet)
// - Чуть медленнее HashSet из-за поддержки порядка

Queue — очередь (FIFO)

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);    // Добавить в конец
queue.offer(2);
queue.offer(3);

queue.poll();      // Удалить из начала (1)
queue.peek();      // Посмотреть начало (2)
queue.poll();      // Удалить (2)

// Методы queue:
// offer(E) — add с возвратом boolean
// poll() — удалить и вернуть, или null
// peek() — посмотреть, или null
// remove() — удалить, выбросить исключение
// element() — посмотреть, выбросить исключение

Deque — двусторонняя очередь

Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);
deque.addLast(2);
deque.addLast(3);

deque.removeFirst();  // 1
deque.removeLast();   // 3

// Используется как Stack:
deque.push(10);       // Добавить в начало
deque.pop();          // Удалить из начала
deque.peek();         // Посмотреть начало

PriorityQueue — приоритетная очередь

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(10);

pq.poll();  // 1 (минимальный элемент)
pq.poll();  // 5
pq.poll();  // 10

// С кастомным компаратором (максимальный элемент):
PriorityQueue<Integer> maxPq = new PriorityQueue<>(
    (a, b) -> b.compareTo(a)
);

// Особенности:
// - На основе двоичной кучи (heap)
// - O(log n) add, remove
// - O(1) peek (посмотреть минимум)

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

HashMap — быстрый доступ по ключу:

Map<String, Integer> map = new HashMap<>();
map.put("Java", 8);
map.put("Python", 7);

map.get("Java");       // 8, O(1)
map.containsKey("C++"); // false
map.remove("Python");  // O(1)

// Итерация:
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

TreeMap — упорядоченное хранилище:

Map<String, Integer> map = new TreeMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);
// Порядок ключей: A, B, C

map.firstKey();    // A
map.lastKey();     // C
map.subMap("A", "C"); // {A=1, B=2}

LinkedHashMap — порядок вставки или доступа:

// Порядок вставки
Map<String, Integer> map = new LinkedHashMap<>();
map.put("B", 2);
map.put("A", 1);
// Порядок: B, A

// Порядок доступа (LRU cache)
Map<String, Integer> lruMap = new LinkedHashMap<String, Integer>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > 3;  // Максимум 3 элемента
    }
};

Сравнение производительности

*LinkedList — O(1) только в начале/конце

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

• Быстрый доступ по индексу? → ArrayList
• Много вставок/удалений в начале/конце? → LinkedList
• Уникальные элементы, быстрая проверка? → HashSet
• Упорядоченные уникальные элементы? → TreeSet
• Ключ-значение, быстрый доступ? → HashMap
• Упорядоченные пары ключ-значение? → TreeMap
• Приоритетная обработка? → PriorityQueue

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