Ответ
Основные операции с map (поиск, вставка, удаление) в Go в среднем имеют амортизированную сложность O(1).
Как это работает:
map в Go реализована как хеш-таблица. Ключ преобразуется в хеш, который используется как индекс для быстрого доступа к значению в нижележащем массиве (массиве бакетов).
m := map[string]int{"one": 1, "two": 2}
// Поиск: O(1) в среднем
val, exists := m["one"]
// Вставка: O(1) в среднем
m["three"] = 3
// Удаление: O(1) в среднем
delete(m, "two")Худший случай:
В редких случаях, когда множество разных ключей генерируют один и тот же хеш (коллизии), сложность операций может деградировать до O(n), где n — количество элементов в map. Однако реализация map в Go хорошо оптимизирована для минимизации таких ситуаций.