Ответ
Хеш-коллизия — это ситуация, когда хеш-функция генерирует одинаковый хеш-код для двух или более разных ключей. Это неизбежное явление, поскольку количество возможных ключей часто бесконечно, а количество возможных хеш-кодов ограничено размером хеш-таблицы.
Как Go обрабатывает коллизии в map?
Go использует метод цепочек (chaining). Каждый элемент массива (бакет) в реализации map является указателем на связанный список (или похожую структуру) пар ключ-значение.
- Когда вы добавляете новый элемент, Go вычисляет хеш ключа и определяет номер бакета.
- Если бакет пуст, новый элемент помещается в него.
- Если в бакете уже есть элементы (из-за коллизии), Go проходит по цепочке элементов в этом бакете и сравнивает искомый ключ с ключами в цепочке.
- Если ключ найден, значение обновляется.
- Если ключ не найден, новая пара ключ-значение добавляется в конец цепочки.
Последствия коллизий:
- Снижение производительности: Вместо мгновенного доступа по индексу (O(1)), системе приходится перебирать элементы в цепочке, что в худшем случае приводит к сложности O(n). Для защиты от этого Go использует качественные хеш-функции и механизм перебалансировки таблицы при её заполнении.
- Атаки на отказ в обслуживании (Hash-DoS): Злоумышленник может намеренно подобрать ключи, которые вызывают максимальное количество коллизий, чтобы замедлить работу системы. В современных версиях Go в хеш-функцию для строк добавляется случайное "зерно" (seed) при старте программы, что делает такие атаки труднореализуемыми.