В Go map реализован как хеш-таблица с открытой адресацией и структурой, основанной на "buckets" (корзинах). Ключи хешируются, и хеш разбивается на две части: старшие биты определяют индекс корзины, младшие — позицию внутри корзины.

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

При добавлении или поиске ключа происходит:

Вычисление хеша ключа.
Определение корзины по части хеша.
Линейный поиск по слотам корзины и overflow-бакетам для совпадения ключа.

Также map в Go динамически расширяется (resize), когда нагрузка превышает порог, что улучшает производительность.

Пример упрощённой структуры:

// bucket содержит несколько пар ключ-значение
// и указатель на overflow-бакет
type bucket struct {
    keys   [8]interface{}
    values [8]interface{}
    overflow *bucket
}

// map содержит массив корзин и другую служебную информацию
// (упрощённо)
type hmap struct {
    buckets []*bucket
    count   int
    // ... другие поля
}

Таким образом, Go map — это эффективная хеш-таблица с корзинами фиксированного размера и цепочечным разрешением коллизий через overflow-бакеты.

Как устроена map в Go? Расскажите про внутреннюю структуру, buckets, коллизии.