Hash-Tabellen

Was sind Hash-Tabellen?

Hash-Tabellen sind Datenstrukturen, die verwendet werden, um die Daten im Schlüssel/Wert-Paar-Format zu speichern. Es verwendet eine Hash-Funktion, um einen Index zu berechnen, der in einem Array verwendet wird, um das Element an diesem Index zu speichern.

Was ist aber ein Schlüssel/Wert-Paar?

Okay, ich werde hier in den Grundlagen graben. Nehmen wir ein Beispiel für eine Datenbanktabelle. Um einen bestimmten Wert aus der Datenbanktabelle abzurufen, müssen Sie manchmal einen Primärschlüssel oder einen eindeutigen Wert aus der Zeile der Datenbanktabelle kennen. Dann fragen Sie die Datenbanktabelle basierend auf diesem eindeutigen Wert oder Primärschlüssel ab, um die gesamte Zeile oder den bestimmten Wert zu erhalten, nach dem Sie suchen.

Immer noch kompliziert?

Nehmen wir ein Klassenzimmer-Beispiel. Sie sind in der 2. Klasse und wenn eine Lehrerin namentlich ist, ruft sie nicht unbedingt Ihren Namen, sie ruft die Ihnen zugewiesene Nummer an. Also Beispiel

1 – John Doe

2 – Jill Doe

3 – Mark Ranson

So wird die dem Schüler zugewiesene Rollennummer zu einem Schlüssel zur Identifizierung dieses Schülers.

Ähnlich verwenden wir in Programmiersprachen (in diesem Fall Java) eine Datenstruktur namens Hash Tables.

Die Hash-Funktion nimmt eine Eingabe und hasht diese Eingabe, um einen Index zu generieren, den wir als Schlüssel zum Speichern des Werts in einem Array verwenden. Warum so komplex? Warum gehen wir nicht der Reihe nach vor?

Gründe gibt es viele, erstes Hashing gibt Sicherheit. Wenn jemand die sequentielle Reihenfolge ausnutzt, ist es einfach, das nächste Element zu finden. Aber Hashing erlaubt es uns, die Daten zufällig zu speichern. Aber das Wichtigste ist, dass die durchschnittliche Zeit, die benötigt wird, um nach einem Element in einer Hash-Tabelle zu suchen, O(1). beträgt

Von den Grundlagen her können wir sagen, dass Hash-Tabellen zwei Komponenten haben – eine ein Array zum Speichern des Werts und eine Funktion zum Berechnen des Index des Arrays.

Was ist also eine Hash-Funktion und wie schreiben wir diese Hash-Funktion?

Eine Hash-Funktion ist eine Funktion, die Daten beliebiger Größe nimmt und diese Daten in Daten fester Größe umwandelt. Kurz gesagt, eine Hash-Funktion nimmt eine Eingabe x und wandelt diese in Ausgabe y um. Das sieht jetzt einfach aus, aber es stellt sich die Frage, was passiert, wenn es mehrere Eingaben gibt, die in y umgewandelt werden können. Dann haben wir ein Problem. Dies wird als Kollision bezeichnet .

Wichtige Eigenschaften dieser Hash-Funktion

1. Es sollte Kollisionen vermeiden.
2. Es sollte die Schlüssel einfach berechnen.
3. Es sollte die Schlüssel gleichmäßig verteilen.

Wie vermeide ich Kollisionen?

Es gibt ein paar Techniken.

Eine Technik ist die offene Adressierung . Speichern Sie bei Open Addressing alle Elemente in der Hash-Tabelle selbst. Die Größe der Hash-Tabelle muss zu jedem Zeitpunkt größer oder gleich der Anzahl der Schlüssel sein. Dies ist im Szenario von Tischen mit fester Größe nützlich. Wenn Sie beim Einfügen den belegten Slot in der Hash-Tabelle gefunden haben, gehen Sie zum nächsten Slot. Es wird fortgesetzt, bis es einen unbesetzten Steckplatz findet. Da dies ein linearer Prozess ist, ist offenes Adressieren auch lineares Sondieren . Der Nachteil der offenen Adressierung ist das Einfügen und der Suchvorgang wird linear.

Die zweite Technik ist Separate Chaining . Lassen Sie dabei jede Zelle einer Hash-Tabelle auf eine verknüpfte Liste von Datensätzen verweisen. Wenn also eine Hash-Funktion einen doppelten Schlüssel zurückgibt, wird der Wert in eine verknüpfte Liste eingefügt, auf die ein früherer Wert verweist, der an diesem Schlüssel gespeichert ist. Auf den nächsten Wert wird durch ein früher verknüpftes Listenelement verwiesen. Nehmen wir zur Vereinfachung an, wir haben eine has-Funktion key % 3 und so wird für 9 0 zurückgegeben. Für 10 wird 1 zurückgegeben. Für 16 wird wieder 1 zurückgegeben. Wenn wir nun einen Wert (für 10) speichern, speichern wir bei Index 1 und der nächste Wert (für 16) befindet sich in einer verknüpften Liste, auf die der bei 1 gespeicherte Wert zeigt.

Wann verwenden wir Hash-Tabellen?

1. Hash-Tabellen bieten schnelles Einfügen
2. Hash-Tabellen ermöglichen schnelles Löschen
3. Hash-Tabellen können bei der Suche nach einem Element helfen

Referenzen

1. Hashtabellen als Datenstrukturen
2. Hash-Tabellen