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

Критерии выбора коллекции для конкретной задачи

Материалы

Алгоритм выбора коллекции

Шаг 1: Определить тип коллекции

Нужна пара ключ-значение? 
    → Map (HashMap, TreeMap, LinkedHashMap)

Нужны уникальные элементы?
    → Set (HashSet, TreeSet, LinkedHashSet)

Нужна очередь/стек?
    → Queue/Deque (ArrayDeque, PriorityQueue, LinkedList)

Нужен список с индексацией?
    → List (ArrayList, LinkedList)

Критерий 1: Операции доступа

Частый доступ по индексу

Требование: get(index) должен быть быстрым

✅ ArrayList

• O(1) доступ по индексу
• Компактное хранение в памяти

❌ LinkedList

• O(n) доступ по индексу
• Нужно проходить по узлам

// Если часто делаем list.get(i)
List<String> data = new ArrayList<>();  // ✅
List<String> data = new LinkedList<>(); // ❌

Частый поиск элемента

Требование: contains(element) должен быть быстрым

✅ HashSet / HashMap

• O(1) проверка наличия элемента

❌ ArrayList / LinkedList

• O(n) линейный поиск

// Если часто проверяем "есть ли элемент"
Set<String> users = new HashSet<>();    // ✅ O(1)
List<String> users = new ArrayList<>(); // ❌ O(n)

if (users.contains("John")) { ... }

Критерий 2: Операции модификации

Частые вставки/удаления в начале или середине

Требование: модификация в произвольных местах

✅ LinkedList

• O(1) вставка/удаление при наличии итератора
• O(n) поиск позиции

❌ ArrayList

• O(n) вставка/удаление (сдвиг элементов)

// Частые вставки в начало
List<String> buffer = new LinkedList<>();  // ✅
buffer.add(0, "new item"); // O(1)

List<String> buffer = new ArrayList<>();   // ❌
buffer.add(0, "new item"); // O(n) - сдвигает все элементы

Только добавление в конец

Требование: add(element) в конец списка

✅ ArrayList

• O(1) амортизированное добавление
• Компактнее в памяти

// Накапливаем результаты последовательно
List<Result> results = new ArrayList<>();  // ✅
for (...) {
    results.add(compute());
}

Частые добавления И удаления с обоих концов

Требование: операции с головой и хвостом

✅ ArrayDeque

• O(1) для операций с обоих концов
• Быстрее LinkedList

// Очередь задач или стек вызовов
Deque<Task> taskQueue = new ArrayDeque<>();  // ✅
taskQueue.addFirst(urgentTask);   // O(1)
taskQueue.addLast(normalTask);    // O(1)
taskQueue.pollFirst();            // O(1)

Критерий 3: Порядок элементов

Порядок не важен

✅ HashSet / HashMap

• Максимальная производительность
• Нет накладных расходов на поддержку порядка

Set<String> uniqueWords = new HashSet<>();  // ✅ Самый быстрый

Нужен порядок вставки (insertion order)

✅ LinkedHashSet / LinkedHashMap

• Предсказуемый порядок итерации
• Небольшие накладные расходы

// История посещенных страниц - порядок важен
Set<String> visitedPages = new LinkedHashSet<>();  // ✅
visitedPages.add("/home");
visitedPages.add("/products");
// Итерация в порядке добавления

Нужна сортировка (natural или custom order)

✅ TreeSet / TreeMap

• Автоматическая сортировка
• O(log n) операции

// Топ игроков по очкам - всегда отсортировано
Set<Player> leaderboard = new TreeSet<>(
    Comparator.comparing(Player::getScore).reversed()
);  // ✅

leaderboard.add(new Player("Alice", 100));
leaderboard.add(new Player("Bob", 150));
// Автоматически отсортировано по убыванию очков

Нужна сортировка + операции навигации

✅ TreeSet / TreeMap

• Методы lower(), higher(), floor(), ceiling()

TreeSet<Integer> prices = new TreeSet<>();
prices.add(100);
prices.add(200);
prices.add(300);

// Найти ближайшую цену <= 250
Integer nearestPrice = prices.floor(250); // 200  ✅

Критерий 4: Уникальность элементов

Дубликаты разрешены

✅ List (ArrayList, LinkedList)

List<String> tags = new ArrayList<>();  // ✅
tags.add("java");
tags.add("java");  // OK, дубликат разрешен

Только уникальные элементы

✅ Set (HashSet, TreeSet, LinkedHashSet)

Set<String> uniqueTags = new HashSet<>();  // ✅
uniqueTags.add("java");
uniqueTags.add("java");  // Не добавится
// size = 1

Критерий 5: Null-элементы

Null разрешен

✅ ArrayList, LinkedList, HashSet, LinkedHashSet, HashMap, LinkedHashMap

List<String> items = new ArrayList<>();
items.add(null);  // ✅ OK

Set<String> set = new HashSet<>();
set.add(null);  // ✅ OK (только один null)

Null запрещен

❌ TreeSet, TreeMap, ArrayDeque, PriorityQueue

