Как в Go разрешаются коллизии в `map`?

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

Процесс работает следующим образом:

1. Вычисление хеша: Для ключа вычисляется хеш-значение.
2. Определение бакета (bucket): Хеш-значение используется для определения индекса "бакета" (корзины) в нижележащем массиве.
3. Разрешение коллизии: Если несколько разных ключей попадают в один и тот же бакет, они организуются в цепочку внутри этого бакета.

Ключевые моменты:

• Каждый бакет — это небольшая структура, которая может хранить до 8 пар ключ-значение.
• Если бакет переполняется (в него пытаются добавить 9-й элемент), создается дополнительный overflow bucket, который связывается с основным. Таким образом, цепочка растет.
• При поиске элемента Go сначала находит нужный бакет по хешу, а затем последовательно перебирает все элементы в этом бакете (и в его overflow-бакетах), сравнивая ключи.

// Пример, иллюстрирующий идею
m := make(map[string]int)

// Предположим, хеши "key1" и "key2" указывают на один и тот же бакет.
// hash("key1") % N == bucket_index
// hash("key2") % N == bucket_index

m["key1"] = 1 // Добавляется в бакет
m["key2"] = 2 // Добавляется в цепочку того же бакета

Из-за этого механизма сложность операций с map в среднем составляет O(1), но в худшем случае (когда все ключи попадают в один бакет) она может деградировать до O(n).