Хеширование множеств

Полиномиальный хеш чувствителен к порядку — на то он и полиномиальный. Иногда нужно обратное: чтобы хеш зависел только от состава.

Типичная задача: даны наборы чисел, надо быстро проверять, состоят ли два набора из одних и тех же элементов.

Идея

Сопоставим каждому возможному значению случайное 64-битное число. Хеш набора — комбинация случайных чисел его элементов операцией, которая не зависит от порядка.

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
map<long long, unsigned long long> randomOf;

unsigned long long randFor(long long x) {
    auto it = randomOf.find(x);
    if (it != randomOf.end()) return it->second;
    return randomOf[x] = rng();
}

Словарь нужен, чтобы одному значению всегда соответствовало одно случайное число. Если элементы ограничены небольшим диапазоном, вместо словаря заведите массив — быстрее.

Множество: XOR

unsigned long long h = 0;
for (long long x : a) h ^= randFor(x);

Добавление и удаление элемента — одна и та же операция: h ^= randFor(x). Это удобно: XOR обратен сам себе.

Вероятность коллизии — примерно $2^{-64}$: каждый бит результата независимо равновероятен.

Важное свойство: XOR игнорирует кратность. Два одинаковых элемента взаимно уничтожаются. Для множества это правильно, для мультимножества — нет.

Мультимножество: сумма

unsigned long long h = 0;
for (long long x : a) h += randFor(x);   // переполнение здесь допустимо

Сложение по модулю $2^{64}$, то есть обычное переполнение unsigned long long. Здесь оно безопасно: против такого хеша нет структурного взлома вроде строк Туэ — Морса, потому что значения случайны и заранее неизвестны.

Удаление — вычитание. Кратность учитывается.

Проверено: на ста тысячах случайных наборов оба хеша не меняются при перестановке элементов; при этом хеш множества не замечает добавления дубликатов, а хеш мультимножества — замечает.

Почему нужна случайность

Соблазн взять randFor(x) = x и просто складывать значения. Так делать нельзя: наборы $\{1, 4\}$ и $\{2, 3\}$ дадут одинаковую сумму, и контрпример строится мгновенно.

Случайные числа убирают всякую структуру: чтобы подобрать коллизию, нужно решить задачу о сумме подмножества над случайными 64-битными числами, а это безнадёжно.

Именно поэтому сид должен быть случайным, а не фиксированным. С фиксированным сидом противник может воспроизвести ваши случайные числа и подобрать тест.

Онлайн-вариант

Если значения приходят по ходу и заранее неизвестны, словарь заполняется лениво — как в коде выше. Память тогда линейна от числа различных встреченных значений, а не от диапазона.

Если запросы можно прочитать заранее, проще сжать координаты и работать массивом.

Что это позволяет

Сравнение мультимножеств на равенство за константу после линейного предподсчёта.

Скользящее окно. Хеш окна поддерживается при сдвиге двумя операциями: убрать вышедший элемент, добавить вошедший. Отсюда — «сколько окон длины $k$ содержат тот же набор, что образец».

Проверка, что два массива — перестановки друг друга. Сравнить хеши мультимножеств. Проще сортировки и работает за линию.

Анаграммы. То же самое для строк.

Хеш подмножества по маске. Если элементов немного, хеш каждого подмножества считается динамикой по маскам.