• Бросят NullPointerException

Set<String> sorted = new TreeSet<>();
sorted.add(null);  // ❌ NullPointerException

Queue<String> queue = new ArrayDeque<>();
queue.add(null);  // ❌ NullPointerException

Критерий 6: Многопоточность

Однопоточное использование

✅ Обычные коллекции (ArrayList, HashSet и т.д.)

• Максимальная производительность
• Без синхронизации

Многопоточное использование - частые чтения, редкие записи

✅ CopyOnWriteArrayList / CopyOnWriteArraySet

• Итерация без блокировки
• Модификации дорогие (копирование массива)

// Список слушателей событий - редко меняется, часто читается
List<EventListener> listeners = new CopyOnWriteArrayList<>();  // ✅

// В любом потоке можно итерировать без locks
for (EventListener listener : listeners) {
    listener.onEvent(event);  // Безопасно
}

Многопоточное использование - частые чтения И записи

✅ ConcurrentHashMap

• Lock-free чтение
• Сегментированная блокировка записи
• Высокая параллельность

// Кэш - частые чтения и записи из разных потоков
Map<String, User> userCache = new ConcurrentHashMap<>();  // ✅

// Поток 1
userCache.put("user123", user);

// Поток 2
User u = userCache.get("user123");  // Безопасно, быстро

❌ Синхронизированные обертки (для совместимости)

// Устаревший подход - ниже производительность
Map<String, String> map = Collections.synchronizedMap(new HashMap<>());  // ❌

Producer-Consumer паттерн

✅ BlockingQueue (LinkedBlockingQueue, ArrayBlockingQueue)

• Автоматическая блокировка при пустой/полной очереди
• Идеально для producer-consumer

// Очередь задач между потоками
BlockingQueue<Task> taskQueue = new LinkedBlockingQueue<>(100);  // ✅

// Producer thread
taskQueue.put(task);  // Блокируется если очередь полная

// Consumer thread
Task task = taskQueue.take();  // Блокируется если очередь пустая

Критерий 7: Размер коллекции

Известный размер заранее

Оптимизация: указать начальную ёмкость

// Плохо - много перевыделений
List<String> items = new ArrayList<>();  // capacity = 10
for (int i = 0; i < 10000; i++) {
    items.add("item" + i);  // Много раз расширяется
}

// Хорошо - одно выделение
List<String> items = new ArrayList<>(10000);  // ✅
for (int i = 0; i < 10000; i++) {
    items.add("item" + i);
}

Маленькая коллекция (< 10 элементов)

Оптимизация: меньше значения коэффициента загрузки для HashMap

// По умолчанию: initialCapacity=16, loadFactor=0.75
Map<String, String> config = new HashMap<>();  // 16 слотов для 3 элементов

// Оптимизировано для малых коллекций
Map<String, String> config = new HashMap<>(4, 1.0f);  // ✅ 4 слота

Очень большая коллекция (миллионы элементов)

Соображения:

• Избегать ArrayList для очень больших размеров (проблемы с перевыделением)
• Рассмотреть сторонние библиотеки (Trove, Fastutil) для примитивов
• Использовать потоковую обработку вместо загрузки всего в память

Критерий 8: Приоритет обработки

FIFO (First-In-First-Out) - обычная очередь

✅ LinkedList или ArrayDeque как Queue

Queue<Task> fifoQueue = new ArrayDeque<>();  // ✅
fifoQueue.offer(task1);
fifoQueue.offer(task2);
fifoQueue.poll();  // task1 (первый добавленный)

LIFO (Last-In-First-Out) - стек

✅ ArrayDeque как Stack

Deque<String> stack = new ArrayDeque<>();  // ✅
stack.push("first");
stack.push("second");
stack.pop();  // "second" (последний добавленный)

Обработка по приоритету

✅ PriorityQueue

// Задачи с приоритетом
Queue<Task> priorityQueue = new PriorityQueue<>(
    Comparator.comparing(Task::getPriority).reversed()
);  // ✅

priorityQueue.offer(new Task(priority: 5));
priorityQueue.offer(new Task(priority: 10));
priorityQueue.poll();  // Task с priority=10 (наивысший)

Сравнительная таблица по критериям

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

Пример 1: Список пользователей для отображения

Требования:

• Нужен порядок вставки
• Доступ по индексу для пагинации
• Дубликаты возможны

Выбор: ✅ ArrayList

List<User> users = new ArrayList<>();

Пример 2: Уникальные посетители сайта

Требования:

• Только уникальные ID
• Быстрая проверка “был ли пользователь”
• Порядок не важен

Выбор: ✅ HashSet

Set<String> uniqueVisitors = new HashSet<>();
if (!uniqueVisitors.contains(userId)) {
    uniqueVisitors.add(userId);
    // Первый визит
}

Пример 3: История команд (undo/redo)

Требования:

• LIFO для undo
• Операции только на концах

Выбор: ✅ ArrayDeque

Deque<Command> undoStack = new ArrayDeque<>();
Deque<Command> redoStack = new ArrayDeque<>();

