Выбор ответа Senior Слайсы и мапы изнутри обновлено
Эвакуация бакетов при росте map
Вопрос
Как росла классическая мапа Go (до 1.24), когда коэффициент загрузки превышал порог 6.5?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Массив бакетов удваивался, перенос шёл постепенно при записях. Старая реализация: массив бакетов по 8 пар плюс цепочки переполнения.
Варианты ответа
- Вся мапа блокировалась и копировалась в новый массив за один шаг
- Добавлялись только новые цепочки переполнения, массив бакетов не рос никогда
- Бакеты с длинными цепочками превращались в дерево поиска
- Массив бакетов удваивался, перенос шёл постепенно при записяхправильный ответ
Разбор
Старая реализация: массив бакетов по 8 пар плюс цепочки переполнения. При средней загрузке больше 6.5 элемента на бакет выделялся массив в 2 раза больше, и эвакуация шла инкрементально: каждая запись или удаление переносили пару бакетов, чтобы не было длинной паузы. При большом числе overflow-бакетов делался рост «того же размера» для уплотнения. Превращения в дерево (как в Java HashMap) в Go не было.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.
Ещё по теме «Слайсы и мапы изнутри»
- Разбить слайс на части по k на Go
- Удаление дубликатов с сохранением порядка на Go
- Группировка анаграмм на Go
- Циклический сдвиг слайса на Go
- Число подмассивов с суммой k на Go
- Топ-k частых слов на Go
- Что выведет Go: append при полной ёмкости
- Что выведет Go: два append в один подслайс