Коллизии (Hash Collisions)
Хеш-функции не являются совершенными: иногда совершенно разные данные могут приводить к одинаковому хеш-значению. Из-за этого пропадает взаимно-однозначное соответствие между входными данными и хешем. В итоге разные строки могут иметь один и тот же хеш, или пара чисел может совпадать по хеш-значению. Такие коллизии могут приводить как к проблемам безопасности, так и к снижению производительности в зависимости от конкретной ситуации. Например, простая хеш-функция, которая сопоставляет паре чисел (a, b) некоторый результат, может отобразить множество разных пар (a, b) в одно и то же хеш-значение:
Ниже приведено несколько примеров пар
(a, b), дающих одинаковый хеш-результат:- h(1, 1) = (1997 + 1) mod 5077 = 1998
- h(1, 5078) = (1997 + 5078) mod 5077 = 1998
- h(5078, 1) = (10140766 + 1) mod 5077 = 1998
- …
Таким образом, если бы мы специально составили список пар, которые все дают одинаковый хеш, мы столкнулись бы с многочисленными коллизиями. Из-за этого поиск нужного значения или проверка, присутствует ли в списке пара
(a, b), могли бы стать крайне неэффективными или даже приводить к неверным результатам (в зависимости от реализации).Коллизии хеша могут представлять серьёзную угрозу в плане безопасности. Пользовательские пароли обычно хранятся в виде хешей (чтобы, даже если база данных утечёт, настоящие пароли не были скомпрометированы). Если же хеш-функция неудачна и вызывает множество коллизий, злоумышленники могут получить доступ к учётной записи без подбора правильного пароля. Достаточно, чтобы хеш случайного пароля совпал с хешем настоящего, и система посчитает, что это один и тот же пользователь.
Хорошая хеш-функция позволяет свести количество коллизий к минимуму. В большинстве случаев встроенные функции хеширования отлично справляются со случайными входными данными. Однако, если входные данные или условия задачи предполагают особые требования, может понадобиться собственная реализация хеш-функции.
Challenge: Check for Collisions
Допустим, у нас есть хеш-функция
h, которая сопоставляет паре целых чисел (a, b) некоторое целое значение. Нужно выяснить, достаточно ли хорошо она работает для заданных данных. Программа должна проверять наличие коллизий и выводить Yes, если коллизий нет, и No — в противном случае. Хеш-функция задаётся так:Input
Первая строка входных данных содержит целое число
n (1 ≤ n ≤ 10 000), указывающее количество пар.В следующих
n строках находятся пары целых чисел (0 ≤ ≤ ), разделённые пробелом. Гарантируется, что все пары уникальны.Output
Программа должна вывести
Yes, если при данных входных данных функции h(a, b) удалось избежать коллизий, и No в противном случае.Examples
Входные данные | Выходные данные |
3
0 4
1 5
2 9 | Yes |
2
0 0
0 1
542313474 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB