В чем отличия структур данных List, Set и Map

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

Понимаете ли вы контракт каждого интерфейса и то, как выбор реализации меняет порядок, скорость и работу с null. Следом почти всегда идут вопросы про equals и hashCode в HashSet и HashMap или про то, почему Map не наследуется от Collection.

Как отвечать

Сначала иерархия: List и Set наследуют Collection, а Map стоит отдельно, потому что хранит пары ключ-значение, а не одиночные элементы.

• List: упорядоченная последовательность с индексами, дубли разрешены. ArrayList даёт get(i) за O(1) и амортизированное O(1) на добавление в конец, вставка в середину O(n) из-за сдвига. LinkedList на практике проигрывает почти всегда: доступ по индексу O(n) и плохая работа с кэшем процессора;
• Set: только уникальные элементы. В HashSet уникальность определяют equals и hashCode, в TreeSet сравнение через compareTo или Comparator. Порядок у HashSet не гарантирован, LinkedHashSet хранит порядок вставки, TreeSet сортирует, операции у него за O(log n);
• Map: уникальные ключи, значения могут повторяться. HashMap в среднем даёт O(1), а при большом числе коллизий в одной корзине (от 8 элементов при достаточном размере таблицы) список в ней превращается в дерево. LinkedHashMap помнит порядок и годится для LRU-кэша, TreeMap сортирует ключи.

Хорошо добавить современное: с Java 21 есть SequencedCollection и SequencedMap с методами getFirst(), getLast(), reversed(). Фабрики List.of, Set.of, Map.of возвращают неизменяемые коллекции и не принимают null, а Set.of с повторяющимися элементами бросает IllegalArgumentException.

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

Говорят, что Set «не хранит порядок». LinkedHashSet и TreeSet хранят, не гарантирует его только HashSet.

Кладут в HashSet или делают ключом HashMap объект, у которого переопределён equals, но не hashCode, или меняют поле, участвующее в хешировании, уже после вставки. Элемент становится «невидимым»: contains возвращает false.

Удаляют элементы из коллекции в цикле for-each и ловят ConcurrentModificationException. Правильно через Iterator.remove() или removeIf.