Какая алгоритмическая сложность доступа по ключу в map Go

Что проверяют

Знаете ли вы, что за коротким m[k] стоит хеш-таблица со своей ценой, и различаете ли среднюю сложность и гарантированную. Вопрос быстрый, поэтому дальше почти всегда спрашивают, что происходит при росте карты, почему порядок обхода каждый раз новый и что будет при записи из двух горутин.

Как отвечать

Сразу назовите оценку: в среднем O(1), в худшем случае O(n), когда ключи сходятся в одну группу. Дальше конкретика:

• реализация: начиная с Go 1.24 рантайм использует Swiss Tables, то есть массив групп по 8 слотов с байтом метаданных на слот, и поиск сравнивает контрольные байты сразу по всей группе. До 1.24 это были бакеты по 8 пар с цепочкой переполнения;
• цена хеша: O(1) считается от числа элементов, но не от размера ключа. Хеширование длинной строки линейно по её длине, поэтому карта с килобайтными ключами не бесплатна;
• рост: при заполнении выше порога таблица увеличивается и элементы переезжают, перенос размазан по последующим операциям, отсюда слово «амортизированная». Если размер известен заранее, make(map[string]int, n) убирает серию перестроек;
• защита от атаки: хеш засеян случайным значением при старте процесса, а обход начинается со случайной позиции. Порядок итерации намеренно не определён, полагаться на него нельзя;
• память: delete не возвращает память, карта не сжимается. clear(m) только опустошает, для реального освобождения карту пересоздают.

Хорошее дополнение про адресацию: &m[k] не компилируется, потому что элементы переезжают при росте, а чтение отдаёт копию значения. И про конкурентность: одновременная запись это фатальная ошибка рантайма, её не перехватить через recover, нужен sync.RWMutex либо sync.Map для сценария с преобладанием чтений и непересекающимися ключами.

Где спотыкаются

Называют O(1) и останавливаются. Без худшего случая и без амортизации ответ звучит заученным.

Уверенно пересказывают метод цепочек из общего курса, не зная, как устроена карта именно в Go. Пары уточняющих вопросов хватает, чтобы это стало заметно.

Считают, что читать карту из нескольких горутин безопасно, пока пишет только одна. Гонка чтения с записью тоже ловится рантаймом и роняет процесс.