// Undo
Command cmd = undoStack.pop();
cmd.undo();
redoStack.push(cmd);

Пример 4: Топ игроков (рейтинг)

Требования:

• Автоматическая сортировка по очкам
• Нужны операции: лучший, худший, позиция игрока

Выбор: ✅ TreeSet с кастомным компаратором

TreeSet<Player> leaderboard = new TreeSet<>(
    Comparator.comparing(Player::getScore)
              .reversed()
              .thenComparing(Player::getName)
);

Пример 5: Кэш с LRU

Требования:

• Отслеживание порядка использования
• Быстрый доступ по ключу
• Удаление самого старого

Выбор: ✅ LinkedHashMap с accessOrder=true

Map<String, Data> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Data> eldest) {
        return size() > MAX_ENTRIES;
    }
};

Пример 6: Буфер событий между потоками

Требования:

• Многопоточность
• Producer-Consumer
• Ограниченный размер

Выбор: ✅ ArrayBlockingQueue

BlockingQueue<Event> eventBuffer = new ArrayBlockingQueue<>(1000);

// Producer
eventBuffer.put(event);

// Consumer
Event event = eventBuffer.take();

Пример 7: Слова в тексте по частоте

Требования:

• Подсчет уникальных слов
• Сортировка по частоте

Решение: HashMap + PriorityQueue или TreeMap

// Подсчет
Map<String, Integer> wordCount = new HashMap<>();
for (String word : words) {
    wordCount.merge(word, 1, Integer::sum);
}

// Топ N слов
PriorityQueue<Map.Entry<String, Integer>> topWords = new PriorityQueue<>(
    Map.Entry.comparingByValue(Comparator.reverseOrder())
);
topWords.addAll(wordCount.entrySet());

Чек-лист выбора коллекции

Вопросы для принятия решения:

1. Структура данных:

   • Нужна пара ключ-значение? → Map
   • Нужны только уникальные элементы? → Set
   • Нужна очередь/стек? → Queue/Deque
   • Нужен список с индексами? → List

2. Операции:

   • Частый доступ по индексу? → ArrayList
   • Частая проверка наличия? → HashSet/HashMap
   • Частые вставки/удаления в начале? → LinkedList/ArrayDeque
   • Только добавление в конец? → ArrayList

3. Порядок:

   • Порядок не важен? → HashSet/HashMap
   • Нужен порядок вставки? → LinkedHashSet/LinkedHashMap
   • Нужна автосортировка? → TreeSet/TreeMap

4. Дополнительно:

   • Нужны null-элементы? → избегай TreeSet/TreeMap/ArrayDeque
   • Многопоточность? → Concurrent коллекции
   • Известен размер? → укажи initialCapacity
   • Нужен приоритет? → PriorityQueue

Антипаттерны и частые ошибки

❌ Использование LinkedList без причины

// Плохо - LinkedList медленнее в большинстве случаев
List<String> items = new LinkedList<>();
for (int i = 0; i < items.size(); i++) {
    process(items.get(i));  // O(n²) !
}

❌ Неправильный выбор для поиска

// Плохо - поиск в списке O(n)
List<String> users = new ArrayList<>();
if (users.contains("john")) { ... }  // Медленно!

// Хорошо - поиск в set O(1)
Set<String> users = new HashSet<>();
if (users.contains("john")) { ... }  // Быстро!

❌ Игнорирование initial capacity

// Плохо - много перевыделений памяти
Map<String, String> map = new HashMap<>();
for (int i = 0; i < 100000; i++) {
    map.put("key" + i, "value" + i);
}

// Хорошо
Map<String, String> map = new HashMap<>(100000);

❌ Использование устаревших классов

// Устарело
Vector<String> vector = new Vector<>();      // → ArrayList
Stack<String> stack = new Stack<>();         // → ArrayDeque  
Hashtable<String, String> table = new Hashtable<>();  // → HashMap

❌ Ручная синхронизация вместо concurrent

// Плохо - грубая синхронизация
Map<String, String> map = Collections.synchronizedMap(new HashMap<>());

synchronized (map) {
    map.forEach((k, v) -> process(k, v));
}

// Хорошо - lock-free
ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
map.forEach((k, v) -> process(k, v));  // Безопасно без locks

Итоговые рекомендации

По умолчанию используй:

• List → ArrayList (самый частый случай)
• Set → HashSet (самый быстрый)
• Queue → ArrayDeque (быстрее LinkedList)
• Map → HashMap (самый быстрый)

Специальные случаи:

• Нужна сортировка → TreeSet / TreeMap
• Нужен порядок вставки → LinkedHashSet / LinkedHashMap
• Многопоточность → ConcurrentHashMap / CopyOnWriteArrayList
• Producer-Consumer → BlockingQueue
• Приоритеты → PriorityQueue
• Вставки в начало → LinkedList / ArrayDeque

Правило оптимизации:

Сначала выбирай правильную структуру данных (Set vs List vs Map),
потом выбирай реализацию (HashSet vs TreeSet),
потом оптимизируй (указывай initialCapacity).