Hashing bezieht sich auf den Prozess der Generierung einer Ausgabe fester Größe aus einer Eingabe variabler Größe unter Verwendung mathematischer Formeln, die als Hash-Funktionen bekannt sind. Diese Technik bestimmt einen Index oder Speicherort für die Speicherung eines Elements in einer Datenstruktur.

Java-Rückgabebefehl

Bedarf an Hash-Datenstruktur

Die Datenmenge im Internet wächst täglich exponentiell, was es schwierig macht, sie alle effektiv zu speichern. In der täglichen Programmierung ist diese Datenmenge vielleicht nicht so groß, dennoch müssen sie einfach und effizient gespeichert, abgerufen und verarbeitet werden. Eine sehr häufige Datenstruktur, die für einen solchen Zweck verwendet wird, ist die Array-Datenstruktur.

Nun stellt sich die Frage: Wenn Array bereits vorhanden war, wofür war dann eine neue Datenstruktur erforderlich? Die Antwort darauf liegt im Wort Effizienz. Obwohl das Speichern im Array dauert O(1) Zeit, die Suche darin dauert mindestens O(log n) Zeit. Diese Zeit scheint kurz zu sein, aber bei einem großen Datensatz kann sie viele Probleme verursachen, was wiederum die Array-Datenstruktur ineffizient macht.

Onclick-Javascript

Nun suchen wir nach einer Datenstruktur, die die Daten speichern und in konstanter Zeit, d. h. in, darin suchen kann O(1) Zeit. So kam die Hashing-Datenstruktur ins Spiel. Mit der Einführung der Hash-Datenstruktur ist es nun möglich, Daten einfach in konstanter Zeit zu speichern und auch in konstanter Zeit abzurufen.

Komponenten des Hashings

Es gibt im Wesentlichen drei Komponenten des Hashings:

1. Schlüssel: A Schlüssel kann eine beliebige Zeichenfolge oder Ganzzahl sein, die als Eingabe in die Hash-Funktion eingespeist wird. Die Technik bestimmt einen Index oder Speicherort für die Speicherung eines Elements in einer Datenstruktur.
2. Hash-Funktion: Der Hash-Funktion empfängt den Eingabeschlüssel und gibt den Index eines Elements in einem Array zurück, das als Hash-Tabelle bezeichnet wird. Der Index ist als bekannt Hash-Index .
3. Hash-tabelle: Eine Hash-Tabelle ist eine Datenstruktur, die Schlüssel mithilfe einer speziellen Funktion namens Hash-Funktion Werten zuordnet. Hash speichert die Daten assoziativ in einem Array, wobei jeder Datenwert seinen eigenen eindeutigen Index hat.

Komponenten des Hashings

Was ist Kollision?

Der Hashing-Prozess generiert eine kleine Zahl für einen großen Schlüssel, sodass die Möglichkeit besteht, dass zwei Schlüssel denselben Wert ergeben. Die Situation, in der der neu eingefügte Schlüssel einem bereits belegten Schlüssel zugeordnet ist und mit einer Kollisionsbehandlungstechnologie behandelt werden muss.

So laden Sie YouTube-Videos VLC herunter

Kollision beim Hashing

Vorteile von Hashing in Datenstrukturen

• Schlüsselwertunterstützung: Hashing ist ideal für die Implementierung von Schlüsselwert-Datenstrukturen.
• Schneller Datenabruf: Hashing ermöglicht den schnellen Zugriff auf Elemente mit zeitlich konstanter Komplexität.
• Effizienz: Einfüge-, Lösch- und Suchvorgänge sind äußerst effizient.
• Reduzierung der Speichernutzung: Hashing erfordert weniger Speicher, da es einen festen Platz zum Speichern von Elementen zuweist.
• Skalierbarkeit: Hashing funktioniert gut bei großen Datensätzen und sorgt für eine konstante Zugriffszeit.
• Sicherheit und Verschlüsselung: Hashing ist für die sichere Datenspeicherung und Integritätsprüfung unerlässlich.

Weitere Informationen zum Hashing finden Sie im Einführung in das Hashing – Tutorials zu Datenstruktur und Algorithmen