Как в Go (до версии 1.24) решаются коллизии в map? Расскажи про бакеты и overflow-бакеты

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

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

• Бакеты (buckets): фиксированного размера (обычно 8 слотов), в которые помещаются пары ключ-значение.
• Если в бакете все слоты заняты и нужно добавить новую пару, создаётся overflow-бакет — дополнительный бакет, связанный с основным, который расширяет пространство для хранения.

Таким образом, при коллизии Go не использует цепочки или списки, а добавляет overflow-бакеты, образуя цепочку бакетов. При поиске ключа сначала проверяются слоты основного бакета, затем overflow-бакетов по цепочке.

Это позволяет эффективно хранить и искать элементы, сохраняя хорошую производительность даже при коллизиях.

Примерно структура выглядит так:

Bucket -> Overflow Bucket -> Overflow Bucket -> ...

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