Hashing von Ganzzahlsätzen für Inklusionstests

Ich suche nach einer Hash-Funktion über Mengen H (.) Und einer Beziehung R (.,.), So dass, wenn A in B enthalten ist, R (H (A), H (B)). Natürlich muss R (.,.) Leicht zu überprüfen sein (konstante Zeit), und H (A) sollte in linearer Zeit berechnet werden.

Ein Beispiel für H und R ist:

• , wobei k eine feste ganze Zahl und h (x) eine Hash-Funktion über ganze Zahlen ist.$H(A) = \bigvee_{x\in A} 1 << (h(x) \mod k)$
• R (H (A), H (B)) = ((H (A) & H (B)) == H (A))

Gibt es noch andere gute Beispiele? (gut ist schwer zu definieren, aber intuitiv, wenn R (H (A), H (B)), dann ist whp A in B enthalten).

Später bearbeiten :

1. Ich suche eine Familie von Hash-Funktionen. Ich habe viele Sätze; 3 - 8 Elemente in jedem Satz; 90% von ihnen haben 3 oder 4 Elemente. Die Beispiel-Hash-Funktion, die ich angegeben habe, ist für diesen Fall nicht sehr gut verteilt.
2. Die Anzahl der Bits von H (.) (In meinem Beispiel k), die klein sein sollten (dh H (.) Muss in eine ganze Zahl oder lang passen).
3. Eine schöne Eigenschaft von R ist, dass wenn H (.) K Bits hat, R (.,.) Für (3 ^ k - 2 ^ k) / 4 ^ k Paare gilt, dh. für sehr wenige Paare.
4. Bloom-Filter eignen sich besonders für große Sets. Ich habe versucht, BF für dieses Problem zu verwenden, aber die optimalen Ergebnisse wurden mit nur einer Funktion erzielt.

(Crosspost von Stackoverflow , ich habe keine gute Antwort erhalten)

(Diese Antwort war ursprünglich in Kommentaren enthalten, aber ich verschiebe sie auf Sureshs Vorschlag hin zu einer separaten Antwort.)

$k$$h_1$$h_2$$h_3$$m$$2^{-3}=1/8^{th}$Einsen. Hash jeder Satz auf das bitweise oder auf die Hashes seiner Bestandteile. Da Ihre Sets 3-8 Elemente enthalten, befinden sich die resultierenden Hashes in der Nähe der Hälfte. Dies ist vermutlich das, was Sie am besten möchten, um die Falsch-Positiv-Rate niedrig zu halten.

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

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