Gibt es eine Hash-Funktion für eine Sammlung (dh mehrere Mengen) von ganzen Zahlen, die gute theoretische Garantien bietet?

36

Ich bin neugierig, ob es eine Möglichkeit gibt, einen Hash aus mehreren Ganzzahlen zu speichern, der im Idealfall die folgenden Eigenschaften aufweist:

  1. Es verwendet O (1) Raum
  2. Es kann aktualisiert werden, um das Einfügen oder Löschen in O (1) -Zeit wiederzugeben
  3. Zwei identische Sammlungen (dh Sammlungen, die die gleichen Elemente mit den gleichen Multiplizitäten aufweisen) sollten immer auf den gleichen Wert gehasht werden, und zwei unterschiedliche Sammlungen sollten mit hoher Wahrscheinlichkeit auf verschiedene Werte gehasht werden (dh die Funktion ist unabhängig oder paarweise unabhängig).

Ein erster Versuch dabei wäre, das Produkt modulo in einer zufälligen Primzahl der Hashes der einzelnen Elemente zu speichern. Dies erfüllt 1 und 2, aber es ist nicht klar, ob es oder eine enge Variation 3 erfüllen würde.

Ich habe das ursprünglich auf StackOverflow gepostet .

* Die Eigenschaften 1 und 2 könnten ein wenig gelockert werden, beispielsweise auf O (log n) oder ein kleines sublineares Polynom. Der Punkt ist zu sehen, ob wir Mehrfachmengen identifizieren und die Gleichheit zuverlässig testen können, ohne die Elemente selbst zu speichern.

jonderry
quelle
Was ist Ihre Darstellung von Multisets? Dh, wie kodiert man ein Multiset als Bitstring? Wenn Sie wirklich -Zeitoperationen erhalten möchten (unabhängig von der Größe des Multisets), sollten Sie die Codierung explizit angeben. O(1)
Jukka Suomela
Die Kodierung der Sets ist unwichtig. Die Hash-Funktion sollte unabhängig von der Darstellung der Mengen sein. Wenn ich eine kanonische Darstellung einer Hash-Menge verwenden würde, würde jeder Standard-Hash auf der Bit-Darstellung der Menge 3 und wahrscheinlich 1, aber nicht 2 erfüllen. Ich sollte hinzufügen, dass zwei gleiche Sammlungen immer den gleichen Wert haben sollten.
jonderry
Was genau meinst du mit 2? Erhalten Sie die alte Menge, den alten Hash-Code und das neue Element und möchten Sie den neuen Hash-Code berechnen? Oder bekommen Sie nur den alten Hash-Code und das neue Element?
Mihai
Idealerweise würden Sie das alte Set nicht brauchen. Sie müssen nicht einmal in der Lage sein, Mitgliederabfragen (wichtig angesichts der Platzbeschränkungen) durchzuführen, sondern lediglich Gleichheitstests durchzuführen, wahrscheinlich durch Vergleichen von Hash-Werten, bei denen die Wahrscheinlichkeit eines falschen Positivs gering ist.
Jonderry

Antworten:

17

Wenn Sie Sätze wie das Leben in Weltall denken , ist es ganz einfach , Ihr Problem mit lösen O ( lg u ) Aktualisierungszeit. Alles, was Sie brauchen, ist eine schnelle Hash-Funktion für einen Vektor von u- Zahlen mit schnellen "lokalen Aktualisierungen".[u]O(lgu)u

Wikipedia / Universal Hashing schlägt vor, dass , wobei p eine ausreichend große Primzahl ist und a gleichmäßig aus [ p ] gezogen wird . Wenn Sie das Element i hinzufügen oder entfernen , müssen Sie ein i zum Hash-Code hinzufügen / davon subtrahieren , was O ( lg i ) Zeit mit dividieren und erobern für die Exponentiation benötigt. Da ein Polynom vom Grad uh(x)=(i=1uxiai)modppa[p]iaiO(lgi)uKann nur Wurzeln haben, ist die Kollisionswahrscheinlichkeit für zwei verschiedene Mengen O ( u / p ) . Dies kann sehr klein gemacht werden, indem p als groß genug angenommen wird (zum Beispiel p = u 2 und Sie arbeiten mit "doppelter Genauigkeit"). Wenn die Mengen viel kleiner als [ u ] sind , können Sie das Universum natürlich zunächst in ein kleineres Universum zerlegen.uO(u/p)pp=u2[u]

Kennt jemand eine Lösung mit -Kollisionswahrscheinlichkeit, wenn das Hashing auf [ p ] liegt ? Das sollte möglich sein.O(1/p)[p]

Mihai
quelle
0

Carter und Wegman behandeln dies in New-Hash-Funktionen und deren Verwendung bei der Authentifizierung und bei der Einstellung der Gleichheit . es ist dem, was du beschreibst, sehr ähnlich. Grundsätzlich kann eine kommutative Hash-Funktion für Einfügungen und Löschungen und Übereinstimmungen mit hoher Wahrscheinlichkeit in O (1) jeweils für ein Element aktualisiert werden.

KWillets
quelle
Ich denke, das funktioniert nur bei Sets, nicht bei Multisets (wie bei der gestellten Frage). Aus Abschnitt 5, am Ende der Seite 274: "ADD (x, S) - Fügt das Element x der Menge mit dem Namen S hinzu. Diese Operation kann nicht verwendet werden, wenn x bereits Mitglied von S ist."
Jbapple
Du hast recht; Ich habe den "multi" Teil verpasst. Es ist wahrscheinlich, dass eine Hash-Funktion mit Duplikaten umgehen kann, obwohl ich kein Zitat dafür habe.
KWillets
-2

Die Qualität einer Hash-Funktion hängt immer von den Eigenschaften der zu hashenden Elemente ab. Können Sie dazu etwas sagen? Zum Beispiel ist Ihr Produktvorschlag wahrscheinlich eine schlechte Hash-Funktion, wenn die Elemente x_i Ihres Multisets typischerweise viele kleine Primfaktoren haben. Aber Sie können es in diesem Fall einfach verbessern, indem Sie das Produkt von allen x_i + p mod q für einige Primzahlen p und q nehmen.

TonyK
quelle
1
Ja, das ist der Grund, die Hashes der einzelnen Elemente zu nehmen, bevor sie miteinander multipliziert werden.
jonderry
Was? Der Vorschlag des OP ist einfach, sie alle zusammen zu multiplizieren, nicht wahr? Ich sage, wenn Sie jedem eine Konstante hinzufügen, bevor Sie dies tun, erhalten Sie wahrscheinlich einen besseren Hash.
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

Mit der Summe können wir mehrere Vorkommen desselben Werts haben. Mit
xor können wir die Summe auf den gleichen Betrag setzen

Louis Reinitz
quelle