Hash-Tabelle in Datenstruktur: Python Beispiel

Was ist Hashing?

Ein Hash ist ein Wert mit fester Länge, der mithilfe einer mathematischen Formel generiert wird. Hash-Werte werden bei der Datenkomprimierung, Kryptologie usw. verwendet. Bei der Datenindizierung werden Hash-Werte verwendet, weil sie unabhängig von den Werten, die zu ihrer Generierung verwendet wurden, eine feste Länge haben. Dadurch nehmen Hash-Werte im Vergleich zu anderen Werten unterschiedlicher Länge nur minimalen Platz ein.

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

Was ist eine Hash-Tabelle?

A HASH-TABELLE ist eine Datenstruktur, die Werte mithilfe eines Schlüssel-Wert-Paares speichert. Jedem Wert ist ein eindeutiger Schlüssel zugeordnet, der mithilfe einer Hash-Funktion generiert wird.

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

Hash-Funktionen

Wenn wir beispielsweise Mitarbeiterdaten 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²) wobei die Variable m die Größe des ist Array, und die Variable n ist die Anzahl der Stellen für die Mitarbeiternummer. Dieser Ansatz führt zu einem Speicherplatzproblem.

Eine Hash-Funktion löst das obige Problem, indem sie die Mitarbeiternummer abruft und daraus einen Hash-Ganzzahlwert, feste Ziffern und eine Optimierung des Speicherplatzes generiert. Der Zweck einer Hash-Funktion besteht darin, einen Schlüssel zu erstellen, der als Referenz auf den Wert verwendet wird, 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₁ % 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. Wir verwenden den Modulo-Operator, 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]

Mit der obigen Formel können wir die Positionen berechnen, die jeder Wert einnehmen sollte.

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

Schritt 1) Berechnen Sie auf diese Weise die Position, die der erste Wert einnehmen wird

h(1) = 1 % 3

= 1

Die Wertschöpfung 1 wird besetzen der Raum auf Index 1

Schritt 2) Berechnen Sie die Position, die der zweite Wert einnehmen wird

h(2) = 2 % 3

= 2

Die Wertschöpfung 2 wird besetzen der Raum auf Index 2

Schritt 3) Berechnen Sie die Position, die der dritte Wert einnehmen wird.

h(3) = 3 % 3

= 0

Die Wertschöpfung 3 wird besetzen der Raum auf 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 Hashs sollte den im Algorithmus zu speichernden Datenwert verwenden.
• Die Hash-Funktion sollte auch für gleich große Eingabedaten eindeutige Hash-Werte generieren.
• Die Funktion soll 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 alle 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₁ % m), wobei m die Größe der Hash-Tabelle ist.

Die folgende Tabelle zeigt die generierten Hashwerte.

Wesentliche	Hash-Algorithmus (k1 % 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 Verkettung oder durch Sondierung gelöst werden. In den folgenden Abschnitten werden Verkettung und Sondierung im Detail erläutert.

Verkettung

Die Verkettung ist eine Technik, die zur Lösung des Kollisionsproblems verwendet wird, indem verknüpfte Listen verwendet werden, die jeweils über eindeutige Indizes verfügen.

Das folgende Bild veranschaulicht, 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 verketteter Listen

Die Vorteile verketteter Listen sind folgende:

• Verkettete Listen weisen beim Einfügen von Daten eine bessere Leistung auf, da die Einfügereihenfolge 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 zur Lösung von Kollisionen verwendet wird, ist die Sondierung. Wenn es bei der Sondierungsmethode zu einer Kollision kommt, können wir einfach weitermachen und einen leeren Steckplatz finden, um unseren Wert zu speichern.

Die folgenden Sondierungsmethoden sind verfügbar:

Methode	Beschreibung
Lineares Antasten	Wie der Name schon sagt, sucht diese Methode linear nach leeren Slots, beginnend an der Position, an der die Kollision stattgefunden hat, und bewegt sich vorwärts. Wenn das Ende der Liste erreicht ist und kein leerer Slot gefunden wird. Die Sondierung 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 Steckplatz zu finden.

Unter Verwendung unseres obigen Beispiels würde die Hash-Tabelle nach der Verwendung von Sondierung wie folgt aussehen:

Hashtabellenoperationen

Hier sind die OperaVon Hash-Tabellen unterstützte Funktionen:

• Einfügen - Dies OperaMit der Funktion wird ein Element zur Hash-Tabelle hinzugefügt
• Suchen - Dies OperaMit der Funktion wird mithilfe des Schlüssels nach Elementen in der Hash-Tabelle gesucht
• Löschen - Dies OperaMit dieser Funktion werden Elemente aus der Hash-Tabelle gelöscht

Daten einfügen

Der Einfügevorgang 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 mithilfe der Hash-Funktion berechnet. Die Hash-Funktion löst alle Kollisionen, die bei der Berechnung der Indexnummer auftreten.

Suchen 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 bei Index 2 speichern, gibt die Suchoperation mit Indexnummer 2 den Wert 6 zurück.

Datenlöschvorgang

Mit der Löschoperation wird ein Wert aus einer Hash-Tabelle entfernt. Zum Löschen des OperaDie Einfügen-Operation erfolgt über die Indexnummer. Sobald ein Wert gelöscht wurde, wird die Indexnummer freigegeben. Sie kann über die Einfügeoperation zum Speichern anderer Werte verwendet werden.

Hash-Tabellen-Implementierung mit Python Beispiel

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

def hash_key( key, m):
    return key % m


m = 7

print(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)}')

