Мне любопытно, есть ли способ хранить хэш из нескольких множеств целых чисел, который в идеале имеет следующие свойства:
- Использует пространство O (1)
- Его можно обновить, чтобы отразить вставку или удаление за время O (1).
- Две идентичные коллекции (т. Е. Коллекции, имеющие одинаковые элементы с одинаковыми кратностями) должны всегда хэшировать одно и то же значение, а две разные коллекции должны хэшировать разные значения с высокой вероятностью (т. Е. Функция независима или попарно независима)
Первой попыткой было бы сохранить произведение по модулю случайного простого числа хешей отдельных элементов. Это удовлетворяет 1 и 2, но не ясно, удовлетворит ли это, или близкое изменение, 3.
Я первоначально отправил это на StackOverflow .
* Свойства 1 и 2 могут быть немного смягчены, скажем, до O (log n) или небольшого сублинейного полинома. Дело в том, чтобы увидеть, можем ли мы идентифицировать множественные множества и надежно проверить равенство, не сохраняя сами элементы.
Ответы:
Если вы думаете о множествах как о живущих во вселенной , решить проблему с помощью времени обновления довольно легко . Все, что вам нужно, это быстрая функция хеширования для вектора чисел с быстрыми «локальными обновлениями».[u] O(lgu) u
Википедия / Универсальное хеширование предлагает , где - достаточно большое простое число, а равномерно взят из . Когда вы добавляете или удаляете элемент , вы должны добавить / вычесть из хеш-кода, что занимает время с использованием деления и завоевания для возведения в степень. Поскольку полином степени может иметь только корни , вероятность столкновения для двух различных множеств равна . Это можно сделать очень маленьким, если взять достаточно большим (например,h(x⃗ )=(∑ui=1xiai)modp p a [p] i ai O(lgi) u u O(u/p) p p=u2 а ты работаешь в "двойной точности"). Если наборы намного меньше, чем , вы, конечно, можете начать с хэширования вселенной до меньшей вселенной.[u]
Кто-нибудь знает решение с вероятностью столкновения при хешировании до диапазона ? Это должно быть возможно.O(1/p) [p]
источник
Картер и Вегман освещают это в новых хэш-функциях и их использовании в аутентификации и установлении равенства ; это очень похоже на то, что вы описываете. По существу, коммутативная хеш-функция может обновляться по одному элементу за раз для вставок и удалений, а также совпадений с высокой вероятностью в O (1).
источник
Качество хеш-функции всегда будет зависеть от свойств элементов, которые она должна хешировать. Можешь что-нибудь сказать по этому поводу? Например, предложение вашего продукта, вероятно, является плохой хеш-функцией, если элементы x_i вашего мультимножества обычно имеют много небольших простых факторов. Но вы можете улучшить его в этом случае, просто взяв произведение всех x_i + p mod q на некоторые простые числа p и q.
источник
сумма позволяет нам иметь несколько вхождений одного и того же значения,
а xor позволяет нам иметь наборы с одинаковой суммой
источник