FLAJOLET-MARTIN ALGORITHM: Frage zur Verwendung bestimmter Hash-Funktionen

Question

Dies ist eine Frage, die in einem PDF über Streaming-Algorithmen angegeben ist (dies ist keine Aufgabe, aber ich versuche es zu verstehen)

Übung 4.4.1 : Angenommen, unser Strom besteht aus den Ganzzahlen 3, 1, 4, 1, 5, 9, 2, 6, 5. Unsere Hash-Funktionen sind alle aus dem Formular H (x)= AX + B MOD 32 für einige A und B. Sie sollten das Ergebnis als 5-Bit behandeln Binäre Ganzzahl. Bestimmen Sie die Schwanzlänge für jedes Stream-Element und die resultierende Schätzung der Anzahl unterschiedlicher Elemente, wenn der Hash Funktion ist:

(a) h (x)= 2x + 1 mod 32.

(b) h (x)= 3x + 7 mod 32.

(c) h (x)= 4x mod 32.

! Übung 4.4.2 : Sehen Sie Probleme mit der Wahl der Hash Funktionen in der Übung 4.4.1? Welchen Rat könnten Sie jemandem geben, der Wird eine Hashfunktion des Formulars H (x)= AX + B MOD 2K verwenden?

Ich habe die erste Übung bereits gelöst, und findet eine maximale Rückenlänge von 0 für (A) und 4 für (B) und (b) und (c), daher beträgt die resultierende Abschätzung verschiedener Elemente jeweils 1,16,16. (Es wird nicht aufgefordert, Durchschnittswerte / Mediane der Hash-Funktionen, um einen besseren Wert zu finden)

Ich kann jedoch nicht die Antwort auf den zweiten Übungsarbeit erstellen? Ist es einfach auf eine bestimmte Weise "A" und "B" zu wählen? Oder sind diese Funktionen nicht gut, um gleichmäßig zufällige Zahlen mit nachlaufenden 0s zu erzeugen, und kein Trailing 0s?

Vielen Dank im Voraus

Sie können die Ergebnisse jeder Hash-Funktionen beobachten, indem Sie diesen Code ausführen: https://onlinegdb.com/rjxc4f4vl

Answer 1

Ich kann jedoch nicht die Antwort auf den zweiten Übungsarbeit erstellen?Ist es einfach auf eine bestimmte Weise "A" und "B" zu wählen?Oder sind diese Funktionen nicht gut, um gleichmäßig zufällige Zahlen mit nachlaufenden 0s zu erzeugen, und kein Trailing 0s?

Sie haben die richtige Idee.Ich glaube, was die Frage versucht, vorzuschlagen, dass diese Hash-Funktion ein Problem mit bestimmten Werten von $ A $ und $ hatB $ .Betrachten Sie insbesondere $ A= 16 $ .Was passiert in diesem Fall mit der Hash-Funktion?Wie viele mögliche Werte gibt es?

Um einen guten Wert von $ A $ auszuwählen, sollten wir wahrscheinlich sicherstellen, dass $ A= 16 $ ist nicht erlaubt. $ A= 8 $ ist auch nicht gut.Was Sie vorschlagen, ist eine gute Wahl für $ A $ ?