Как происходит эвакуация элементов в хэш-таблице?
Что проверяют
Знаете ли вы, что происходит внутри map при росте и почему Go не переносит все элементы разом. Следом обычно спрашивают, почему нельзя взять адрес элемента мапы и что изменилось в реализации начиная с Go 1.24.
Как отвечать
Начните с классической реализации, для неё и придуман термин «эвакуация»:
- устройство:
hmapхранит массив из 2^B бакетов, в каждом до 8 пар ключ/значение и массивtophashсо старшими байтами хешей. Если бакет заполнен, к нему цепляется overflow-бакет; - когда растёт: средняя загрузка превысила 6.5 элемента на бакет, тогда массив удваивается. Второй триггер: слишком много overflow-бакетов после удалений, тогда делается рост того же размера, чтобы уплотнить данные;
- как переносит: новый массив выделяется сразу, старый остаётся в
oldbuckets. Элементы переезжают постепенно: каждая запись или удаление эвакуирует бакет, в который попал ключ, и ещё один по порядку. Цена роста размазана по операциям, а не выпадает одной паузой; - куда переносит: при удвоении старый бакет делится на два, X с тем же индексом и Y со сдвигом на старый размер. Решает следующий бит хеша;
- чтение во время роста: поиск проверяет, эвакуирован ли нужный старый бакет, и если нет, читает из
oldbuckets.
Отсюда же запрет на &m[k]: после переезда указатель смотрел бы в старый массив.
Затем скажите, что с Go 1.24 встроенная мапа построена на Swiss Tables. Данные разбиты на таблицы ограниченного размера (до 1024 слотов) из групп по 8 слотов с контрольными байтами. Переполненная таблица перестраивается целиком, а на пределе размера делится надвое, как в extendible hashing. Постепенного переноса больше нет, но пауза ограничена одной таблицей.
Где спотыкаются
Говорят, что при росте все элементы копируются за один проход, как в HashMap из Java. Для старой реализации это неверно, для новой верно лишь в пределах одной таблицы.
Считают, что после delete мапа ужимается. Память не отдаётся: чтобы её освободить, создают новую мапу и копируют живые ключи.
Путают рост с потокобезопасностью. Одновременная запись из двух горутин роняет программу с fatal error: concurrent map writes, и recover это не перехватывает.