Что такое бакет в хэш-таблице

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

Знаете ли вы, что map в Go это не абстракция из учебника, а конкретная реализация с бакетами. Из её устройства прямо следуют ограничения языка: почему нельзя взять адрес элемента, почему порядок обхода случайный и почему параллельная запись роняет процесс.

Как отвечать

Бакет это группа слотов, в которую попадают ключи с совпадающими младшими битами хэша. Ключевая особенность реализации в Go: бакет хранит не один элемент, а сразу несколько пар, плюс массив коротких меток со старшими битами хэша.

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

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

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

Стоит добавить, что в современных версиях внутреннее устройство переехало на схему с группами слотов и управляющими байтами, но внешний контракт и само понятие бакета остались прежними.

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

Переносят на Go книжную схему со связным списком в каждом бакете. Цепочка здесь не из элементов, а из бакетов по несколько пар, и это меняет ответ на вопрос о локальности памяти и стоимости промаха мимо кэша.

Считают порядок обхода стабильным. Он намеренно рандомизирован на каждом проходе, и код, который берёт первый ключ из range, ломается на ближайшем же запуске; нужна явная сортировка ключей.

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