Hashing in der Datenstruktur: Funktion, Techniken [mit Beispielen]

Einführung

Hashing ist eine wichtige Datenstruktur, die entwickelt wurde, um das Problem des effizienten Findens und Speicherns von Daten in einem Array zu lösen. Wenn Sie zum Beispiel eine Liste mit 20000 Nummern haben und eine Nummer angegeben haben, die in dieser Liste gesucht werden soll, scannen Sie jede Nummer in der Liste, bis Sie eine Übereinstimmung finden.

Es erfordert einen erheblichen Teil Ihrer Zeit, die gesamte Liste zu durchsuchen und diese bestimmte Nummer zu finden. Dieser manuelle Scanvorgang ist nicht nur zeitaufwändig, sondern auch ineffizient. Mit Hashing in der Datenstruktur können Sie die Suche eingrenzen und die Nummer innerhalb von Sekunden finden.

Dieser Blog vermittelt Ihnen anhand von Beispielen ein tieferes Verständnis der Hash-Methode, Hash-Tabellen und des linearen Sondierens.

Was ist Hashing in der Datenstruktur?

Hashing in der Datenstruktur ist eine Technik, bei der ein großer Datenblock mithilfe einer Hash-Funktion in kleine Tabellen abgebildet wird. Sie wird auch als Message-Digest-Funktion bezeichnet. Es ist eine Technik, die einen bestimmten Artikel aus einer Sammlung ähnlicher Artikel eindeutig identifiziert.

Es verwendet Hash-Tabellen, um die Daten in einem Array-Format zu speichern. Jedem Wert im Array ist eine eindeutige Indexnummer zugeordnet. Hash-Tabellen verwenden eine Technik, um diese eindeutigen Indexnummern für jeden Wert zu generieren, der in einem Array-Format gespeichert ist. Diese Technik wird als Hash-Technik bezeichnet.

Sie müssen nur den Index des gewünschten Elements finden, anstatt die Daten zu finden. Mit der Indizierung können Sie schnell die gesamte Liste durchsuchen und das gewünschte Element abrufen. Die Indizierung hilft auch beim Einfügen von Vorgängen, wenn Sie Daten an einer bestimmten Stelle einfügen müssen. Egal wie groß oder klein die Tabelle ist, Sie können Daten innerhalb von Sekunden aktualisieren und abrufen.

Hashing in einer Datenstruktur ist ein zweistufiger Prozess.

1. Die Hash-Funktion wandelt das Element in eine kleine Ganzzahl oder einen Hash-Wert um. Diese Ganzzahl wird als Index zum Speichern der Originaldaten verwendet.
2. Es speichert die Daten in einer Hash-Tabelle. Sie können einen Hash-Schlüssel verwenden, um Daten schnell zu finden.

Beispiele für Hashing in der Datenstruktur

Das Folgende sind reale Beispiele für Hashing in der Datenstruktur –

• In Schulen weist der Lehrer jedem Schüler eine eindeutige Rollennummer zu. Später verwendet der Lehrer diese Rollennummer, um Informationen über diesen Schüler abzurufen.
• Eine Bibliothek hat unendlich viele Bücher. Der Bibliothekar weist jedem Buch eine eindeutige Nummer zu. Diese eindeutige Nummer hilft bei der Identifizierung der Position der Bücher im Bücherregal.

Checkout: Sortierung in der Datenstruktur

Hash-Funktion

Die Hash-Funktion in einer Datenstruktur bildet Daten mit beliebiger Größe auf Daten mit fester Größe ab. Es gibt die folgenden Werte zurück: einen kleinen ganzzahligen Wert (auch bekannt als Hash-Wert), Hash-Codes und Hash-Summen.

hash = hashfunc(Schlüssel)

Index = Hash % array_size

Die has-Funktion muss die folgenden Anforderungen erfüllen:

• Eine gute Hash-Funktion ist einfach zu berechnen.
• Eine gute Hash-Funktion bleibt nie im Clustering stecken und verteilt die Schlüssel gleichmäßig über die Hash-Tabelle.
• Eine gute Hash-Funktion vermeidet Kollisionen, wenn zwei Elementen oder Elementen derselbe Hash-Wert zugewiesen wird.

Hash-tabelle

Beim Hashing in der Datenstruktur werden Hash-Tabellen zum Speichern der Schlüssel-Wert-Paare verwendet. Die Hash-Tabelle verwendet dann die Hash-Funktion, um einen Index zu generieren. Hashing verwendet diesen eindeutigen Index, um Einfüge-, Aktualisierungs- und Suchvorgänge auszuführen.

Wie funktioniert Hashing in der Datenstruktur?

Beim Hashing ordnet die Hashfunktion Zeichenfolgen oder Zahlen einem kleinen ganzzahligen Wert zu. Hash-Tabellen rufen das Element mithilfe einer Hash-Funktion aus der Liste ab. Das Ziel der Hashing-Technik besteht darin, die Daten gleichmäßig über ein Array zu verteilen. Hashing weist allen Elementen einen eindeutigen Schlüssel zu. Die Hash-Tabelle verwendet diesen Schlüssel, um auf die Daten in der Liste zuzugreifen.

