Hash-Tabelle in der Datenstruktur: Python-Beispiel

Inhaltsverzeichnis:

Anonim

Was ist Hashing?

Ein Hash ist ein Wert mit fester Länge und wird mithilfe einer mathematischen Formel generiert. Hash-Werte werden bei der Datenkomprimierung, Kryptologie usw. verwendet. Bei der Datenindizierung werden Hash-Werte verwendet, da sie unabhängig von den Werten, mit denen sie generiert wurden, eine feste Längengröße haben. Hash-Werte belegen im Vergleich zu anderen Werten unterschiedlicher Länge nur minimalen Speicherplatz.

Eine Hash-Funktion verwendet einen mathematischen Algorithmus, um den Schlüssel in einen Hash umzuwandeln. Eine Kollision tritt auf, wenn eine Hash-Funktion denselben Hash-Wert für mehr als einen Schlüssel erzeugt.

In diesem Algorithmus-Tutorial lernen Sie:

  • Was ist Hashing?
  • Was ist eine Hash-Tabelle?
  • Hash-Funktionen
  • Eigenschaften einer guten Hash-Funktion
  • Kollision
  • Hash-Tabellenoperationen
  • Hash Table Python Beispiel
  • Erläuterung des Hash-Tabellencodes
  • Beispiel für ein Python-Wörterbuch
  • Komplexitätsanalyse
  • Reale Anwendungen
  • Vorteile von Hash-Tabellen
  • Nachteile von Hash-Tabellen

Was ist eine Hash-Tabelle?

Eine HASH-TABELLE ist eine Datenstruktur, in der Werte mithilfe eines Paares von Schlüsseln und Werten gespeichert werden. Jedem Wert wird ein eindeutiger Schlüssel zugewiesen, der mithilfe einer Hash-Funktion generiert wird.

Der Name des Schlüssels wird verwendet, um auf den zugehörigen Wert zuzugreifen. Dies macht die Suche nach Werten in einer Hash-Tabelle sehr schnell, unabhängig von der Anzahl der Elemente in der Hash-Tabelle.

Hash-Funktionen

Zum Beispiel, wenn wir Mitarbeiterdatensätze speichern möchten und jeder Mitarbeiter anhand einer Mitarbeiternummer eindeutig identifiziert wird.

Wir können die Mitarbeiternummer als Schlüssel verwenden und die Mitarbeiterdaten als Wert zuweisen.

Der obige Ansatz erfordert zusätzlichen freien Speicherplatz in der Größenordnung von (m * n 2 ), wobei die Variable m die Größe des Arrays und die Variable n die Anzahl der Stellen für die Mitarbeiternummer ist. Dieser Ansatz führt zu einem Speicherplatzproblem.

Eine Hash-Funktion löst das oben genannte Problem, indem sie die Mitarbeiternummer abruft und daraus einen Hash-Integer-Wert, feste Ziffern und die Optimierung des Speicherplatzes generiert. Der Zweck einer Hash-Funktion besteht darin, einen Schlüssel zu erstellen, der verwendet wird, um auf den Wert zu verweisen, den wir speichern möchten. Die Funktion akzeptiert den zu speichernden Wert und berechnet dann mithilfe eines Algorithmus den Wert des Schlüssels.

Das Folgende ist ein Beispiel für eine einfache Hash-Funktion

h(k) = k1 % m

HIER,

  • h (k) ist die Hash-Funktion, die einen Parameter k akzeptiert. Der Parameter k ist der Wert, für den wir den Schlüssel berechnen möchten.
  • k 1 % m ist der Algorithmus für unsere Hash-Funktion, wobei k1 der Wert ist, den wir speichern möchten, und m die Größe der Liste ist. Wir verwenden den Moduloperator, um den Schlüssel zu berechnen.

Beispiel

Nehmen wir an, wir haben eine Liste mit einer festen Größe von 3 und den folgenden Werten

[1,2,3]

