О-нотация и сложность операций в Map
В основе map в Go лежит хеш-таблица (массив "корзин" или buckets). Поэтому скорость работы мапы напрямую зависит от качества хеш-функции и заполненности этих корзин.
Сводная таблица сложности
| Операция | Средний (лучший) случай | Худший случай |
|---|---|---|
Чтение (val := m[k]) | $O(1)$ | $O(n)$ |
Запись (m[k] = val) | $O(1)$ | $O(n)$ |
Удаление (delete(m, k)) | $O(1)$ | $O(n)$ |
Итерация (for range) | $O(n)$ | $O(n)$ |
(где $n$ — количество элементов в мапе)
Почему средний случай — $O(1)$?
В идеальных условиях хеш-функция равномерно распределяет ключи по разным корзинам (buckets). Чтобы найти, записать или удалить элемент, Go делает следующее:
- Вычисляет хеш от ключа (быстрая математическая операция).
- По хешу мгновенно находит нужную корзину в массиве.
- Пробегается по элементам внутри корзины (в Go их максимум 8 штук — это константное время).
Все эти шаги не зависят от общего количества элементов в мапе, поэтому сложность — $O(1)$.
Почему худший случай — $O(n)$? (Коллизии)
Худший сценарий наступает, когда происходит множество хеш-коллизий — ситуаций, когда разные ключи выдают одинаковый хеш или попадают в одну и ту же корзину.
Что происходит под капотом:
- Если в корзину (где всего 8 мест) нужно положить 9-й элемент, Go создает overflow bucket (дополнительную корзину) и связывает их с помощью указателя (получается связный список).
- Если злоумышленник (или плохая хеш-функция) сгенерирует ключи так, что все $n$ элементов попадут в одну корзину, они выстроятся в длинный связный список.
- Теперь, чтобы найти элемент, Go придется линейно перебирать весь этот список. Сложность деградирует до $O(n)$.
Чтобы защититься от искусственного создания таких коллизий (атака Hash DoS), Go при создании каждой новой мапы генерирует случайный
hash seed. Из-за этого одна и та же строка в разных мапах будет иметь разный хеш.
Сложность при расширении мапы (Эвакуация)
Как и в слайсах, когда мапа заполняется (коэффициент загрузки > 6.5 элементов на корзину), ей нужно вырасти. Выделяется массив корзин в 2 раза большего размера.
- Наивный подход: Скопировать все элементы сразу. Это заняло бы $O(n)$ времени и вызвало бы "фриз" (зависание) программы.
- Подход Go (Эвакуация): Go использует инкрементальную эвакуацию. При каждой операции записи или удаления в мапу, Go переносит лишь по 2 корзины из старого массива в новый.
- Итог: Благодаря этому "размазыванию" работы, сложность записи даже во время роста мапы остается амортизированной $O(1)$.
Сложность итерации — $O(n)$
Цикл for k, v := range m должен обойти все корзины и все overflow-корзины. Время обхода линейно зависит от размера выделенной под мапу памяти.
Важный нюанс: Порядок обхода элементов в Go намеренно рандомизирован, чтобы разработчики не закладывались на порядок выдачи ключей.