Преимущества Map перед другими структурами данных

Что проверяют

Понимаете ли вы, что Map не соперник List и Set, а другой контракт: доступ по ключу вместо доступа по позиции или проверки принадлежности. Заодно смотрят, умеете ли вы выбирать реализацию под задачу и чем платите за быстрый поиск.

Как отвечать

Начните с контракта. Map хранит пары ключ и значение, ключи уникальны, а главное свойство это поиск, вставка и удаление по ключу за константное время в среднем, тогда как поиск по содержимому в ArrayList линейный. Отсюда применения: кэши, индексы, счётчики, группировка через Collectors.groupingBy.

Дальше про реализации, за этим вопрос обычно и задаётся:

• HashMap: среднее O(1), порядок обхода не гарантирован, допускает один null в ключах;
• LinkedHashMap: порядок вставки, а в режиме порядка обращений готовый LRU через removeEldestEntry;
• TreeMap: O(log n), зато отсортирована и умеет floorKey, ceilingKey, subMap;
• EnumMap: ключи-перечисления, внутри массив, поэтому быстрее и компактнее;
• ConcurrentHashMap: конкурентный доступ и атомарные compute, merge, putIfAbsent.

Скажите и про цену. На каждую запись создаётся узел со ссылками и кэшированным хэшем, памяти уходит заметно больше, чем на плоский массив, а при исчерпании ёмкости таблица пересобирается. Если ключей единицы, обычный список окажется быстрее.

Где спотыкаются

Первое: говорят «всегда O(1)» и останавливаются. Константа средняя и держится на равномерном распределении хэшей. При массовых коллизиях корзина вырождается в список, и хотя в современной Java она перестраивается в дерево с O(log n), причина остаётся в плохом hashCode.

Второе: забывают контракт equals и hashCode. Переопределили одно без другого или взяли изменяемый объект ключом и поменяли поле после вставки: запись лежит в таблице, но get её не находит. Это любимый уточняющий вопрос после ответа про скорость.

Третье: считают Map частью Collection и путаются в потокобезопасности. Map не наследует Collection и перебирается через entrySet. HashMap не потокобезопасна, а Collections.synchronizedMap защищает отдельные вызовы, но не связку «проверил и положил»: для неё нужны атомарные методы ConcurrentHashMap.