Erklärung über Hashing und seine Verwendung für die Datenkompression

Question

Ich bin vor einer Anwendung, das Hashing verwendet, aber ich kann immer noch nicht herausfinden, wie es funktioniert. Hier ist mein Problem, Hashing verwendet wird einigen Index zu erzeugen und mit diesem Indizes ich den Zugriff auf verschiedene Tabellen, und nachdem ich den Wert jede Tabelle hinzufügen, dass ich die Indizes bekommen verwenden und damit ich meine Endwert. Dies geschieht, um den Speicherbedarf zu reduzieren. Die Eingabe in die Hash-Funktion ist dabei die XOR zwischen einer zufälligen konstanten Anzahl und einige Parameter aus der Anwendung.

Ist das eine typische Hashing-Anwendung ?. Die Sache, die ich nicht verstehe, ist, wie mit Hashing können wir die Speicheranforderungen zu reduzieren ?. Kann jemand klären das?.

Danke

Answer 1

Hashing allein nichts mit dem Gedächtnis zu tun hat.

Was es oft verwendet wird, ist eine Hash-Tabelle. Hashtables arbeiten durch die Berechnung der Hash von dem, was Sie aus der sind Keying, die dann als Index in eine Datenstruktur verwendet wird.

Hashing ermöglicht es Ihnen, den Schlüssel (string, etc.) in einen kompakteren Wert wie eine ganze Zahl oder einen Satz von Bits zu reduzieren.

Das könnte die Speichereinsparungen Sie sich beziehen - einen großen Schlüssel für eine einfache ganze Zahl zu reduzieren

.

Beachten Sie jedoch, dass Hashes sind nicht einzigartig! Ein guter Hashing-Algorithmus minimiert Kollisionen, aber sie sind nicht auf einen eindeutigen Wert reduzieren, soll - so nicht möglich ist (zB wenn Ihr Hash eine 32-Bit-Integer-Ausgänge, Ihre Hash nur 2 ^ 32 eindeutige Werte haben würde)

Answer 2

Ist es ein Bloom-Filter Sie sprechen werden? Dies nutzt Funktionen Hash einen Raum effizienten Weg, um die Mitgliedschaft in einer Reihe zu testen. Wenn ja, dann den Link für eine Erklärung sehen.

Answer 3

Die meist gute Hash-Implementierungen sind Speicher ineffizient, sonst gäbe es mehr Rechen beteiligt sein -. Und das würde genau den Punkt des Hashing fehlt

Hash-Implementierungen sind für die Effizienz der Verarbeitung verwendet wird, wie sie Sie mit konstanter Laufzeit für Operationen wie Einfügen, Entfernen und Wieder bereitstellen werden.

Sie können denken, über die Qualität in einer Art und Weise von Hashing, die alle Ihre Daten, egal welche Art und Größe, ist immer in einem einzigen fester Länge Form dargestellt.

Answer 4

Dies erklärt werden könnte, wenn das Hashing getan wird, ist nicht eine echte Hash-Tabelle zu erstellen, ist aber nur einen Index in einem String / Speicherblock Tabelle zu erstellen. Wenn Sie die gleiche Zeichenfolge (oder die Speichersequenz) hatten 20-mal in Ihren Daten, und Sie dann ersetzt alle 20 Instanzen dieser Zeichenfolge mit nur seinem Hash / Tabellenindex, könnten Sie die Datenkomprimierung auf diese Weise erreichen. Wenn es eine tatsächliche Kollision Kette in dieser Tabelle für jeden Hash-Wert enthalten ist, jedoch dann, was ich gerade beschrieben ist nicht, was los ist; in diesem Fall würde wahrscheinlich der Grund für den Hashing seine Ausführung zu beschleunigen (durch schnellen Zugriff auf gespeicherte Werten bereitstellt), anstatt Kompression.