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

В Go map реализована как хеш-таблица. Временная сложность основных операций в среднем случае является константной — O(1).

Средний случай: O(1)

В большинстве практических сценариев операции с map выполняются за константное время. Это достигается благодаря эффективной хеш-функции, которая равномерно распределяет ключи по внутренним "корзинам" (buckets).

// Создаем и заполняем map
m := make(map[string]int)

// Эти операции в среднем выполняются за O(1)
m["apple"] = 1      // Добавление
value := m["apple"] // Поиск
delete(m, "apple")  // Удаление

Худший случай: O(n)

Худший случай наступает при возникновении большого количества коллизий — когда множество разных ключей имеют одинаковый хеш. В этой ситуации все эти ключи попадают в одну "корзину", которая представляет собой связанный список. Для поиска, добавления или удаления элемента в этой корзине потребуется перебрать все её n элементов, что приводит к линейной сложности O(n).

На практике в Go это случается крайне редко, так как:

1. Встроенные хеш-функции для стандартных типов хорошо спроектированы.
2. При увеличении количества коллизий map автоматически перестраивается (рехешируется), чтобы перераспределить элементы.