Grundlegende Konzepte des Hashing von Vektoren

Question

Ich lerne Hashing-Techniken für Nachschlagevorgänge und Informationsabruf. Aber bevor ich tiefgrabe, bin ich mit bestimmten Konzepten über Hash-Funktionen im Allgemeinen verwirrt.

Angenommen, ich habe einen Eingang x, der ein Vektor von Fließkommawerten ist, xi = [x_1,x_2,...,x_L]. Die Größe des Vektors ist L. Es gibt N solche Vektoren, auch als Beispiele bezeichnet, X = [x1,x2,..,x_N]. Bei einem Abfragevektor p muss ich das nächste/nächste Beispiel finden, das mit der Abfrage übereinstimmt. Wenn Sie mehrere Lesestoffe durchgehen, ist die einfachste (aber ineffizienteste) Hashing-Funktion , wenn die Tabellengröße M=10 (sagen wir) ist.

x mod M der Rest von x ist, wenn durch M geteilt, dann wird immer zwischen x mod M0 und M -1, können wir immer eine ganze Zahl mit einem der Schlitze M kartieren. Meine Fragen:

Frage 1: Der Modul wird über die Tabellengröße durchgeführt. Wenn jedoch jede Probe die Länge L hat und es N solche Proben gibt, welche Modulo-Zahl dann darstellt? Würde h(x) = x mod vector length

oder h(x) = xmod number of examples?

In Kryptografieanwendungen wird normalerweise mod 256 verwendet, da jeder Block eine Größe von 8 Bits hat. Dies bedeutet, dass Modulus über die Länge des Vektors genommen wird? Bitte korrigiere mich wenn falsch.

Frage 2: Sollte ich die Fließkommazahlen in Ganzzahlen konvertieren, weil viele Beispiele zeigen, dass die Eingabe entweder ein ASCII-Wert oder eine ganze Zahl ist.

Frage 3: Wenn die Hash-Funktion h(x) = 2*x mod 1 ist, dann würde dies eine Gleitkommazahl im Bereich [0,1] erzeugen. Ich kann es mit H(x) = round(h(x)) in eine ganze Zahl umwandeln. Für ein Nachrichtenbeispiel x, wenn es in k Blöcke von jeder Länge gleicher Länge L aufgeteilt wird, würde ich k solche Hash-Funktionen benötigen? Irgendwelche Vorschläge für eine Hash-Funktion für dieses Beispiel. Vielen Dank.

Answer 1

Wenn Sie also eine Hash-Tabelle erstellen, ist dies nur ein Array, und was eine Hash-Funktion macht, ist ein Objekt, das basierend auf den Objekteigenschaften integer mod (length of array) zurückgibt. Also mach dir keine Sorgen über deine Fließkommazahlen! Wenn Sie einen Vorschlag zur Umsetzung wünschen, würde ich Folgendes tun.

Zuerst überlegen Sie, wie lange Ihre Hashtable sein soll (normalerweise ist die doppelte Anzahl von Objekten, die Sie [oder ein bisschen länger] einsetzen, eine gute Wette). Das ist nur ein Array von Typvektor (oder das Objekt, das Sie speichern).

Als nächstes wollen Sie Ihre Hash-Funktion machen. Beim Entwerfen von Hashfunktionen ist es eine gute Idee, große Primzahlen zu verwenden und verschiedene Teile Ihres Objekts mit ihnen zu multiplizieren und alles hinzuzufügen. Zum Beispiel ...

int total = 0 
for each floatingptNum currentVector: 
    total = total + 129 * currentFloatingptNum 

return total % lengthOfArray 

Das ist nur eine sehr einfache Hash-Funktion in suedo Code (nicht sicher, welche Sprache Sie verwenden), aber solange es Ihnen eine ganze Zahl im Bereich von Ihnen sind Array gibt Du bist fertig!

Der Grund, warum wir große Primzahlen verwenden, ist so, dass wir möglichst wenige Kollisionen (wenn zwei separate Werte auf den gleichen Ort abgebildet werden) erhalten, aber bedenken Sie, dass diese fast immer passieren müssen. Eine Lösung ist bucket or chain hashing. Dies bedeutet im Grunde, dass Sie anstelle eines Arrays von Vektoren eine Reihe von verknüpften Listen von Vektoren haben, nur um zwei verschiedene Vektoren an der gleichen Stelle in der Hash-Tabelle speichern zu können!

Eine Menge Informationen, aber ich hoffe, es hilft! Fröhliches Hashing!