Модуль: Хеширование

Помимо последовательностей можно также хэшировать множества. То есть наборы объектов без порядка на них. Считается он по следующей формуле:
hash(A) = \(\sum_{a \in A} p^{ord(a)}\)   <- считая все по модулю mod
где ord - функция, которая сопоставляет объекту множества его абсолютный порядковый номер среди всех возможных объектов (например, если объекты - натуральные числа, то ord(x) = x, а если строчные латинские буквы, то ord('a') = 1, ord('b') = 2 и т.д.)

То есть каждому объекту мы сопоставляем величину равную основанию в степени номера этого объекта и суммируем все эти величины для того, чтобы получить хэш всего множества. Как понятно из формулы, хэш легко пересчитывается, если в множество добавляется элемент или удаляется из него (просто добавляем или вычитаем необходимую величину). Такая же логика,  если добавляются или удаляются не одиночные элементы, а другие множества (просто добавляем/вычитаем их хэш).

Как вы уже могли понять, одиночные элементы рассматриваются как множества размера 1, для которых мы умеем считать хэш. А более крупные множества просто являются объединением таким единичных множеств, где объединяя множества, мы складываем их хэши.

На самом деле это все тот же полиномиальный хэш, но раньше коэффициентом при p^m у нас было значение элемента последовательности под номером n - m - 1 (где n - длина последовательности), а теперь это количество элементов в множестве, у которых абсолютный порядковый номер равен m.

В таком хэшировании необходимо брать достаточно большое основание (большее, чем максимальный размер множества), либо использовать двойное хэширование, чтобы избежать ситуаций, когда множество из p объектов с абсолютным порядковым номером m имеюют тот же хэш, что и множество с одним объектом с абсолютным порядковым номером m+1.