Ich versuche, einen Count-Min-Sketch -Algorithmus in Scala zu implementieren, und so muss ich generieren k paarweise unabhängige Hash-Funktionen.
Dies ist eine niedrigere Ebene als alles, was ich jemals programmiert habe, und ich weiß nicht viel über Hash-Funktionen außer den Algorithmen-Klassen. Meine Frage ist also: Wie erzeuge ich diese k paarweisen unabhängigen Hash-Funktionen? / p>
Soll ich eine Hash-Funktion wie MD5 oder MurmurHash verwenden? Generiere ich einfach k Hash-Funktionen der Form f(x) = ax + b (mod p) , wobei p eine Primzahl ist und a und b zufällige ganze Zahlen sind? (d. h. die universelle Hashing-Familie lernt jeder in Algorithmen 101)
Ich suche mehr nach Einfachheit als nach roher Geschwindigkeit (z. B. nehme ich etwas 5x langsamer, wenn es einfacher zu implementieren ist).
Scala hat bereits MurmurHash implementiert (es ist scala.util.MurmurHash ). Es ist sehr schnell und sehr gut darin, Werte zu verteilen. Ein kryptografischer Hash ist übertrieben - Sie brauchen nur einige zehn oder hundert Mal länger als nötig. Wählen Sie einfach k verschiedene Startwerte und, da es fast kryptografisch ist, erhalten Sie k weitgehend unabhängige Hashcodes. (In 2.10 sollten Sie wahrscheinlich scala.util.hashing.MurmurHash3 verwenden; die Verwendung ist etwas anders, aber Sie können immer noch dasselbe mit dem Mischen tun.)
Wenn Sie nur Werte in der Nähe benötigen, die zufällig großen Werten zugeordnet werden, funktioniert dies; Wenn Sie Kollisionen vermeiden wollen (dh wenn A und B mit Hash 1 kollidieren, kollidieren sie wahrscheinlich auch nicht mit Hash 2), dann müssen Sie mindestens einen weiteren Schritt gehen und nicht das gesamte Objekt, sondern die Unterkomponenten davon hashen Es gibt eine Möglichkeit für die Hashes, anders zu beginnen.
Der wahrscheinlich einfachste Ansatz besteht darin, eine kryptografische Hashfunktion zu verwenden und sie mit verschiedenen Bytefolgen zu "säen". Für die meisten praktischen Zwecke sollten die Ergebnisse unabhängig sein, da dies eine der Schlüsseleigenschaften ist, die eine kryptografische Hash-Funktion haben sollte (wenn Sie einen Teil einer Nachricht ersetzen, sollte der Hash völlig anders sein).
Ich würde etwas tun wie:
%Vor%Bearbeiten: Ich kenne die genauen Anforderungen der Count-Min-Sketch nicht, vielleicht würde eine einfache has-Funktion ausreichen, aber es scheint nicht die einfachste Lösung zu sein.
Ich habe eine kryptografische Hash-Funktion vorgeschlagen, weil Sie ziemlich starke Garantien haben, dass die resultierenden Hash-Funktionen sehr unterschiedlich sein werden, und es einfach zu implementieren ist, verwenden Sie einfach die Standardbibliotheken.
Wenn Sie andererseits zwei Hash-Funktionen der Form f1(x) = ax + b (mod p) und f2(x) = cx + d (mod p) haben, können Sie eine andere (ohne x zu kennen) mit einer einfachen linearen Formel f2(x) = c / a * (f1(x) - b) + d (mod p) berechnen, was suggeriert dass sie nicht sehr unabhängig sind. Sie könnten also hier auf unerwartete Probleme stoßen.
Tags und Links scala hash-function cryptographic-hash-function