Какова алгоритмическая сложность основных операций с `map` в Go?

Основные операции с 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 хорошо оптимизирована для минимизации таких ситуаций.