Ответ
В Go map реализован на основе хэш-таблицы, которая состоит из массива бакетов (buckets). Каждый бакет — это небольшая структура для хранения до 8 пар ключ-значение.
Структура бакета (bmap)
Каждый бакет содержит:
tophash[8]: Массив из 8 байт, где каждый байт — это старшие 8 бит хэша от соответствующего ключа. Это позволяет быстро отсеивать ключи, которые точно не совпадают, без сравнения самих ключей.- Массивы для хранения 8 ключей и 8 значений.
overflow: Указатель на следующий (переполненный) бакет. Если в один бакет пытается записаться более 8 элементов, создается новый бакет, и они связываются в цепочку.
Процесс работы
- Вычисление хэша: От ключа вычисляется хэш-сумма.
- Определение бакета: Младшие биты хэша используются как индекс в массиве бакетов.
- Поиск в бакете: Старшие биты хэша (
tophash) используются для быстрого поиска нужной ячейки внутри бакета. - Сравнение ключа: Если
tophashсовпал, происходит полное сравнение ключа, чтобы убедиться в его идентичности. - Переход по цепочке: Если в текущем бакете ключ не найден, поиск продолжается в бакетах по указателю
overflow.
Рост таблицы
Когда среднее количество элементов на бакет (load factor) превышает 6.5, происходит расширение хэш-таблицы: количество бакетов удваивается, и элементы постепенно перераспределяются по новым бакетам.