Eine Frage zu Hashing

Question

Guten Abend. Kann mir jemand bitte kurz bei folgender Aufgabe weiterhelfen

Aufgabe
Betrachten Sie doppeltes Hashing mit der Familie von Hashfunktionen

hi(x) = (f(x) +i·g(x)) mod mfü ri= 0, ..., m−1,wobei

f(x) = 2x mod m für eine natürliche Zahl m >3,

g(x) = m* −(x mod m)für eine natürliche Zahl m mit 1 < m* < m.

Seien m = 8 und m* = 2. Betrachten Sie eine anfangs leere Hashtabelle mit 8 Zellen. Geben Sie eine aufsteigend sortierte Sequenz von fünf Zahlen an, sodass die fünfte Zahl nicht ohne Reorganisation der Hashtabelle eingefügt werden kann. Geben Sie eine weitereaufsteigend sortierte Sequenz von acht Zahlen an, die vollständig eingefügt werden kann.""

Ansatz:

Bei der aufsteigend sortierten Sequenz von 5 Zahlen, die nicht ohne Reorganisation der Hashtabelle eingefügt werden kann, hätte ich die Zahlen (1,2,3,4,5) genommen. Weil

2* 1 mod 8 = 2

2 * 2 mod 8 = 4

2 * 3 mod 8 = 6

2 * 4 mod 8 = 8

2 * 5 mod 8 = 2 -> 2 ist schon besetzt. Naja, dann geht's halt auf die 0.

Beim zweiten Aufgabenteil (8 Zahlen ohne Reorganisation) bin ich überfordert. Egal welche Zahl man einsetzt, sie landet doch entweder auf der Position 2, 4, 6 oder 0. Oder versteh ich das mit dem Reorganisieren hier falsch?

Answer 1

Zur Berechnung des Hash-Index reicht es nicht, nur f(x) zu betrachten. Die gesamte Funktion h(x,i) ist auszuwerten.

h(x,i) = [ 2*x mod 8 + i * (2 -(x mod 8)] mod 8

Beim doppelten Hashing beginnt der Algorithmus mit jedem neuen Eingangswert x mit dem Index i=0. Dieser Index wird nur dann um 1 erhöht, sobald eine Kollision auftritt.

Betrachtet man die Zahlenfolge x=1,2,3,4,5 :

h(x=1,i=0) = 2
h(x=2,i=0) = 4
h(x=3,i=0) = 6
h(x=4,i=0) = 0
h(x=5,i=0) = 2

Mit x=5 wäre der Hash-Index 2 bereits belegt. Nun wird i ums eins erhöht

h(x=5,i=1) = 3 (frei)

Die Zahlenfolge 1,2,3,4,5, führt also nicht zu einer Reorganisation der Tabelle. Dazu wählt man anstatt x=5 den Wert x=6. Wegen

h(x=6,i=0) = 4
h(x=6,i=1) = 2
h(x=6,i=2) = 0
h(x=6,i=3) = 6
h(x=6,i=4) = 4
h(x=6,i=5) = 2
h(x=6,i=6) = 0
h(x=6,i=7) = 6

wären alle Tabellenplätze bereits belegt. Die erste gesuchte Zahlenfolge lautet also 1,2,3,4,6.

Eine mögliche Zahlenfolge für die zweite Aufgabe wäre

h(x=1,i=0) = 2
h(x=2,i=0) = 4
h(x=3,i=0) = 6
h(x=4,i=0) = 0
h(x=7,i=1) = 7
h(x=9,i=1) = 3
h(x=11,i=7) = 5
h(x=13,i=7) = 1