Wir können die obige Formel verwenden, um die Positionen zu berechnen, die jeder Wert einnehmen sollte.

Das folgende Bild zeigt die verfügbaren Indizes in unserer Hash-Tabelle.

Schritt 1)

Berechnen Sie so die Position, die der erste Wert einnehmen wird

h (1) = 1% 3

= 1

Der Wert 1 belegt den Platz auf Index 1

Schritt 2)

Berechnen Sie die Position, die der zweite Wert einnehmen wird

h (2) = 2% 3

= 2

Der Wert 2 belegt den Platz auf Index 2

Schritt 3)

Berechnen Sie die Position, die der dritte Wert einnehmen wird.

h (3) = 3% 3

= 0

Der Wert 3 belegt den Platz im Index 0

Endergebnis

Unsere ausgefüllte Hash-Tabelle sieht nun wie folgt aus.

Eigenschaften einer guten Hash-Funktion

Eine gute Hash-Funktion sollte die folgenden Eigenschaften haben.

  • Die Formel zum Generieren des Hash sollte den Wert der Daten verwenden, der im Algorithmus gespeichert werden soll.
  • Die Hash-Funktion sollte auch für Eingabedaten mit derselben Menge eindeutige Hash-Werte generieren.
  • Die Funktion sollte die Anzahl der Kollisionen minimieren. Kollisionen treten auf, wenn derselbe Wert für mehr als einen Wert generiert wird.
  • Die Werte müssen konsistent über die gesamten möglichen Hashes verteilt sein.

Kollision

Eine Kollision tritt auf, wenn der Algorithmus denselben Hash für mehr als einen Wert generiert.

Schauen wir uns ein Beispiel an.

Angenommen, wir haben die folgende Werteliste

[3,2,9,11,7]

Nehmen wir an, dass die Größe der Hash-Tabelle 7 beträgt, und verwenden wir die Formel (k 1 % m), wobei m die Größe der Hash-Tabelle ist.

Die folgende Tabelle zeigt die Hash-Werte, die generiert werden.

Schlüssel Hash-Algorithmus (k 1 % m) Hashwert
3 3% 7 3
2 3% 7 2
9 3% 7 2
11 3% 7 4
7 3% 7 0

Wie wir aus den obigen Ergebnissen sehen können, haben die Werte 2 und 9 den gleichen Hashwert, und wir können nicht mehr als einen Wert an jeder Position speichern.

Das gegebene Problem kann entweder durch Verketten oder durch Prüfen gelöst werden. In den folgenden Abschnitten wird das Verketten und Prüfen ausführlich erläutert.

Verkettung

Die Verkettung ist eine Technik, mit der das Kollisionsproblem mithilfe von verknüpften Listen mit jeweils eindeutigen Indizes gelöst wird.

Das folgende Bild zeigt, wie eine verkettete Liste aussieht

Sowohl 2 als auch 9 belegen denselben Index, werden jedoch als verknüpfte Listen gespeichert. Jede Liste hat eine eindeutige Kennung.

Vorteile von verketteten Listen

Folgendes sind die Vorteile von verketteten Listen:

  • Verkettete Listen weisen beim Einfügen von Daten eine bessere Leistung auf, da die Reihenfolge des Einfügens O (1) ist.
  • Es ist nicht erforderlich, die Größe einer Hash-Tabelle zu ändern, die eine verkettete Liste verwendet.
  • Es kann problemlos eine große Anzahl von Werten aufnehmen, solange freier Speicherplatz verfügbar ist.

Sondierung

Die andere Technik, die zum Auflösen von Kollisionen verwendet wird, ist das Prüfen. Wenn bei Verwendung der Prüfmethode eine Kollision auftritt, können wir einfach weitermachen und einen leeren Steckplatz finden, um unseren Wert zu speichern.

Das Folgende sind die Methoden zum Prüfen:

