Какие знаешь реализации Map в Kotlin?

Основные реализации Map в Kotlin (и JVM)

В Kotlin, как и в Java, интерфейс Map<K, V> имеет несколько ключевых реализаций, каждая со своей спецификой производительности, порядком элементов и поведением при многопоточности. Kotlin предоставляет удобные функции-фабрики для создания экземпляров, но "под капотом" используются классические реализации из Java Collections Framework.

1. HashMap — наиболее распространённая реализация

HashMap хранит данные в виде хеш-таблицы, обеспечивая константное время выполнения O(1) для базовых операций (get, put, containsKey) в среднем случае. Однако в худшем случае (коллизии) время может деградировать до O(n).

Ключевые особенности:

• Не гарантирует порядок элементов при итерации (может меняться при рехешировании).
• Разрешает один null ключ и множество null значений.
• Не является потокобезопасной.

// Создание через функцию-фабрику Kotlin
val hashMap1 = hashMapOf("a" to 1, "b" to 2)
// Или через конструктор
val hashMap2 = HashMap<String, Int>().apply {
    put("x", 10)
    put("y", 20)
}

2. LinkedHashMap — HashMap с предсказуемым порядком

Расширяет HashMap, добавляя связный список, который определяет порядок итерации. По умолчанию используется порядок вставки (insertion-order), но можно настроить и порядок доступа (access-order) для реализации LRU-кэшей.

Ключевые особенности:

• Гарантирует итерацию в порядке добавления элементов (или последнего доступа, если настроено).
• Время операций чуть выше, чем у HashMap, из-за обслуживания связного списка, но остаётся O(1).
• Потребляет немного больше памяти.

// Порядок вставки сохраняется
val linkedMap = linkedMapOf(
    "first" to 1,
    "second" to 2,
    "third" to 3
)
// Итерация: "first", "second", "third"

3. TreeMap — отсортированная по ключам реализация

Реализует интерфейс SortedMap/NavigableMap, храня элементы в красно-чёрном дереве. Ключи автоматически сортируются согласно их естественному порядку (если они реализуют Comparable) или компаратору, переданному в конструктор.

Ключевые особенности:

• Гарантирует логарифмическое время O(log n) для операций get, put, remove.
• Предоставляет дополнительные методы для работы с диапазонами: subMap, headMap, tailMap.
• Не разрешает null ключи (если только компаратор не поддерживает сравнение с null).

// Сортировка по ключам (естественный порядок для String)
val treeMap = TreeMap<String, Int>()
treeMap["zebra"] = 1
treeMap["apple"] = 2
treeMap["banana"] = 3
// Итерация: "apple", "banana", "zebra"

4. ConcurrentHashMap — потокобезопасная версия

Специализированная реализация для многопоточных сред. Обеспечивает высокую степень параллелизма за счёт сегментирования (блокировка на уровне сегментов или использование lock-free операций в новых версиях Java).

Ключевые особенности:

• Потокобезопасность без глобальной блокировки всей таблицы.
• Итераторы обладают свойством weakly-consistent (отражают состояние коллекции на момент создания или обхода, но не выбрасывают ConcurrentModificationException).
• Разрешает операции при частичной блокировке.

import java.util.concurrent.ConcurrentHashMap
val concurrentMap = ConcurrentHashMap<String, Int>()

5. MutableMap и mapOf() — функции-обёртки Kotlin

Kotlin предоставляет удобные функции для создания неизменяемых (mapOf()) и изменяемых (mutableMapOf()) коллекций. Конкретная реализация под капотом зависит от размера и версии Kotlin/Java.

// Неизменяемая (часто возвращается как java.util.Collections$SingletonMap или LinkedHashMap)
val readOnlyMap = mapOf("key" to "value")

// Изменяемая (обычно LinkedHashMap)
val mutableMap = mutableMapOf<Char, Int>()

6. EnumMap — оптимизированная для enum-ключей

Высокоэффективная реализация для случаев, когда ключами являются значения перечисления (enum). Внутри использует массивы, индексируемые порядковым номером (ordinal) элемента enum.

Ключевые особенности:

• Крайне низкое потребление памяти и очень высокая производительность.
• Гарантирует порядок итерации согласно порядку объявления элементов в enum.
• Не разрешает null ключи.

enum class Priority { LOW, MEDIUM, HIGH }
val enumMap = EnumMap<Priority, String>(Priority::class.java)
enumMap[Priority.HIGH] = "Важно"

Краткий итог по выбору реализации:

• HashMap — по умолчанию, когда порядок не важен.
• LinkedHashMap — когда требуется сохранить порядок вставки или реализовать LRU-кэш.
• TreeMap — когда необходим сортированный порядок по ключам или работа с диапазонами.
• ConcurrentHashMap — для многопоточных приложений.
• EnumMap — когда ключи принадлежат одному перечислению (максимальная эффективность).

Все эти реализации наследуются от интерфейса MutableMap в Kotlin, что позволяет использовать богатый набор функций-расширений (filterKeys, mapValues, onEach, и т.д.), предоставляемых стандартной библиотекой Kotlin.