Was ist eine Hashtabelle?
Eine Hashtabelle ist eine Datenstruktur, die zu einem Schlüssel den passenden Wert in wenigen Schritten findet. Sie steckt hinter Wörterbüchern, Zwischenspeichern und Registern und macht die Suche fast unabhängig von der Zahl der Einträge.
Ein Amt sucht zu einem Autokennzeichen wie HH den Ort. Statt 400 Kennzeichen durchzugehen, rechnet es aus dem Kennzeichen eine Fachnummer aus und sieht dort nach.
Am Ende dieser Lektion
Notiz
Ich kann erklären, wie eine Hashtabelle einen Schlüssel schnell findet.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Schlüssel | die Angabe, nach der gesucht wird | HH |
| Hashfunktion | eine Rechnung, die aus einem Schlüssel eine Fachnummer macht | |
| Fach | ein Platz der Tabelle für Einträge (englisch Bucket) | |
| Kollision | zwei Schlüssel ergeben dieselbe Fachnummer | |
| Verkettung | Einträge im selben Fach stehen in einer Liste | |
| Füllgrad | die Zahl der Einträge geteilt durch die Zahl der Fächer |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die Hashfunktion macht aus dem Schlüssel eine Fachnummer
Die Tabelle hat eine feste Zahl von Fächern, zum Beispiel fünf. Eine Hashfunktion rechnet den Schlüssel in eine Nummer von 0 bis 4 um. Bei Text addieren Sie die Zeichencodes und teilen die Summe durch die Zahl der Fächer. Der Rest ist die Fachnummer. Derselbe Schlüssel ergibt immer dieselbe Nummer.
Beispiel: Kennzeichen in fünf Fächern
| Schlüssel | Zeichencodes | Summe | Rest bei fünf Fächern |
|---|---|---|---|
| M | 77 | 77 | 2 |
| B | 66 | 66 | 1 |
| K | 75 | 75 | 0 |
| HH | 72 und 72 | 144 | 4 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Fachnummern von Kennzeichen berechnen
# Die Fachnummer eines Autokennzeichens: Summe der Zeichencodes, Rest.
def fach_nummer(schluessel, groesse):
summe = 0
for zeichen in schluessel:
summe = summe + ord(zeichen)
return summe % groesse
for kennzeichen in ["M", "B", "K", "HH", "S"]:
print(kennzeichen, "kommt in Fach", fach_nummer(kennzeichen, 5))
# Aendern Sie die Groesse auf 7 und fuehren Sie erneut aus.
Zeichencodes und Rest im Terminal
Die Funktion ord gibt den Code eines Zeichens zurück. Der erste Befehl zeigt die Codes von M, B und K. Der zweite rechnet den Rest für HH (72 plus 72) und für M bei fünf Fächern. Der Operator % liefert den Rest einer Division.
Die Codes von drei Buchstaben
python3 -c "print(ord('M'), ord('B'), ord('K'))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Den Rest für HH und M berechnen
python3 -c "print((72 + 72) % 5, 77 % 5)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Zwei Schlüssel können im selben Fach landen
Es gibt mehr mögliche Schlüssel als Fächer. Darum kommt es zu einer Kollision: Zwei Schlüssel ergeben dieselbe Nummer. Bei der Verkettung steht in jedem Fach eine kleine Liste. Beim Suchen springen Sie in das Fach und prüfen die wenigen Einträge dort. Eine Kollision ist normal und kein Fehler.
Beispiel: sieben Kennzeichen in fünf Fächern
| Fach | Einträge in dieser Reihenfolge |
|---|---|
| 0 | K (75) und F (70) |
| 1 | B (66) und DD (136) |
| 2 | M (77) |
| 3 | S (83) |
| 4 | HH (144) |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Wenige Einträge pro Fach halten die Suche schnell
Entscheidend ist der Füllgrad: die Zahl der Einträge geteilt durch die Zahl der Fächer. Wird die Tabelle zu voll, legt man mehr Fächer an und verteilt alle Einträge neu. Eine gute Hashfunktion streut die Schlüssel gleichmäßig. Dann prüft die Suche im Durchschnitt nur wenige Einträge.
Beispiel: der Füllgrad
| Einträge | Fächer | Im Schnitt pro Fach |
|---|---|---|
| 20 | 10 | 2 |
| 20 | 40 | 0,5 |
| 100 | 10 | 10 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein häufiger Fehler
Warnung
Viele denken, eine Hashtabelle halte die Einträge sortiert. Die Fächer haben zwar Nummern, aber die Schlüssel liegen in zufällig wirkender Reihenfolge. Brauchen Sie die Schlüssel sortiert, ist ein Suchbaum besser geeignet. Für das schnelle Finden eines einzelnen Schlüssels ist die Hashtabelle ideal.