0 Daumen
227 Aufrufe

Frage:

In der folgenden Tabelle sollen Integer-Werte mit Hilfe von Hashing eingefügt werden Als Hash-Funktion für einen Integer-Wert \( i \) wird die Funktion \( h(i)=i \) mod 8 benutzt. Die Kollisionsstrategie ist die einfache lineare Sondierung. Gel\vecschte Einträge werden durch Klammern als gelöscht markiert und nicht sofort entfernt.

Pos.Einfügen
37
Einfügen
8
Löschen
12
Einfügen
3
Löschen
24
Einfügen
81
024
1
218
3
412
5(13)
6
715

a) An welchen Positionen in der ersten Spalte der Tabelle müsste nachgeschaut werden, wenn nach dem Wert 23 gesucht wird?

b) Nennen Sie eine Alternative zur linearen Sondierung. Wie werden bei diesel Alternative neue Suchpositionen ermittelt?

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.

Avatar von

1 Antwort

0 Daumen

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)
188888
218181818181818
3333
4121212(12)(12)(12)(12)
5(13)373737373737
681
715151515151515
Avatar von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
1 Antwort

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community