Как в Go `map` определяется бакет для ключа и как происходит поиск?

Внутреннее устройство map в Go — это хэш-таблица, состоящая из массива бакетов (buckets).

Процесс определения бакета и поиска значения выглядит так:

1. Вычисление хэша: Для ключа вычисляется хэш с помощью типо-специфичной хэш-функции. Go выбирает быструю хэш-функцию во время компиляции.

2. Определение бакета: Количество бакетов в map всегда является степенью двойки. Это позволяет найти индекс бакета с помощью быстрой побитовой операции AND, а не медленной операции остатка от деления (%).

   // Псевдокод
   hashValue := hash(key)
   // Вместо hashValue % numBuckets используется побитовая операция
   bucketIndex := hashValue & (numBuckets - 1)

3. Поиск внутри бакета (Tophash): Чтобы избежать дорогостоящего сравнения полных ключей при коллизиях, Go использует оптимизацию tophash. Каждый бакет хранит 8 старших бит хэша (tophash) для каждого из своих 8 слотов.

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

4. Обработка коллизий: Если все 8 слотов в бакете заняты, используется overflow bucket (дополнительный бакет), связанный с основным. Поиск продолжается в нем.

5. Рехеширование (Rehashing): Когда map становится слишком заполненной (load factor > 6.5), ее размер удваивается. В Go рехеширование происходит инкрементально: старые бакеты переносятся в новую, увеличенную таблицу постепенно, во время операций записи, а не за один раз, что позволяет избежать долгих пауз (stop-the-world).