Какая сложность операций с Map

Операции с Map в Java (и Kotlin) зависят от реализации.

HashMap (основная реализация):

• put(), get(), remove() – O(1) в среднем, но могут деградировать до O(n) при коллизиях (редко, если хеш-функция хорошая).
• containsKey() – аналогично get().

TreeMap (на основе красно-черного дерева):

• Все операции (put, get, remove) – O(log n), так как дерево балансируется.

LinkedHashMap:

• Как HashMap, но с поддержкой порядка (вставки/доступа) – O(1) для основных операций.

Пример:

val map = hashMapOf<Int, String>()
map[1] = "A"  // O(1)
val value = map[1]  // O(1)

Выбор реализации зависит от требований: скорость (HashMap), порядок (LinkedHashMap) или сортировка (TreeMap).