Methode Beschreibung
Lineare Abtastung Wie der Name schon sagt, sucht diese Methode linear nach leeren Slots, beginnend an der Position, an der die Kollision aufgetreten ist, und vorwärts. Wenn das Ende der Liste erreicht ist und kein leerer Steckplatz gefunden wird. Die Prüfung beginnt am Anfang der Liste.
Quadratische Prüfung Diese Methode verwendet quadratische Polynomausdrücke, um den nächsten verfügbaren freien Slot zu finden.
Double Hashing Diese Technik verwendet einen sekundären Hash-Funktionsalgorithmus, um den nächsten freien verfügbaren Slot zu finden.

In unserem obigen Beispiel würde die Hash-Tabelle nach Verwendung der Prüfung wie folgt aussehen:

Hash-Tabellenoperationen

Hier sind die Operationen, die von Hash-Tabellen unterstützt werden:

  • Einfügen - Mit dieser Operation wird der Hash-Tabelle ein Element hinzugefügt
  • Suchen - Mit dieser Operation wird mit dem Schlüssel nach Elementen in der Hash-Tabelle gesucht
  • Löschen - Mit dieser Operation werden Elemente aus der Hash-Tabelle gelöscht

Datenoperation einfügen

Die Einfügeoperation wird verwendet, um Werte in der Hash-Tabelle zu speichern. Wenn ein neuer Wert in der Hash-Tabelle gespeichert wird, wird ihm eine Indexnummer zugewiesen. Die Indexnummer wird mit der Hash-Funktion berechnet. Die Hash-Funktion löst alle Kollisionen auf, die bei der Berechnung der Indexnummer auftreten.

Suche nach Datenoperation

Die Suchoperation wird verwendet, um Werte in der Hash-Tabelle anhand der Indexnummer nachzuschlagen. Die Suchoperation gibt den Wert zurück, der mit der Suchindexnummer verknüpft ist. Wenn wir beispielsweise den Wert 6 in Index 2 speichern, gibt die Suchoperation mit der Indexnummer 2 den Wert 6 zurück.

Datenoperation löschen

Der Löschvorgang wird verwendet, um einen Wert aus einer Hash-Tabelle zu entfernen. Das Löschen des Vorgangs erfolgt anhand der Indexnummer. Sobald ein Wert gelöscht wurde, wird die Indexnummer freigegeben. Es kann verwendet werden, um andere Werte mithilfe der Einfügeoperation zu speichern.

Implementierung einer Hash-Tabelle mit Python-Beispiel

Schauen wir uns ein einfaches Beispiel an, das den Hashwert eines Schlüssels berechnet

def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')

Erläuterung des Hash-Tabellencodes

HIER,

  1. Definiert eine Funktion hash_key, die die Parameter key und m akzeptiert.
  2. Verwendet eine einfache Moduloperation, um den Hashwert zu bestimmen
  3. Definiert eine Variable m, die auf den Wert 7 initialisiert wird. Dies ist die Größe unserer Hash-Tabelle
  4. Berechnet und druckt den Hashwert von 3
  5. Berechnet und druckt den Hashwert von 2
  6. Berechnet und druckt den Hashwert von 9
  7. Berechnet und druckt den Hashwert von 11
  8. Berechnet und druckt den Hashwert von 7

Das Ausführen des obigen Codes führt zu den folgenden Ergebnissen.

The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0

Beispiel für ein Python-Wörterbuch

Python wird mit einem integrierten Datentyp namens Dictionary geliefert. Ein Wörterbuch ist ein Beispiel für eine Hash-Tabelle. Es speichert Werte mithilfe eines Paares von Schlüsseln und Werten. Die Hash-Werte werden automatisch für uns generiert und Kollisionen werden im Hintergrund für uns aufgelöst.

Das folgende Beispiel zeigt, wie Sie einen Wörterbuchdatentyp in Python 3 verwenden können

employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)

