Antwort mit KI erzeugt
a) An welchen Positionen in der ersten Spalte der Tabelle müsste nachgeschaut werden, wenn nach dem Wert 23 gesucht wird?
Um zu ermitteln, an welchen Positionen nach dem Wert 23 gesucht werden muss, wendet man die gegebene Hash-Funktion \( h(i) = i \mod 8 \) auf den Wert 23 an.
\( h(23) = 23 \mod 8 = 7 \)
Die Suche startet daher bei Position 7. Da die Kollisionsstrategie die einfache lineare Sondierung ist, würde, falls der Wert 23 nicht an Position 7 gefunden wird und die Position belegt ist, der nächste Schritt sein, die Position 0, 1, 2, und so weiter zu prüfen, bis ein freier Platz oder der gesuchte Wert gefunden wird. In diesem speziellen Fall, wenn an der ersten berechneten Position (7) der Wert 23 nicht gefunden wird, schaut man der Reihe nach in die Positionen 0, 1, 2, usw., bis der Eintrag gefunden wird oder ein freier Platz erreicht wird, der anzeigt, dass der Wert 23 nicht in der Tabelle vorhanden ist.
b) Nennen Sie eine Alternative zur linearen Sondierung. Wie werden bei dieser Alternative neue Suchpositionen ermittelt?
Eine Alternative zur linearen Sondierung ist die quadratische Sondierung. Bei der quadratischen Sondierung wird eine quadratische Folge zur Bestimmung der nächsten Suchposition verwendet. Die Hash-Funktion ändert sich zu
\( h(i, j) = (h(i) + j^2) \mod T \)
wobei \( h(i) \) die ursprüngliche Hash-Funktion ist, \( j \) der Sondierungsindex (beginnend bei 0 und erhöht um 1 nach jedem Konflikt) und \( T \) die Größe der Hashtabelle. Der wesentliche Unterschied zur linearen Sondierung ist also, dass die Schritte, die nach jedem Konflikt gemacht werden, quadratisch anwachsen (\(1, 4, 9, 16, \ldots\)) statt linear (\(1, 2, 3, 4, \ldots\)).
c) Tragen Sie in die freien Spalten der Tabelle jeweils den Zustand ein, der sich durch Anwendung der Operationen in Zeile 1 auf den vorhergehenden Zustand ergibt.
Um die Operationen schrittweise durchzuführen, führen wir die gegebenen Aktionen nacheinander aus:
1. Einfügen 37: \( h(37) = 37 \mod 8 = 5 \). Da Position 5 mit (13) markiert ist, also gelöscht, kann 37 dort eingefügt werden.
2. Einfügen 8: \( h(8) = 8 \mod 8 = 0 \). Da Position 0 besetzt ist, wird die nächste freie Position gesucht. Es wird an Position 1 eingefügt.
3. Löschen 12: Eintrag 12 befindet sich an Position 4 und wird markiert als gelöscht.
4. Einfügen 3: \( h(3) = 3 \mod 8 = 3 \). Da Position 3 frei ist, wird 3 dort eingefügt.
5. Löschen 24: Eintrag 24 befindet sich an Position 0 und wird markiert als gelöscht.
6. Einfügen 81: \( h(81) = 81 \mod 8 = 1 \). Da Position 1 besetzt ist, wird die nächste freie Position gesucht. Da Position 2 besetzt ist, prüfen wir weiter und Position 3 ist auch besetzt, Position 4 ist gelöscht (kann überschreiben werden, aber wir wählen stattdessen leere oder gelöschte Plätze), Position 5 ebenfalls. An Position 6 findet sich eine echte freie Stelle, also wird 81 dort eingefügt.
Die aktualisierte Tabelle sieht daher wie folgt aus:
| Pos. | | Einfügen
37 | Einfügen
8 | Löschen
12 | Einfügen
3 | Löschen
24 | Einfügen
81 |
|---|
| 0 | (24) | (24) | (24) | (24) | (24) | | |
| 1 | | | 8 | 8 | 8 | 8 | 8 |
| 2 | 18 | 18 | 18 | 18 | 18 | 18 | 18 |
| 3 | | | | | 3 | 3 | 3 |
| 4 | 12 | 12 | 12 | (12) | (12) | (12) | (12) |
| 5 | (13) | 37 | 37 | 37 | 37 | 37 | 37 |
| 6 | | | | | | | 81 |
| 7 | 15 | 15 | 15 | 15 | 15 | 15 | 15 |
