Doppeltes Hashing

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Doppeltes Hashing
Hat hier jemand Ahnung vom doppelten Hashing? Das muss sowas wie das Anwenden einer anderen Funktion im Kollisionsfall sein, mehr konnte ich aus den 4 Zeilen im Skript nicht rauslesen (Kap14_1.pdf, Seite 23). Wobei ich diese tolle blaue Formel nicht ganz verstehe…

Ganz konkret würde ich gerne die Aufgabe 7c der Klausur 4/2000 verstehen. Da werden ganz merkwürdige h-ähnliche Funktionen gegeben, mit denen man die Hash-Tabelle aufbauen soll.


bei doppelten hashing verwendest du im kollisionsfall einfech die 2. hashfunktion, wie du ja schon richtig erkannt hast, wobei i gleich der anzahl der kollisionen entspricht.

bei der aufgabe ist komm ich auf folgendes ergebnis:

0 1 2 3 4 5 6 7 8 9 10 11 12
14 28 8 18 27 21 36 5 15


Dabei nimmst du halt noch eine 2. Hashfunktion die abhängig von i ist mit dazu.(wenns zu einer Kollision kommt)
Das schaut dann ungef. so aus:
h(x, i) = h1 (x) + i*h2(x)
dabei dann z.B.:
h1(x) = x mod 7
h2 (x)= 1+ (x mod 4)

Aber wenn dann musst du das nur anwenden!Und nicht selbst eine HashFunktion erfinden!In der Übung ist doch auch doppeltes Hashing drangek.!


Hiho, ich geh an eine solche Aufgabe wie folgt:
Einzufügen: 14|21|27|28|8|18|15|36|5 → jetzt Plätze nach
xmod13: 1| 8| 1| 2|8| 5| 2| 10|5 → jetzt Plätze nach
xmod11 4|11| 6| 7|9| 8| 5| 4|6

jetzt mit der 14 anfangen einzufügen:
0 1 2 3 4 5 6 7 8 9 10 11 12
14 28 8 16 27 21 36 5 15

Vorgehen wie folgt:
14 einfügen mit xmod13: ok.
21 einfügen mit xmod13: ok.
27 einfügen mit xmod13: Kollision auf 1-> +ih1 ausführen, also (1+6)mod13=7, dort einfügen: ok.
28 ok.
8: Kollision, neue Position bei (8+9)mod13 → 4, einfügen ok.
18 ok.
15: Kollision, neue Position bei (2+5)mod13=7 → Kollision, neue Position bei (2+2*5)mod13=12, einfügen ok.
36 ok.
5: Kollision, neue Position (5+6)mod13=11, einfügen ok.
Fertig!

nochmal hashing…
wenn ich das jetzt jetzt richtig verstanden habe, wendet man die
h0(x)= x mod 13 erst mal auf alle Schlüssel an. Sollten jetzt Schlüssel doppelt belegt sein, muss man die DOPPELTE Hashfunktion anwenden :
h( x,i )= [( (x mod 13 ) + ( i * ( 1 + ( x mod 11 )))) mod 13] !

Die Funktion h1(x) ist nur zum Einsetzten in die Double-Hashfunktion da , oder ?

Meine Belegung ist wie die aus der Lösung :
Platz | Schlüssel :
0 -->2 7 -->27
1–>14 8–>21
2–>28 9–>–
3–>-- 10–>36
4–>8 11–>5
5–>-- 12–>15
6–>leer
Frag nur nochmal nach, weil bei obigen Posts irgendwie immer die 2 fehlt, und die muss man tatsächlich bis :
i = 8 in die 2. Funktion einsetzten. Kann mir jemand zustimmen ? :anx:


die obigen posts beziehen sich auf die klausur 04.00, da kommt keine 2 vor

ups…
sorry, überlesen. Dann stimmt meine Verteilung also ! :smiley: