What is a Hash Table?
Lektion 2 von 14 im Kurs Hash-Tabellen – Datenstrukturen-Serie #4 von Coddy.
Eine Hash-Tabelle ist eine Datenstruktur, die Schlüssel-Wert-Paare speichert, ähnlich wie ein Wörterbuch, das Einträge anhand ihres Schlüssels nachschlägt. Die Magie liegt in der Geschwindigkeit: Eine gut aufgebaute Hash-Tabelle findet, fügt ein oder entfernt einen Eintrag in O(1) durchschnittlicher Zeit, unabhängig davon, wie viele Einträge sie enthält.
Der Trick ist die Hash-Funktion. Jeder Schlüssel wird in einen Bucket-Index umgewandelt, sodass wir genau wissen, wo wir suchen müssen, ohne die gesamte Tabelle zu scannen. Wenn zwei verschiedene Schlüssel im selben Bucket landen (eine Kollision), behalten wir sie zusammen in einer Liste in diesem Bucket. Diese Strategie wird Chaining genannt.
Die fünf Hauptoperationen einer Hash-Tabelle sind:
- Put: Speichern eines Schlüssel-Wert-Paares oder Aktualisieren des Wertes, falls der Schlüssel bereits existiert.
- Get: Nachschlagen des Wertes für einen gegebenen Schlüssel.
- ContainsKey: Prüfen, ob ein Schlüssel in der Tabelle gespeichert ist.
- Remove: Löschen eines Schlüssel-Wert-Paares.
- Size: Rückgabe der Anzahl der aktuell gespeicherten Paare.
Lassen Sie uns eine HashMap-Klasse erstellen!
Probier es selbst
Diese Lektion enthält keine Programmieraufgabe.