HIER,

  1. Definiert einen Mitarbeiter mit einer Wörterbuchvariablen. Der Schlüsselname wird verwendet, um den Wert John Doe zu speichern, Alter speichert 36 und Position speichert den Wert Business Manager.
  2. Ruft den Wert des Schlüsselnamens ab und druckt ihn im Terminal aus
  3. Aktualisiert den Wert der Schlüsselposition auf den Wert Software Engineer
  4. Druckt die Werte des Schlüsselnamens und der Position
  5. Löscht alle Werte, die in unserer Wörterbuchvariablen Mitarbeiter gespeichert sind
  6. Druckt den Wert des Mitarbeiters

Das Ausführen des obigen Codes führt zu den folgenden Ergebnissen.

The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}

Komplexitätsanalyse

Hash-Tabellen haben im besten Fall eine durchschnittliche Zeitkomplexität von O (1). Die Zeitkomplexität im ungünstigsten Fall ist O (n). Das Worst-Case-Szenario tritt auf, wenn viele Werte denselben Hash-Schlüssel generieren und wir die Kollision durch Prüfen auflösen müssen.

Reale Anwendungen

In der realen Welt werden Hash-Tabellen zum Speichern von Daten verwendet

  • Datenbanken
  • Assoziative Arrays
  • Sets
  • Speicher-Cache

Vorteile von Hash-Tabellen

Hier sind die Vor- und Vorteile der Verwendung von Hash-Tabellen:

  • Hash-Tabellen bieten eine hohe Leistung beim Nachschlagen von Daten, Einfügen und Löschen vorhandener Werte.
  • Die zeitliche Komplexität für Hash-Tabellen ist unabhängig von der Anzahl der Elemente in der Tabelle konstant.
  • Sie arbeiten auch bei der Arbeit mit großen Datenmengen sehr gut.

Nachteile von Hash-Tabellen

Hier sind die Nachteile der Verwendung von Hash-Tabellen:

  • Sie können keinen Nullwert als Schlüssel verwenden.
  • Kollisionen können beim Generieren von Schlüsseln mit nicht vermieden werden. Hash-Funktionen. Kollisionen treten auf, wenn ein bereits verwendeter Schlüssel generiert wird.
  • Wenn die Hashing-Funktion viele Kollisionen aufweist, kann dies zu einer Leistungsminderung führen.

Zusammenfassung:

  • Hash-Tabellen werden zum Speichern von Daten mithilfe eines Paares von Schlüsseln und Werten verwendet.
  • Eine Hash-Funktion verwendet einen mathematischen Algorithmus, um den Hash-Wert zu berechnen.
  • Eine Kollision tritt auf, wenn der gleiche Hashwert für mehr als einen Wert generiert wird.
  • Die Verkettung löst Kollisionen, indem verknüpfte Listen erstellt werden.
  • Das Prüfen löst Kollisionen, indem leere Slots in der Hash-Tabelle gefunden werden.
  • Die lineare Prüfung sucht nach dem nächsten freien Steckplatz, um den Wert ab dem Steckplatz zu speichern, an dem die Kollision aufgetreten ist.
  • Bei der quadratischen Prüfung werden Polynomausdrücke verwendet, um den nächsten freien Slot zu finden, wenn eine Kollision auftritt.
  • Double Hashing verwendet einen sekundären Hash-Funktionsalgorithmus, um den nächsten freien Slot zu finden, wenn eine Kollision auftritt.
  • Hash-Tabellen weisen im Vergleich zu anderen Datenstrukturen eine bessere Leistung auf.
  • Die durchschnittliche zeitliche Komplexität von Hash-Tabellen beträgt O (1).
  • Ein Wörterbuchdatentyp in Python ist ein Beispiel für eine Hash-Tabelle.
  • Hash-Tabellen unterstützen Einfüge-, Such- und Löschvorgänge.
  • Ein Nullwert kann nicht als Indexwert verwendet werden.
  • Kollisionen können in Hash-Funktionen nicht vermieden werden. Eine gute Hash-Funktion minimiert die Anzahl der Kollisionen, die auftreten, um die Leistung zu verbessern.