Иерархия коллекций

Иерархия Java Collections Framework

Карта интерфейсов

Java Collections Framework объединяет интерфейсы, реализации и алгоритмы из java.util.

Iterable
└── Collection
    ├── List
    │   ├── ArrayList
    │   └── LinkedList
    ├── Set
    │   ├── HashSet
    │   ├── LinkedHashSet
    │   └── SortedSet
    │       └── NavigableSet
    │           └── TreeSet
    └── Queue
        ├── PriorityQueue
        └── Deque
            ├── ArrayDeque
            └── LinkedList
 
Map                         // отдельная ветка, не Collection
├── HashMap
├── LinkedHashMap
├── SortedMap
│   └── NavigableMap
│       └── TreeMap
└── ConcurrentMap
    └── ConcurrentHashMap

Это не полный перечень классов, а рабочая карта выбора.

Как читать контракты

Каждый уровень добавляет свой инвариант:

Интерфейс	Что гарантирует
Iterable<E>	объект можно обойти через Iterator<E>
Collection<E>	группа элементов и базовые операции
List<E>	порядок, индексы, дубликаты
Set<E>	отсутствие дубликатов по правилам равенства
Queue<E>	извлечение по политике очереди
Deque<E>	работа с обоими концами
Map<K,V>	каждому уникальному ключу соответствует не более одного значения
SortedSet / SortedMap	элементы или ключи отсортированы
NavigableSet / NavigableMap	поиск ближайших меньших и больших значений

Тип интерфейса описывает требуемое поведение, а класс реализации — устройство и стоимость операций:

List<String> order = new ArrayList<>();
Set<String> uniqueIds = new HashSet<>();
Deque<Task> pending = new ArrayDeque<>();
Map<String, User> usersById = new HashMap<>();

Как выбирать реализацию

1. Сначала зафиксировать семантику: порядок, уникальность, сортировка, доступ с концов или поиск по ключу.
2. Затем оценить преобладающие операции и их сложность.
3. Отдельно проверить требования к null, параллельному доступу и изменяемости.

По умолчанию обычно достаточно:

• ArrayList для последовательности;
• HashSet для проверки уникальности;
• ArrayDeque для стека или очереди;
• HashMap для индекса по ключу.

Сортированные и concurrent-реализации выбирают из-за конкретного контракта, а не «на всякий случай».

Ловушки

• LinkedList одновременно реализует List и Deque, но это не делает его лучшим выбором для обеих задач.
• Порядок обхода HashMap и HashSet не является частью контракта.
• Collections.synchronizedList синхронизирует отдельные методы, но составные действия и обход требуют внешней синхронизации.
• Неизменяемые фабрики List.of, Set.of, Map.of не принимают null; Set.of также отвергает дубликаты.
• Интерфейс не гарантирует конкретную сложность — её задаёт реализация.

Вопросы на собеседовании

1. Почему Map вынесен в отдельную ветку?
2. Какие гарантии добавляют List, Set и Queue?
3. Чем SortedMap отличается от NavigableMap?
4. Как выбрать между ArrayList, HashSet, ArrayDeque и HashMap?
5. Почему порядок HashSet нельзя использовать как часть бизнес-логики?

Связанные заметки

Collection · List · Set · Queue and Deque · Map · Big O оценка сложности операций с коллекциями · ConcurrentHashMap