Хеширование наборов целых чисел

Question

Я ищу хэш-функцию для множеств H (.) И отношения R (.,.), Чтобы, если A включается в B, то R (H (A), H (B)).Конечно, R (.,.) Должно легко проверяться (постоянное время), а H (A) должно рассчитываться за линейное время.

Один из примеров H и R:

• H (A) = ИЛИ более 1 << (h (x)% k), для x в A k фиксированное целое число и h (x) хеш-функция над целыми числами. </li>
• R (H (A), H (B)) = ((H (A) и H (B)) == H (A))

Есть ли другие хорошие примеры?(хорошо трудно определить, но интуитивно понятно, если R (H (A), H (B)), тогда whp A включен в B).

Answer 1

• Подумав об этом, я закончил с примером, который вы привели. То есть каждый элемент в B устанавливает бит в хэше, и A содержится только в B, если каждый бит, установленный в H (A), также установлен в H (B).
• Может быть, Фильтр Блума применим в вашем случае. Кажется, он использует тот же битовый трюк, но с несколькими хэш-функциями.