> Для чего нужны два экстра бита внутри бакета map Go и как они используются (Go)

Два дополнительных бита (так называемые tophash - старшие 8 бит хеша) в каждом бакете (bucket) Go map используются для ускорения поиска и оптимизации сравнения.

Назначение:

1. Быстрый провал (early rejection): При поиске ключа сначала сравнивается tophash элемента с вычисленным tophash искомого ключа. Если они не совпадают - сразу переходим к следующему слоту, не вызывая дорогую функцию сравнения полных ключей (особенно для строк или структур).

2. Маркировка состояния слота: Битовая маска tophash хранит не только хеш, но и специальные флаги:

   • emptyRest (0) - слот пуст, и все последующие тоже пусты (конец цепочки).

   • emptyOne (1) - слот пуст, но не конец.

   • evacuated (2) - слот перемещён при рехешировании.

   • minTopHash (4) - минимальное значение для реального хеша (если хеш меньше - он смещается, чтобы не пересекаться с флагами).

Использование:

• При вставке tophash сначала проверяется на emptyRest, чтобы найти свободное место.

• При поиске цикл по слотам бакета прерывается, как только встречается emptyRest - это гарантирует, что ключа нет, без просмотра всех 8 слотов.

• При рехешировании evacuated позволяет корректно обрабатывать частично перемещённые бакеты.

Таким образом, два байта tophash на слот (всего 16 байт на бакет из 8 слотов) экономят время сравнения и упрощают логику обхода.