Hashing conjuntos de enteros para pruebas de inclusión

Estoy buscando una función hash sobre los conjuntos H (.) Y una relación R (.,.) Tal que si A está incluida en B, entonces R (H (A), H (B)). Por supuesto, R (.,.) Debe ser fácil de verificar (tiempo constante) y H (A) debe calcularse en tiempo lineal.

Un ejemplo de H y R es:

• , donde k es un entero fijo y h (x) una función hash sobre enteros.$H(A) = \bigvee_{x\in A} 1 << (h(x) \mod k)$
• R (H (A), H (B)) = ((H (A) y H (B)) == H (A))

¿Hay otros buenos ejemplos? (bueno es difícil de definir pero intuitivamente si R (H (A), H (B)) entonces whp A está incluido en B).

Edición posterior :

1. Estoy buscando una familia de funciones hash. Tengo muchos juegos; 3 - 8 elementos en cada conjunto; El 90% de ellos tienen 3 o 4 elementos. El ejemplo de función hash que proporcioné no está muy bien distribuido para este caso.
2. El número de bits de H (.) (En mi ejemplo, k) que debe ser pequeño (es decir, H (.) Debe caber en un entero o largo).
3. Una buena propiedad de R es que si H (.) Tiene k bits, entonces R (.,.) Es verdadero para (3 ^ k - 2 ^ k) / 4 ^ k pares, es decir. por muy pocos pares.
4. Los filtros Bloom son especialmente buenos para conjuntos grandes. Intenté usar BF para este problema, pero los resultados óptimos fueron con una sola función.

(crosspost de stackoverflow , no recibí una respuesta lo suficientemente buena)

(Esta respuesta estaba originalmente en los comentarios, pero la estoy moviendo a otra respuesta por sugerencia de Suresh).

$k$$h_1$$h_2$$h_3$$m$$2^{-3}=1/8^{th}$unos. Hash cada conjunto al bit o de los hashes de sus elementos constituyentes. Debido a que sus conjuntos tienen de 3 a 8 elementos, los hashes resultantes estarán cerca de la mitad, lo que presumiblemente es lo que desea para mantener baja la tasa de falsos positivos.

$G_{n,p}$$d$$k$$m/8$$m/8$

$m$$k$$m=64$$k=4$