Как устроена мапа в Go, как происходит поиск и решаются коллизии

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

Знаете ли вы устройство и главные практические правила: нулевая карта, порядок обхода, отсутствие потокобезопасности.

Как отвечать

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

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

Правила, которые проверяют:

• нулевая карта только читается. var m map[string]int возвращает нулевое значение на любой ключ, но запись в неё это паника. Создавать через make или литерал;
• проверка наличия через второе значение: v, ok := m[k], потому что отсутствующий ключ неотличим от нулевого значения;
• порядок обхода случайный намеренно, чтобы никто на него не полагался. Нужен порядок, соберите ключи и отсортируйте;
• не потокобезопасна: параллельная запись обнаруживается рантаймом и роняет программу с явным сообщением. Нужен sync.RWMutex или sync.Map для сценария «много чтений, редкие записи»;
• нельзя взять адрес элемента, потому что рост карты переносит данные;
• ключ должен быть сравнимым: срез, карта и функция ключом быть не могут.

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

Пишут в нулевую карту и получают панику.

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

Считают, что удаление освобождает память: карта не уменьшается, для этого её пересоздают.

Не знают про рантайм-детектор параллельной записи и ищут причину падения в своём коде.