Какая упорядоченность у Map в Kotlin и существуют ли реализации, сохраняющие порядок элементов

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

Знаете ли вы, что именно возвращают фабричные функции коллекций Kotlin, а не только контракт интерфейса. Следом обычно спрашивают, как сделать LRU-кэш или почему ArrayMap отдаёт элементы не в порядке добавления.

Как отвечать

Интерфейс Map порядок не гарантирует, но конкретные функции стандартной библиотеки его задают:

• mapOf() и mutableMapOf(): на JVM возвращают LinkedHashMap, итерация идёт в порядке вставки, и это прописано в документации. Порядок сохраняют и buildMap, associate, groupBy, toMap;
• hashMapOf(): HashMap, порядок не определён и может меняться при росте таблицы;
• linkedMapOf(): явный LinkedHashMap. Повторная запись по существующему ключу место элемента не меняет. Конструктор LinkedHashMap(16, 0.75f, true) переключает порядок на порядок доступа, на этом с переопределённым removeEldestEntry строится LRU;
• sortedMapOf(): java.util.TreeMap, сортировка по ключу или по переданному Comparator, операции за O(log n). Из готовой карты такую даёт toSortedMap().

Для Android добавьте платформенные структуры:

• ArrayMap: экономит память на небольших картах, но хранит ключи упорядоченными по хэш-кодам, поэтому порядок вставки не сохраняет;
• SparseArray: ключи Int без боксинга, keyAt(i) отдаёт ключи по возрастанию;
• LruCache: готовый кэш поверх LinkedHashMap в режиме порядка доступа.

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

Говорят «Map в Kotlin неупорядочен», смешивая интерфейс и реализацию. Тогда непонятно, почему mapOf на практике отдаёт элементы ровно в порядке объявления.

Полагаются на порядок HashMap: на тестовых данных он кажется стабильным, а при других ключах или объёме меняется.

Ждут, что порядок учитывается в ==. Равенство карт сравнивает только пары ключ-значение, поэтому LinkedHashMap и TreeMap с одинаковым содержимым равны.