Как устроен hashmap в Go?

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

Понимание внутреннего устройства map, а не умение пользоваться синтаксисом. Отдельно смотрят на знание роста таблицы, отсутствия потокобезопасности и рандомизации порядка обхода.

Как отвечать

Сначала честная оговорка: реализация менялась. До Go 1.24 это классическая хеш-таблица с бакетами (hmap/bmap), с Go 1.24 рантайм перешёл на Swiss Tables. Контракт языка при этом не изменился.

Классическая схема:

• таблица это массив бакетов, в каждом бакете 8 слотов ключ-значение;
• младшие биты хеша выбирают бакет, старшие 8 бит хранятся в tophash и позволяют отсеять несовпадения без полного сравнения ключей;
• коллизии решаются не связным списком элементов, а overflow-бакетами, то есть цепочкой дополнительных бакетов по 8 слотов;
• при среднем заполнении выше 6.5 элементов на бакет число бакетов удваивается, а при избытке overflow-бакетов возможен рост «того же размера» ради дефрагментации;
• перенос инкрементальный: старая таблица эвакуируется порциями во время последующих записей, а не одним длинным перехешированием.

Swiss Tables: те же группы по 8 слотов, но с управляющим словом метаданных и открытой адресацией с пробированием по группам. Метаданные сравниваются векторно, отсюда меньше промахов кэша и более быстрое чтение.

Что важно независимо от версии:

• средняя сложность вставки, поиска и удаления O(1), деградация до O(n) на патологическом распределении хешей;
• ключ должен быть сравнимым: слайсы, мапы и функции нельзя, структуры и массивы из сравнимых типов можно;
• порядок обхода намеренно перемешивается, стартовая точка выбирается случайно на каждом range. Это не «не гарантируется», это активное противодействие завязке на порядок;
• нулевая мапа (var m map[string]int) читается, но паникует при записи, нужен make;
• чтение отсутствующего ключа возвращает нулевое значение, отличить помогает v, ok := m[k];
• адрес элемента взять нельзя (&m[k] не компилируется), и нельзя присвоить поле структуре, лежащей в мапе по значению: только через временную переменную или map[K]*V;
• delete не возвращает память, таблица не сжимается. Для долгоживущего кэша с вычищением помогает пересоздание мапы;
• конкурентная запись это не гонка данных, а фатальная ошибка рантайма concurrent map writes, которую не поймать через recover. Нужен sync.RWMutex или sync.Map, причём вторая выигрывает лишь в узких сценариях с редкой записью и частым чтением.

m := make(map[string]int, 1000) // предаллокация снимает серию перестроений
if v, ok := m["apple"]; ok {
    fmt.Println(v)
}

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

Говорят «коллизии разрешаются связным списком», описывая устройство HashMap из Java, и представляют рост как разовое полное перехеширование под блокировкой. Ещё частая ошибка: считать sync.Map универсальной заменой обычной мапе под мьютексом.