Есть ли хеш-функция для набора (то есть, множества) целых чисел, которое имеет хорошие теоретические гарантии?

36

Мне любопытно, есть ли способ хранить хэш из нескольких множеств целых чисел, который в идеале имеет следующие свойства:

  1. Использует пространство O (1)
  2. Его можно обновить, чтобы отразить вставку или удаление за время O (1).
  3. Две идентичные коллекции (т. Е. Коллекции, имеющие одинаковые элементы с одинаковыми кратностями) должны всегда хэшировать одно и то же значение, а две разные коллекции должны хэшировать разные значения с высокой вероятностью (т. Е. Функция независима или попарно независима)

Первой попыткой было бы сохранить произведение по модулю случайного простого числа хешей отдельных элементов. Это удовлетворяет 1 и 2, но не ясно, удовлетворит ли это, или близкое изменение, 3.

Я первоначально отправил это на StackOverflow .

* Свойства 1 и 2 могут быть немного смягчены, скажем, до O (log n) или небольшого сублинейного полинома. Дело в том, чтобы увидеть, можем ли мы идентифицировать множественные множества и надежно проверить равенство, не сохраняя сами элементы.

jonderry
источник
Какое у вас представление о мультимножествах? Т.е. как вы кодируете мультимножество как битовую строку? Если вы действительно хотите получить -временные операции (независимо от размера мультимножества), я думаю, вы должны сделать кодировку явной. O(1)
Юкка Суомела
Кодирование наборов неважно. Хеш-функция должна быть независимой от представления множеств. Если бы я использовал каноническое представление хеш-набора, то любой стандартный хэш в битовом представлении набора удовлетворял бы 3 и, вероятно, 1, но не 2. Я должен добавить, что две равные коллекции должны всегда хэшировать к одному и тому же значению.
Jonderry
Что именно вы подразумеваете под 2? Получаете ли вы старый набор, старый хеш-код и новый элемент, и вы хотите вычислить новый хеш-код? Или вы получаете только старый хэш-код и новый элемент?
Михай
В идеале вам не понадобится старый набор. Вам даже не нужно иметь возможность выполнять запросы членов (важно, учитывая ограничения пространства), только тестирование на равенство, возможно, путем сравнения значений хеш-функции, которые имеют низкую вероятность ложного срабатывания.
Jonderry

Ответы:

17

Если вы думаете о множествах как о живущих во вселенной , решить проблему с помощью времени обновления довольно легко . Все, что вам нужно, это быстрая функция хеширования для вектора чисел с быстрыми «локальными обновлениями».[u]O(lgu)u

Википедия / Универсальное хеширование предлагает , где - достаточно большое простое число, а равномерно взят из . Когда вы добавляете или удаляете элемент , вы должны добавить / вычесть из хеш-кода, что занимает время с использованием деления и завоевания для возведения в степень. Поскольку полином степени может иметь только корни , вероятность столкновения для двух различных множеств равна . Это можно сделать очень маленьким, если взять достаточно большим (например,h(x)=(i=1uxiai)modppa[p]iaiO(lgi)uuO(u/p)pp=u2а ты работаешь в "двойной точности"). Если наборы намного меньше, чем , вы, конечно, можете начать с хэширования вселенной до меньшей вселенной.[u]

Кто-нибудь знает решение с вероятностью столкновения при хешировании до диапазона ? Это должно быть возможно.O(1/p)[p]

Михай
источник
0

Картер и Вегман освещают это в новых хэш-функциях и их использовании в аутентификации и установлении равенства ; это очень похоже на то, что вы описываете. По существу, коммутативная хеш-функция может обновляться по одному элементу за раз для вставок и удалений, а также совпадений с высокой вероятностью в O (1).

KWillets
источник
Я думаю, что это работает только на наборах, а не на мультимножествах (как вопрос задан). Из раздела 5 внизу страницы 274: «ADD (x, S) - добавляет элемент x к набору с именем S. Эта операция может не использоваться, если x уже является членом S.»
jbapple
Вы правы; Я пропустил "мульти" часть. Кажется вероятным, что хеш-функция может обрабатывать дубликаты, хотя у меня нет для этого ссылки.
KWillets
-2

Качество хеш-функции всегда будет зависеть от свойств элементов, которые она должна хешировать. Можешь что-нибудь сказать по этому поводу? Например, предложение вашего продукта, вероятно, является плохой хеш-функцией, если элементы x_i вашего мультимножества обычно имеют много небольших простых факторов. Но вы можете улучшить его в этом случае, просто взяв произведение всех x_i + p mod q на некоторые простые числа p и q.

TonyK
источник
1
Да, это причина взятия хешей отдельных элементов перед их умножением.
Jonderry
Какая? ОП предлагает просто умножить их все вместе, не так ли? Я говорю, что если вы добавите константу к каждому перед тем, как сделать это, вы, вероятно, получите лучший хеш.
TonyK
-5
A = 0x4F1BBCDD
B = 0x314EFB75
A*B = 1 
N = size of set before addition/removal<P>
Add X
H = (H-N)*B
U = H >> 16
V = H & 0xFFFF
H = (((U+X)&M)<<16) + ((V^X)&M)
H *= A
H += N+1

Remove X
H = (H-N)*B
U = H >> 16
V = H & 0xFFFF
H = (((U-X)&M)<<16) + ((V^X)&M)
H *= A
H += N-1

сумма позволяет нам иметь несколько вхождений одного и того же значения,
а xor позволяет нам иметь наборы с одинаковой суммой

Луи Рейниц
источник