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

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

Знаете ли вы среднюю и худшую оценку и понимаете ли устройство корзин.

Как отвечать

В среднем O(1), в худшем O(n).

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

Рост: при среднем заполнении выше примерно шести с половиной элементов на корзину число корзин удваивается. Перенос данных при этом постепенный: он размазан по последующим операциям, а не выполняется одним долгим шагом. Поэтому отдельная вставка не даёт неожиданной паузы.

Худший случай возникает при массовых коллизиях, когда почти всё оседает в цепочках переполнения одной корзины. На практике этого не происходит, потому что при старте программы выбирается случайное начальное значение хеша. Это не только про равномерность: так закрывается атака, когда злоумышленник подбирает ключи с одинаковым хешем и превращает поиск в линейный.

Что стоит добавить:

• порядок обхода намеренно случайный и меняется от запуска к запуску. Это сделано специально, чтобы код не начинал зависеть от порядка. Нужен порядок, значит собирайте ключи и сортируйте;
• обход всей карты это O(n);
• нельзя взять адрес элемента карты, потому что при росте данные переезжают;
• удаление не уменьшает число корзин: память после массового удаления не возвращается, и если это важно, карту пересоздают.

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

Называют только O(1) без худшего случая.

Полагаются на порядок обхода.

Не знают про случайное начальное значение хеша и его назначение.

Ждут, что удаление элементов освободит память.