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

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

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

Пример:

m := make(map[string]int)

m["foo"] = 42       // В среднем O(1)
m["bar"] = 100      // В среднем O(1)

val, ok := m["foo"] // В среднем O(1)

delete(m, "bar")    // В среднем O(1)

Ключевые моменты производительности map:

1. Коллизии: Go разрешает коллизии, храня пары ключ-значение с одинаковым хэшем в одном «бакете» (bucket). При поиске в таком бакете происходит линейный перебор, что и может привести к O(n) в худшем случае.
2. Рехеширование (рост карты): Когда map заполняется (load factor > 6.5), Go выделяет в два раза больше памяти и переносит все старые элементы в новую таблицу. Это дорогая операция, которая может вызвать кратковременную задержку.
3. Предварительное выделение ёмкости: Если вы заранее знаете примерное количество элементов, используйте make(map[K]V, size). Это позволяет сразу выделить нужную память и избежать затратных рехеширований в процессе наполнения карты.