tgoop.com/javaproglib/6957
Last Update:
Часто выбор коллекции ограничивается только таблицей сложностей и на этом всё.
Но реальный кейс сложнее: средняя сложность ≠ реальная скорость в продакшне. JVM, кэш процессора, GC и паттерны доступа могут радикально поменять картину.
🔑 Главная мысль
Выбирайте коллекцию под сценарий использования, а не “по самой быстрой ячейке в таблице”.
ArrayList хранит элементы в массиве → локальность памяти + CPU кэш → итерации летят.
Вставка в середину за O(n), но при небольших списках разница с LinkedList исчезающе мала.
🔧 Паттерн использования:
— 90% чтение, редкие вставки → идеально.
— Если заранее известно примерное кол-во элементов → задайте initialCapacity, иначе ArrayList будет несколько раз пересоздавать массив (copy O(n) на каждом росте).
В бенчмарках JMH даже при вставке в середину ArrayList часто быстрее LinkedList просто потому, что LinkedList платит за “pointer chasing” (скачки по памяти, cache-miss).
Да, вставка/удаление в начало или конец за O(1).
Но get(i) = O(n), и каждый шаг = новый объект, новая ссылка → нагрузка на GC.
🔧 Паттерн использования:
— Когда нужна двусторонняя очередь с частыми удалениями/добавлениями в начало и конец.
— Во всех остальных случаях лучше ArrayDeque, он без лишних объектов и быстрее почти всегда.
LinkedList ест больше памяти: на каждый элемент два указателя + объект-узел.
HashMap даёт O(1) доступ при хорошем hashCode().
Но:
— Если хэши “плохие” → коллизии → O(log n)
— При достижении load factor 0.75 → resize → перераспределение всех бакетов (дорогая операция).
🔧 Паттерн использования:
— Когда нужен быстрый поиск по ключу без сохранения порядка или когда важно хранить уникальные элементы или строить словари/кэши по ключу.
— Если знаете примерное кол-во элементов → сразу задайте кол-во элементов в конструкторе new HashMap<>(N).
Начиная с Java 8 при коллизии, когда LinkedList становится длинным (по умолчанию ≥ 8 элементов) → список превращается в красно-чёрное дерево.
Дают O(log n) доступ и всегда хранят ключи отсортированными.
Но если сортировка нужна редко, дешевле собрать HashMap и вызвать sorted() на стриме.
🔧 Паттерн использования:
— Когда важно поддерживать сортировку на каждой операции (напр. Top-N задач в приоритетной очереди).
— Не храните mutable-ключи, т.к. можно “потерять” элемент при изменении поля, участвующего в compareTo.
TreeMap хранит узлы с балансировкой (красно-чёрное дерево) → накладные расходы на память + сравнения ключей.
LinkedHashMap поддерживает порядок вставки или порядок доступа (accessOrder=true).
Можно сделать LRU-кэш, переопределив removeEldestEntry.
🔧 Паттерн использования:
— Когда важен порядок, но сортировка не нужна.
— Когда нужно легко реализовать ограниченный кэш.
Каждый get() в режиме accessOrder вызывает перестановку в двусвязном списке → небольшие накладные расходы.
#CoreJava