Erklärung des Hash-Tabellencodes

HIER,

1. Definiert eine Funktion hash_key, die die Parameter key und m akzeptiert.
2. Verwendet eine einfache Modulo-Operation zur Ermittlung des Hash-Wertes
3. Definiert eine Variable m, die auf den Wert 7 initialisiert wird. Dies ist die Größe unserer Hash-Tabelle
4. Berechnet den Hashwert von 3 und gibt ihn aus
5. Berechnet den Hashwert von 2 und gibt ihn aus
6. Berechnet den Hashwert von 9 und gibt ihn aus
7. Berechnet den Hashwert von 11 und gibt ihn aus
8. Berechnet den Hashwert von 7 und gibt ihn aus

Die Ausführung des obigen Codes erzeugt die folgenden Ergebnisse.

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

Python Wörterbuchbeispiel

Python verfügt über einen integrierten Datentyp namens Dictionary. Ein Wörterbuch ist ein Beispiel für eine Hash-Tabelle. Es speichert Werte mithilfe eines Schlüssel-Wert-Paares. Die Hashwerte werden automatisch für uns generiert und eventuelle Kollisionen werden im Hintergrund für uns aufgelöst.

Das folgende Beispiel zeigt, wie Sie einen Dictionary-Datentyp verwenden können in Python 3

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 Wörterbuchvariablen. Der Schlüsselname wird verwendet, um den Wert „John Doe“ zu speichern, „age“ speichert „36“ und „position“ speichert den Wert „Business Manager“.
2. Ruft den Wert des Schlüsselnamens ab und gibt 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 Schlüsselposition
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 erzeugt die folgenden Ergebnisse.

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 schlimmsten Fall beträgt O(n). Der schlimmste Fall tritt ein, wenn viele Werte denselben Hash-Schlüssel generieren und wir die Kollision durch Sondieren auflösen müssen.

Reale Anwendungen

In der Praxis werden Hash-Tabellen zum Speichern von Daten verwendet

• Datenbanken
• Assoziative Arrays
• Sets
• Speicher-Cache

Vorteile von Hash-Tabellen

Hier sind die Vorteile/Vorteile der Verwendung von Hash-Tabellen:

• Hash-Tabellen bieten eine hohe Leistung beim Nachschlagen von Daten sowie beim 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 funktionieren 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.
• Bei der Schlüsselgenerierung mit können Kollisionen nicht vermieden werden. Hash-Funktionen. Kollisionen treten auf, wenn ein Schlüssel generiert wird, der bereits verwendet wird.
• Wenn die Hashing-Funktion viele Kollisionen aufweist, kann dies zu Leistungseinbußen führen.

Zusammenfassung

• Hash-Tabellen werden zum Speichern von Daten mithilfe eines Schlüssel-Wert-Paares verwendet.
• Eine Hash-Funktion verwendet einen mathematischen Algorithmus zur Berechnung des Hash-Werts.
• Eine Kollision tritt auf, wenn für mehr als einen Wert derselbe Hashwert generiert wird.
• Durch die Verkettung werden Kollisionen gelöst, indem verknüpfte Listen erstellt werden.
• Beim Sondieren werden Kollisionen gelöst, indem leere Slots in der Hash-Tabelle gefunden werden.
• Die lineare Abtastung sucht nach dem nächsten freien Steckplatz, um den Wert ab dem Steckplatz zu speichern, in dem die Kollision aufgetreten ist.
• Bei der quadratischen Sondierung werden Polynomausdrücke verwendet, um bei einer Kollision den nächsten freien Slot zu finden.
• Double Beim Hashing wird ein sekundärer Hash-Funktionsalgorithmus verwendet, um bei einer Kollision den nächsten freien Slot zu finden.
• Hash-Tabellen weisen im Vergleich zu anderen Datenstrukturen eine bessere Leistung auf.
• Die durchschnittliche Zeitkomplexitä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 auftretenden Kollisionen, um die Leistung zu verbessern.