Question

Gegeben seien eine Hash-Tabelle der Größe 7 mit der Belegung

Index:  0  |  1  |   2  |   3  |  4  |   5  |   6 

Wert :  8  | 31 |  44 |  55 |   3 |   47|   64

und die Hash-Funktion h(k) = Quersumme(k) mod 7. Wir verwenden offenes Hashing und als Kollisionsstrategie wird quadratisches Sondieren angewandt.

Beispiel: h(4711) = (4 + 7 + 1 + 1) mod 7 = 13 mod 7 = 6

Achten Sie bei allen Teilaufgaben auf einen nachvollziehbaren Lösungsweg. 

1. Geben Sie eine Reihenfolge an, in welcher die Schlüssel in die anfangs leere Hash- Tabelle eingefügt worden sein können. 

2. Wie viele Tabellenplätze werden inspiziert, wenn nach jedem der Schlüssel einmal gesucht wird? 

3. Geben Sie eine alternative Einfügereihenfolge der Werte an, die – unter der Voraussetzung, dass nach jedem Schlüssel genau einmal gesucht wird – zu einer geringeren Anzahl zu inspizierender Tabellenplätze fuhrt.

Hat jm. eine Idee wie ich anfangen soll. Habe alle Zahlen aus der Tabelle wie im Beispiel als Quersumme berechnet und weiter komme ich iwie. nicht :(( 

Answer 1

Du musst Deine gegebenen Regeln überprüfen und anwenden.

Z.B.

Der Wert 8 steht an Pos. 0. Weil 8 mod 7 = 1, sollte er eigentlich an Pos.1 stehen und steht nur deshalb an Pos. 0, weil Pos. 1 bereits belegt war. Wegen des quadr. Sondierens ist er aber nur 1mal verschoben worden (wg. der Differenz Pos. 0 zu Pos. 1).

Prüfe alles durch, überlege die Reihenfolge und die Strategie.

Grüße,

M.B.

Comments

Ich habe jetzt rausgefunden, dass die Zahlen bei 1. 55, 3, 44,... sind.Ich komme aber jetzt trotzdem nicht weiter, wenn ich z.B. die 8 nehme, dann berechne ich die Zahl erst als Quersumme (bei der 8 bleibt es ja 8), also:
h(8)=8%7=1%7=1 (wie im Beispiel)
da Platz 1 schon belegt ist, rechne ich:
(8+1^2)/7 = 1(2) Also sollte die 8 auf Platz 2 kommen in der Tabelle ist es wieder nicht der Fall Dann prüfe ich die Zahl so weiter mit 2^2, 3^2 usw. , aber es passt trotzdem nichts, könntest du mir vlt. weiter helfen?

---

die Zahl 1 hast Du gar nicht.

Der Platz wird nicht \( /7 \) sondern \( \%7 \) berechnet.

Quadratisches Sondieren geht mit \( \pm \) (oder auch \(\mp\)), nicht nur mit \(+\).

Grüße,

M.B.

---

Mein Skript ist nicht so gut und ich habe ein Video gefunden wo für die Kollision folgende Formel benutzt wird: (x+1^2)%7 bei dem ersten Fehler, (x+2^2)%7 für den zweiten und so weiter... mit dieser Formel habe ich jetzt die Reihenfolge von allen Zahlen gefunden außer 8 und 64. Ist die Formel falsch? Wenn ja könntest du mir vlt. eine von den Zahlen vorrechnen? Ich weiß ehrlich gesagt nicht wie ich die Aufgabe sonst schaffen soll.

---

das war meine Rechnung:

h(55)= (5+5)%7 = 3 (Passt)

h(3)= 3%7 = 3 (Passt nicht)

Also: (3+1^2)%7= 4 (Passt)

h(47)=(4+7)%7=4 (Passt nicht)

Also:(11+1^2)%7=5 (Passt)

usw.

---

Du berechnest einen Platz nach der normalen Hash-Regel. Ist dieser belegt, wird ein neuer Platz nach der Sondierungsregel gesucht. Die Sondierung gib Dir nicht den neuen Platz direkt, sondern nur die Verschiebung zum alten an.

Bei linearer Sondierung ist der Offset (vom Prinzip) 1, 2, 3, 4, ...; bei quadratischer Sondierung ist der Offset 1, 4, 9, 16 ,...

Zu beachten ist, dass Du in beide Richtungen gehst, also gilt

linear: +1, -1, +2, -2, +3, -3, ... oder auch -1, +1, -2, +2, -3, +3, ...

quadratisch: +1, -1, +4, -4, +9, -9, ... oder auch -1, +1, -4, +4, -9, +9, ...

Bei Dir:

8 --> 8 % 7 = 1 (ist aber auf 0)

31 --> (3+1) % 7 = 4 (ist aber auf 1)

44 --> (4+4) % 7 = 1 (ist aber auf 2)

55 --> (5+5) % 7 = 3 (ist auf 3)

3 --> 3 (ist aber auf 4)

47 --> (4+7) % 7 = 4 (ist aber auf 5)

64 --> (6+4) % 7 = 3 (ist aber auf 6)

Alle Zahlen kommen mehrfach vor, also hast Du (theoretisch) überall Konflikte. Die einzige richtige Zahl ist 55, sie muss also als erstes einsortiert worden sein.

Zumindest jeweils eine der Zahlen 8 oder 44 bzw. 31 oder 47 hätte auf die richtige Position kommen sollen, außer das Feld ist belegt, und das kann dann nur wegen einer Sondierung aus dem Feld 3 der Fall sein.

Grüße,

M.B.

---

Was ist dieses mod von einer zahl?

---

Hallo L88isReal,

mod bedeutet, dass Du bei einer Teilung nur den Rest betrachtest, z.B. \( 7:5 = 1 {\rm~Rest~} 2 \)., also \( 7 {\rm~mod~} 5 = 2 \), oft abgekürzt mit \( 7 {~\%~} 5 = 2 \).

Streng genommen sind es keine Reste, sondern Restklassen, weil auch \( 12:5 = 2 {\rm~Rest~} 2 \) den gleichen Rest erzeugt, d.h. \(7\) und \(12\) sind in der gleichen Menge = Restklasse. \(6\) und \(1\) wären auch in einer gleichen Menge, aber einer anderen, nämlich derjenigen, die den Rest 1 erzeugen.

(Alles bei Teilung durch 5, bei anderen Teilungen läuft es analog ab, erzeugt aber dann andere Mengen = Restklassen.)

Hier geht es jedoch nur um die Reste an sich, und die ganze Theorie wird einfach ingoriert.

Grüße,

M.B.

---

Danke für die Erklärung :)