❓ Какова алгоритмическая сложность обращения к мапе

Обращение к элементу в мапе работает за константное время, потому что Go использует хеш-таблицу. Ключ хешируется, и по значению хеша система сразу указывает на нужный бакет в памяти.

При переаллокации данных сложность может деградировать до O(n).

Это происходит, когда количество элементов в мапе превышает load factor, примерно 6,125 элементов на баккет в среднем, или около 81% заполненности. Тогда Go выделяет новую память под бакеты в два раза больше и постепенно переносит данные из старых бакетов в новые.

🐸 Библиотека Go для собеса