Antwort mit KI erzeugt
Um die Aufgabe zu lösen, müssen wir jeden Schlüssel nacheinander in eine Hash-Tabelle mit \( m = 7 \) Einträgen einfügen. Die Hash-Funktion ist definiert als \( h(k) = k \mod 7 \). Bei Kollisionen verwenden wir Open Adressing mit quadratischer Sondierung, wobei die Sondierungsfunktion \( s(j, k) = j^2 \) für den \( j \)-ten Einfügeversuch ist.
Wir betrachten den Index des \( j \)-ten Einfügeversuchs für den Schlüssel \( k \) gemäß der Formel:
\(
\text{Index} = (h(k) - j^2 \mod 7 + 7) \mod 7
\)
Schritte der Berechnung:
1. Berechnen Sie die Initial-Position \( h(k) = k \mod 7 \).
2. Wenn diese Position bereits belegt ist, berechnen Sie die nächste Position unter Verwendung der quadratischen Sondierung \( s(j, k) = j^2 \).
Angenommene Reihenfolge der Schlüssel: 10, 22, 31, 4, 15, 28.
Berechnungsschritte:
Einfügen von Schlüssel 10:
1. Berechne Initial-Position: \( h(10) = 10 \mod 7 = 3 \).
2. Platz 3 ist frei, 10 wird an Position 3 eingefügt.
Hash-Tabelle:
[-, -, -, 10, -, -, -]
Einfügen von Schlüssel 22:
1. Berechne Initial-Position: \( h(22) = 22 \mod 7 = 1 \).
2. Platz 1 ist frei, 22 wird an Position 1 eingefügt.
Hash-Tabelle:
[-, 22, -, 10, -, -, -]
Einfügen von Schlüssel 31:
1. Berechne Initial-Position: \( h(31) = 31 \mod 7 = 3 \).
2. Platz 3 ist belegt, verwende quadratische Sondierung:
- \( j = 1 \): \((h(31) - 1^2 \mod 7 + 7) \mod 7 = (3 - 1 \mod 7 + 7) \mod 7 = (9) \mod 7 = 2\)
3. Platz 2 ist frei, 31 wird an Position 2 eingefügt.
Hash-Tabelle:
[-, 22, 31, 10, -, -, -]
Einfügen von Schlüssel 4:
1. Berechne Initial-Position: \( h(4) = 4 \mod 7 = 4 \).
2. Platz 4 ist frei, 4 wird an Position 4 eingefügt.
Hash-Tabelle:
[-, 22, 31, 10, 4, -, -]
Einfügen von Schlüssel 15:
1. Berechne Initial-Position: \( h(15) = 15 \mod 7 = 1 \).
2. Platz 1 ist belegt, verwende quadratische Sondierung:
- \( j = 1 \): \((h(15) - 1^2 \mod 7 + 7) \mod 7 = (1 - 1 \mod 7 + 7) \mod 7 = (7) \mod 7 = 0\)
3. Platz 0 ist frei, 15 wird an Position 0 eingefügt.
Hash-Tabelle:
[15, 22, 31, 10, 4, -, -]
Einfügen von Schlüssel 28:
1. Berechne Initial-Position: \( h(28) = 28 \mod 7 = 0 \).
2. Platz 0 ist belegt, verwende quadratische Sondierung:
- \( j = 1 \): \((h(28) - 1^2 \mod 7 + 7) \mod 7 = (0 - 1 \mod 7 + 7) \mod 7 = (6) \mod 7 = 6\)
3. Platz 6 ist frei, 28 wird an Position 6 eingefügt.
Hash-Tabelle:
[15, 22, 31, 10, 4, -, 28]
Die finale Hash-Tabelle sieht wie folgt aus:
[15, 22, 31, 10, 4, -, 28].
Damit haben wir alle Schlüssel erfolgreich in die Hash-Tabelle eingefügt und Kollisionen mithilfe der quadratischen Sondierung gelöst.
