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

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

Механизм работы

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

Когда вы обращаетесь к map для чтения или записи:

• Go вычисляет хэш ключа и находит нужный бакет.
• Затем он последовательно перебирает все элементы в связном списке этого бакета, сравнивая ключи уже по их фактическому значению, пока не найдет нужный.

// Концептуальный пример
m := make(map[string]int)

// Предположим, хэши "key1" и "key2" указывают на один и тот же бакет.
// Это и есть коллизия.
m["key1"] = 1
m["key2"] = 2

// Внутри бакета №N теперь будет что-то вроде списка: [("key1", 1), ("key2", 2)]

Важные аспекты

• Производительность: При большом количестве коллизий в одном бакете производительность map деградирует. В худшем случае, когда все ключи попадают в один бакет, время доступа превращается из O(1) в O(n).
• Автоматическое расширение: Чтобы минимизировать коллизии, Go runtime отслеживает коэффициент загрузки (load factor). Когда map становится слишком заполненной, Go автоматически выделяет больший массив бакетов и перераспределяет все элементы (rehashes). Этот процесс для пользователя прозрачен.