Хеширование множеств (с точностью до перестановки): различия между версиями
м |
|||
| Строка 8: | Строка 8: | ||
Сопоставим каждому ключу различные случайные числа (будем называть их хешом ключа) от $0$ до некоторого $M$ (в целом, можно и по модулю $MAX\_LONGLONG$ ), а хешом множества будет считать сумму хешей всех входящих в него ключей. Тогда, очевидно, хеши равных (с точностью до перестановки) множеств будут одинаковые из-за коммутативности сложения, а вероятность коллизий при таком подходе в условиях олимпиад можно считать пренебрежимо малой. | Сопоставим каждому ключу различные случайные числа (будем называть их хешом ключа) от $0$ до некоторого $M$ (в целом, можно и по модулю $MAX\_LONGLONG$ ), а хешом множества будет считать сумму хешей всех входящих в него ключей. Тогда, очевидно, хеши равных (с точностью до перестановки) множеств будут одинаковые из-за коммутативности сложения, а вероятность коллизий при таком подходе в условиях олимпиад можно считать пренебрежимо малой. | ||
| + | |||
| + | {{Автор|Александр Гришутин|rationalex}} | ||
Текущая версия на 16:43, 4 февраля 2020
Задача
Хотим научиться сравнивать множества чисел/строк на равенство с точностью до перестановки. Например, $\{1, 2, 3\} = \{2, 1, 3\} \\ \{"lal", "abc"\} = \{"abc", "lal"\} \\ \{4, 5\} \neq \{5, 6\} \\ \{"lal", "abc"\} \neq \{"abc", "all"\}$ .
При этом мы знаем, что количество различных значений, которые могут принимать ключи(объекты, которые лежат в множествах) невелико.
Решение
Сопоставим каждому ключу различные случайные числа (будем называть их хешом ключа) от $0$ до некоторого $M$ (в целом, можно и по модулю $MAX\_LONGLONG$ ), а хешом множества будет считать сумму хешей всех входящих в него ключей. Тогда, очевидно, хеши равных (с точностью до перестановки) множеств будут одинаковые из-за коммутативности сложения, а вероятность коллизий при таком подходе в условиях олимпиад можно считать пренебрежимо малой.
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex