Всем привет, меня зовут Сергей Прощаев, и в этой статье я расскажу про коллекции в Java и их алгоритмическую сложность. В этой статье мы разберём, что это такое применительно к коллекциям Java, сравним популярные реализации и я покажу, как правильный выбор может ускорить ваш код в сотни раз. А в конце — небольшая история про баг, который чуть не ушёл в прод из-за неправильного hashCode().
Алгоритмическая сложность: нужен ли нам этот «Big O»?
Если кратко: Big O описывает, как быстро растёт время выполнения операции (или потребление памяти) при увеличении количества элементов в коллекции. Это не точная цифра в миллисекундах, а асимптотическая оценка. Например, O(1) — значит, время константно и не зависит от размера коллекции. O(n) — время линейно растёт с ростом n.
Для меня это как дорожная карта: я сразу понимаю, что можно делать с коллекцией без страха, а что — только в крайнем случае. Дальше мы посмотрим на конкретные цифры для основных коллекций.
Списочные структуры: ArrayList и LinkedList
ArrayList
Внутри — обычный массив, который пересоздаётся при заполнении. Доступ по индексу — O(1) (мгновенно). Вставка в конец — в среднем O(1), но иногда требует расширения массива (тогда O(n) на копирование). Вставка в середину или начало — O(n), так как нужно сдвигать все последующие элементы. Поиск элемента по значению (contains) — O(n).
Когда следует использовать: почти всегда, если вам нужен список. Отлично подходит для доступа по индексу, итераций, операций в конце.
LinkedList
Двунаправленный список из узлов. Доступ по индексу — O(n) (нужно пройти от начала или конца). Вставка/удаление в начале или конце — O(1), если уже есть ссылка на узел. В середине — тоже O(n) из-за поиска позиции. Поиск элемента — O(n).
Когда следует использовать: если вы часто вставляете/удаляете в начале списка и при этом редко обращаетесь по индексу. На практике таких сценариев немного. Например, реализация очереди или дека. В современной Java лучше использовать ArrayDeque — он быстрее за счёт кэш-локальности.
Множества: HashSet, TreeSet, LinkedHashSet
HashSet
Основан на HashMap. Элементы хранятся как ключи мапы. Вставка, удаление, поиск — O(1) в среднем, но при плохой хеш-функции может деградировать до O(n). Важно правильно переопределять hashCode() и equals().
Когда брать: когда нужен набор уникальных элементов без порядка. Лучший выбор для операций contains.
TreeSet
Реализован как красно-чёрное дерево. Элементы хранятся отсортированными. Операции add, remove, contains — O(log n). Поддерживает навигационные методы (first, last, headSet и т.д.).
Когда брать: если важен естественный порядок или нужны операции с диапазонами. Но платим за это логарифмической сложностью.
LinkedHashSet
Гибрид: поддерживает порядок вставки с помощью связного списка. Сложность как у HashSet, но чуть дороже память. Когда нужно сохранить порядок добавления.
Мап-ы: HashMap, TreeMap, LinkedHashMap
Аналогично множествам: HashMap — O(1), TreeMap — O(log n), LinkedHashMap — O(1) с порядком вставки.
Ключевой момент для HashMap: хеш-функция должна быть качественной. Если все ключи попадают в один бакет (например, одинаковый hashCode), HashMap превращается в связанный список — сложность операций падает до O(n). В Java 8+ при большом размере бакета список преобразуется в дерево (порог 8), что улучшает производительность до O(log n), но это скорее защита от атак.
Схема выбора коллекции
Чтобы наглядно представить, как выбирать коллекцию — нарисовал небольшую блок-схему с использованием Mermaid, изображенную на рисунке 1. Сохраните её себе — помогает не запутаться:
Эта схема — упрощение, но для повседневных задач работает отлично. Конечно, если вам нужна карта (ключ-значение), то аналогично: HashMap, TreeMap, LinkedHashMap.
Best Practices при работе с коллекциями
Помните о правилах, которые помогают избежать сложности при работе с коллекциями:
1. Выбирайте интерфейс, а не реализацию
В коде используйте List<String> list = new ArrayList<>();, а не ArrayList<String> list = .... Это даёт гибкость сменить реализацию позже, если понадобится.
// Плохо: привязка к конкретной реализации ArrayList<String> badList = new ArrayList<>(); // Хорошо: программируем на уровень интерфейса List<String> goodList = new ArrayList<>(); // Теперь легко сменить реализацию, например, на LinkedList: // List<String> goodList = new LinkedList<>();
2. Для пустых коллекций возвращайте Collections.emptyList(), emptySet(), emptyMap()
Это экономит память и делает код чище. Главное — помнить, что такие коллекции неизменяемы.
public List<String> getNames() { if (someCondition) { return listOfNames; } // Вместо return null; или return new ArrayList<>(); return Collections.emptyList(); // неизменяемая, но пустая } // Использование: (безопасно, даже если пусто) List<String> names = getNames(); for (String name : names) { System.out.println(name); }
3. Инициализируйте с ожидаемым размером.
Если вы знаете, что в HashMap будет 10 000 элементов, создавайте её с new HashMap<>(16_000) (примерно с запасом). Это уменьшит количество перехеширований и ускорит вставку.
// Плохо: без указания размера HashMap начнёт с 16, потом будет многократно расширяться Map<String, User> badMap = new HashMap<>(); // Хорошо: сразу задаём ожидаемую ёмкость int expectedSize = 10_000; Map<String, User> goodMap = new HashMap<>(expectedSize * 2); // часто берут с запасом // Для ArrayList тоже полезно: List<Integer> list = new ArrayList<>(1_000_000); // если знаем, что будет миллион элементов
4. Используйте итераторы для безопасного удаления во время обхода.
Никогда не удаляйте элементы из ArrayList в цикле for-each — получите ConcurrentModificationException. Либо используйте итератор, либо removeIf()
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C", "B")); // Ошибка: ConcurrentModificationException for (String s : list) { if (s.equals("B")) { list.remove(s); // НЕЛЬЗЯ! } } // Вариант 1: явный итератор Iterator<String> iterator = list.iterator(); while (iterator.hasNext()) { String s = iterator.next(); if (s.equals("B")) { iterator.remove(); // безопасно } } // Вариант 2: removeIf (Java 8+) list.removeIf(s -> s.equals("B"));
5. Для сортировки своих объектов реализуйте Comparable или используйте Comparator
Тогда TreeSet и TreeMap будут работать корректно, а сортировка списков (Collections.sort) будет эффективна.
class Person implements Comparable<Person> { private final String name; private final int age; // конструктор, геттеры @Override public int compareTo(Person other) { // Сначала по имени, потом по возрасту int nameCmp = this.name.compareTo(other.name); if (nameCmp != 0) return nameCmp; return Integer.compare(this.age, other.age); } } // Использование: List<Person> people = Arrays.asList(new Person("Alice", 30), new Person("Bob", 25)); Collections.sort(people); // использует compareTo // Или с компаратором: people.sort(Comparator.comparing(Person::getAge)); // по возрасту
6. Профилируйте!
Даже зная теорию, всегда проверяйте предположения под нагрузкой. Бывает, что микрооптимизации на основе Big O не дают эффекта из-за накладных расходов. Но в 90% случаев математика побеждает.
Вот простейший способ быстро проверить гипотезу:
long start = System.nanoTime(); // код, который тестируем (например, contains для разных коллекций) long end = System.nanoTime(); System.out.println("Время: " + (end - start) + " нс");
Для серьёзных замеров используйте JMH (Java Microbenchmark Harness), но на первое время хватит и простых приблизительных замеров. Главное — не делать по одному прогону, а прогревать JVM и усреднять результаты.
А что насчёт обычного массива?
Мы так увлеклись коллекциями, что чуть не забыли про фундамент — обычные массивы. Иногда они оказываются самым эффективным решением. Да, коллекции удобны, но за удобство приходится платить.
Когда массив выигрывает
Скорость доступа. Массив даёт прямой доступ к элементу по индексу за константное время, причём без накладных расходов на вызовы методов. Операция array[i] выполняется быстрее, чем list.get(i), потому что в последнем есть проверка границ, вызов метода и, возможно, приведение типа. В критических участках это может дать ощутимый прирост.
Память. Массив с примитивами (int[], double[]) хранит значения непосредственно, а коллекция — объекты-обёртки (Integer, Double). Это значит, что массив из 1 миллиона int займёт ~4 МБ, а ArrayList<Integer> — минимум 16 МБ + память под объекты. Упаковка (boxing) и распаковка тоже отнимают время.
Предсказуемость. Размер массива фиксирован, нет операций расширения, копирования, перехеширования. Если вы точно знаете количество элементов — массив будет идеальным выбором.
Но не всё так просто с массивами
Массивы не умеют динамически расширяться, у них нет удобных методов contains, remove, итераторов. Поэтому я обычно придерживаюсь правила: использую массив только внутри критических по производительности методов или при работе с примитивами, а наружу отдаю неизменяемую коллекцию или список.
Пример:
public List<Integer> getProcessedData() { int[] raw = processInternal(); // внутри метода массив return Arrays.stream(raw).boxed().collect(Collectors.toList()); }
Если размер известен и не меняется — смело берите массив. Если нужна гибкость — коллекции. А если нужна максимальная производительность на примитивах — присмотритесь к библиотекам вроде fastutil или Eclipse Collections, которые предоставляют коллекции для примитивов без boxing'а.
Так что, когда в следующий раз будете выбирать между ArrayList и LinkedList, вспомните: возможно, вам вообще не нужна коллекция. Обычный массив может оказаться лучшим вариантом!
Заключение
Мы разобрали основные коллекции Java и их алгоритмическую сложность. Надеюсь, теперь вы будете осознанно подходить к выбору, особенно когда речь идёт о больших объёмах данных. Помните, что правильный выбор структуры данных может ускорить программу на порядки.
Если хотите системно закрыть базу, на курсе «Разработчик на Java. Базовый уровень» собираем фундамент разработчика: Java, алгоритмы и структуры данных, базы данных, тестирование и основы архитектуры. Разбираем типовые ошибки, которые потом превращаются в «почему тормозит», и учимся диагностировать их руками.
Для знакомства с форматом обучения и экспертами приходите на бесплатные уроки:
