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

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

Структура и процесс

1. Массив бакетов (buckets): map внутри представляет собой массив указателей на бакеты.
2. Вычисление хеша: Когда вы добавляете или ищете элемент, Go вычисляет хеш-функцию от ключа.
3. Определение бакета: Младшие биты хеша используются как индекс для определения, в какой бакет попадёт ключ.
4. Разрешение коллизии:
   • Каждый бакет — это небольшая структура, которая может хранить до 8 пар ключ-значение.
   • Если два разных ключа попадают в один и тот же бакет, они размещаются в нём последовательно.
   • При поиске элемента Go сначала находит нужный бакет по хешу, а затем линейно перебирает элементы внутри этого бакета, сравнивая уже не хеши, а сами ключи.
   • Если бакет переполняется (более 8 элементов), создается дополнительный "overflow" бакет, и они связываются в односвязный список.

Производительность

• Средний случай: O(1). Операция выполняется очень быстро, так как в большинстве случаев в бакете находится всего несколько элементов.
• Худший случай: O(n). Если все ключи попадают в один бакет (из-за плохой хеш-функции или специально подобранных данных), поиск превращается в линейный перебор по связанному списку бакетов.

Важное замечание: Начиная с Go 1.12, для строковых ключей используется качественный криптографический хеш-алгоритм (на базе AES), который делает преднамеренное создание коллизий (hash flooding attack) практически невозможным.