Java Collections Framework

Collections Framework — это стандартная библиотека структур данных Java: единый набор интерфейсов (List, Set, Map, Queue), их готовых реализаций (ArrayList, HashMap, TreeSet и другие) и переиспользуемых алгоритмов в утилитном классе Collections. Один согласованный API позволяет менять реализацию, не переписывая вызывающий код — объявляете переменную как List<T>, а под капотом держите ArrayList или LinkedList, и выбор становится решением о производительности, а не о синтаксисе.

Собеседование по коллекциям почти всегда проверяет не знание имён классов, а модель их внутреннего устройства — какая операция стоит O(1), а какая O(n), где массив, а где узлы и указатели, кто синхронизирован, кто допускает null. Кандидат, который объясняет выбор ArrayList через «O(1) доступ по индексу, но O(n) вставка в середину», сразу выделяется на фоне «ну, это список». Полная карта — в слоях ниже.

Карта темы

• Collections Framework — два корня иерархии Collection и Map и связка «интерфейс — реализация — алгоритм».
• ArrayList и LinkedList — динамический массив против двусвязного списка и их Big-O по операциям.
• ArrayList и Vector — почему Vector синхронизирован на каждом методе и потому устарел.
• Set против List — уникальность и правила порядка против позиционной последовательности с дублями.
• HashSet и TreeSet — хеш-таблица O(1) без порядка против красно-чёрного дерева O(log n) с сортировкой.
• HashMap и Hashtable — null, синхронизация и почему Hashtable — legacy.
• Устройство HashMap — бакеты, loadFactor, resize и превращение бакета в дерево при 8 записях.
• Comparable и Comparator — единственный естественный порядок против множества внешних.
• Collection и Collections — корневой интерфейс против финального утилитного класса.
• Выбор структуры данных — от требований задачи к конкретной реализации коллекции.

Частые ошибки и ловушки

Значение для собеседований

Коллекции спрашивают почти на каждом Java-интервью, но проверяют модель, а не факты — асимптотику операций, внутреннее устройство и правила null/синхронизации/порядка. Сильный ответ всегда привязывает выбор к стоимости операций.

Что обычно проверяют:

• Big-O доступа, вставки и удаления для ArrayList, LinkedList, HashMap, TreeMap.
• Устройство HashMap — бакеты, коллизии, loadFactor, resize, treeify с Java 8.
• Разницу HashMap/Hashtable и ArrayList/Vector по синхронизации и null.
• Comparable против Comparator и контракт метода compareTo.
• Когда брать Set, когда List, когда Map, а когда очередь.

Типичный неверный ответ: «LinkedList быстрее ArrayList, потому что не копирует массив». Это открывает разговор о том, что произвольный доступ у LinkedList — O(n), кэш-локальность массива обычно перевешивает, и на реальных нагрузках ArrayList чаще оказывается быстрее.