Die Hash-Tabelle speichert die Daten in einem Schlüssel-Wert-Paar. Der Schlüssel fungiert als Eingabe für die Hash-Funktion. Die Hashing-Funktion generiert dann eine eindeutige Indexnummer für jeden gespeicherten Wert. Die Indexnummer behält den Wert, der diesem Schlüssel entspricht. Die Hash-Funktion gibt als Ausgabe einen kleinen ganzzahligen Wert zurück. Die Ausgabe der Hash-Funktion wird als Hash-Wert bezeichnet.

Lassen Sie uns das Hashing in einer Datenstruktur anhand eines Beispiels verstehen. Stellen Sie sich vor, Sie müssen einige Elemente (in einem Schlüssel-Wert-Paar angeordnet) in einer Hash-Tabelle mit 30 Zellen speichern.

Die Werte sind: (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)

Die Hash-Tabelle sieht wie folgt aus:

Lesen Sie auch: Arten von Datenstrukturen in Python

Kollisionsauflösungstechniken

Das Hashing in der Datenstruktur gerät in eine Kollision, wenn zwei Schlüsseln dieselbe Indexnummer in der Hash-Tabelle zugewiesen wird. Die Kollision verursacht ein Problem, da jeder Index in einer Hash-Tabelle nur einen Wert speichern soll. Beim Hashing in der Datenstruktur werden mehrere Kollisionsauflösungstechniken verwendet, um die Leistung einer Hash-Tabelle zu verwalten.

Lineare Sondierung

Das Hashen in der Datenstruktur führt zu einem Array-Index, der bereits zum Speichern eines Werts belegt ist. In einem solchen Fall führt Hashing eine Suchoperation durch und sucht linear nach der nächsten leeren Zelle.

Beispiel für lineare Sondierung

Stellen Sie sich vor, Sie wurden gebeten, einige Elemente in einer Hash-Tabelle der Größe 30 zu speichern. Die Elemente sind bereits in einem Schlüssel-Wert-Paar-Format sortiert. Die angegebenen Werte sind: (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .

Der Hash(n) ist der Index, der mit einer Hash-Funktion berechnet wird, und T ist die Tabellengröße. Wenn Slot-Index = (Hash(n) % T) voll ist, dann suchen wir nach dem nächsten Slot-Index, indem wir 1 ((Hash(n) + 1) % T) hinzufügen. Wenn (hash(n) + 1) % T ebenfalls voll ist, versuchen wir (hash(n) + 2) % T. Wenn (hash(n) + 2) % T ebenfalls voll ist, versuchen wir (hash( n) + 3) %T.

Die Hash-Tabelle sieht wie folgt aus:

Doppeltes Hashing

Die Double-Hashing-Technik verwendet zwei Hash-Funktionen. Die zweite Hash-Funktion kommt zum Einsatz, wenn die erste Funktion eine Kollision verursacht. Es stellt einen Offset-Index bereit, um den Wert zu speichern.

Die Formel für die Double-Hashing-Technik lautet wie folgt:

(ersterHash(Schlüssel) + i * zweiterHash(Schlüssel)) % Tabellengröße

Wobei i der Offset-Wert ist. Dieser Versatzwert wird inkrementiert, bis er einen leeren Steckplatz findet.

Sie haben beispielsweise zwei Hash-Funktionen: h1 und h2. Sie müssen die folgenden Schritte ausführen, um einen leeren Steckplatz zu finden:

1. Überprüfen Sie, ob hash1(key) leer ist. Wenn ja, dann speichern Sie den Wert in diesem Steckplatz.
2. Wenn hash1(key) nicht leer ist, suchen Sie mit hash2(key) einen anderen Slot.
3. Überprüfen Sie, ob hash1(key) + hash2(key) leer ist. Wenn ja, dann speichern Sie den Wert in diesem Steckplatz.
4. Erhöhen Sie den Zähler weiter und wiederholen Sie dies mit hash1(key)+2hash2(key), hash1(key)+3hash2(key) und so weiter, bis ein leerer Slot gefunden wird.

Beispiel für doppeltes Hashing

Stellen Sie sich vor, Sie müssen einige Elemente in einer Hash-Tabelle der Größe 20 speichern. Die angegebenen Werte sind: (16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1).

h1(n)=n%20

h2(n)=n%13

nh(n, i) = (h1 (n) + ih2(n)) mod 20

Fazit

Double-Hashing hat einen hohen Rechenaufwand, aber es sucht den nächsten freien Slot schneller als die lineare Sondierungsmethode. Die im Artikel aufgeführten Beispiele dienen nur der Erläuterung. Sie können die oben angegebenen Anweisungen gemäß Ihren Anforderungen ändern. In diesem Blog haben wir das Hashing-Konzept in der Datenstruktur kennengelernt .

Sie können das Beispiel ausprobieren, um Ihr Wissen über Datenstrukturen zu festigen. Wenn Sie mehr über die Datenstruktur erfahren möchten, sehen Sie sich den Kurs upGrad Executive PG Program in Full Stack Development an . Dieser Kurs richtet sich an Berufstätige und bietet eine strenge Ausbildung und Stellenvermittlung bei Top-Unternehmen.