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

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

Понимаете ли вы, какие гарантии даёт каждая коллекция и во что это обходится по скорости и памяти. В Android-проекте следом часто спрашивают про Kotlin: чем List отличается от MutableList и почему для ключей важны equals и hashCode.

Как отвечать

• List: упорядоченная коллекция с доступом по индексу, дубликаты допустимы. ArrayList даёт доступ по индексу за O(1), а вставку в середину за O(n). LinkedList на практике почти не нужен;
• Set: только уникальные элементы, уникальность определяется через equals и hashCode. HashSet проверяет наличие за O(1) в среднем, LinkedHashSet помнит порядок вставки, TreeSet держит элементы отсортированными, операции за O(log n);
• Map: пары ключ и значение, ключи уникальны. HashMap, LinkedHashMap с порядком вставки, TreeMap с сортировкой по ключу. В Java Map не наследует Collection, это отдельная иерархия.

Дальше про Kotlin, на котором пишется большинство Android-кода. List, Set, Map это интерфейсы только для чтения, менять коллекцию можно через MutableList и его соседей. Это не настоящая неизменяемость: за ссылкой типа List может стоять изменяемый объект. setOf и mutableMapOf создают LinkedHashSet и LinkedHashMap, поэтому порядок вставки сохраняется.

Android-специфика: в androidx.collection есть ArrayMap и ArraySet, на небольших коллекциях они экономнее по памяти, чем HashMap. SparseArray хранит значения по ключу int без упаковки в Integer. В Compose стандартный List компилятор считает нестабильным, поэтому для параметров экранов берут kotlinx.collections.immutable или файл конфигурации стабильности.

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

Говорят «Set всегда неупорядочен». В Kotlin setOf сохраняет порядок вставки, а TreeSet сортирует.

Кладут в HashSet или делают ключом HashMap объект без переопределённых equals и hashCode либо меняют поля ключа после вставки. Элемент перестаёт находиться.

Удаляют элементы из коллекции внутри for по ней же и получают ConcurrentModificationException. Нужен removeAll, removeIf или явный итератор.