Что такое эвакуация в мапе Go

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

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

Как отвечать

Карта в Go это массив бакетов, в каждом до восьми пар. Когда заполненность превышает порог (в среднем 6.5 элементов на бакет) или накапливается слишком много переполненных бакетов, рантайм запускает рост: выделяется новый массив, обычно вдвое больше.

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

Отсюда следствия, которые и просят объяснить:

• чтение во время роста проверяет оба массива: если бакет ещё не эвакуирован, значение ищется в старом;
• рост растянут по времени и завершается, когда перенесён последний бакет;
• при удвоении каждый старый бакет делится надвое: элементы расходятся по новому биту хеша;
• есть и рост «на месте» (sameSizeGrow), когда размер не меняется: он нужен, если карту много раз заполняли и очищали, и бакеты стали разрежёнными.

Практический вывод: если известно примерное число элементов, стоит задать его при создании (make(map[K]V, n)), тогда роста и эвакуации не произойдёт вовсе. И ещё: удаление элементов не уменьшает карту, память возвращается только пересозданием.

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

Думают, что рост карты происходит одномоментно.

Не знают, что во время роста чтение смотрит в два массива.

Считают, что delete освобождает память карты.

Не задают ёмкость при создании, зная объём заранее.