Double Hashing

[Petzi]

ich hab da ein kleines Problem mit double hashing und ich hoff dass mir wer weiterhelfen kann

Angabe: m=7; einzufügende Elemente: 10,19,31,22,14,16
h1(k)=k mod7
h2(k)= 1+ (k mod5)
(ist noch aus dem Skriptum vom SS 2002)

wenn ich jetzt 10 einfügen will, dann steht im Skript dass es an die Stelle 3 kommt
bei mir steht es aber an Stelle 4, weil ich ja (h1(k) + i*h2(k))mod m rechne -> ((10mod7) + 1*(1+(10mod5)))mod7 = 4

nach dem Buch nach zu gehen, rechnen die nur h1(k)=10mod7=3
dann würd`s passen

aber wie rechne ich das jetzt wirklich aus?????


MfG Petzi :confused:

[Stella]

Hi!
Du darfst das "i" in (h1(k) + i*h2(k))mod m erst bei einer Kollision erhöhen. Daher ist es am Anfang "0" und der Teil mit h2(k) fällt weg. Du betrachtest also immer nur h1(k), ausser es kommt zu einer Kollision.

Lg Stella

[the_unclean]

siehe auch
http://hades.gothic.at/iforum/showthread.php?threadid=8890

[Petzi]

also setz ich i=1 erst, wenn es zu einer Kollision kommt!?
jetzt wird`s mir klar

Thx for help

[Petzi]

könnte vielleicht trotzdem irgendwer die Hashtabelle aufzeichnen??

die Hashtabelle im Buch sieht so aus:
0: 31
1: 22
2: 16
3: 10
4:
5: 19
6: 14


hat das noch wer so?

und wie funkt das dann bei der Verbesserung nach Brent?
:confused: :confused:

[abmue]

hallo, ja komme auf die tabelle vom buch. bei der verbesserung nach brendt
siehts so aus:

0: 14
1: 22
2: 16
3: 31
4: 10
5: 19
6:

bei dieser version, prüfst du, falls es zu einer kollision kommt, für beide werte den hashwert mit i=1. Falls der für den einzufügenden frei ist trägst du ihn ganz normal ein, falls nicht, aber für die zahl die schon drinnenstand schon, nimmst du diese und trägst sie dort ein, wo sie für i=1 stehen sollte und die andere für i=0. in unserem fall gab es dann eh nur bei 10 und 31 eine kollision..

ist ein bißchen blöd zu erklären, aber schau dir einfach an was der pseudocode im script macht...

lg
abmue

[Stella]

Habs nachgerechnet, und komm auf das selbe: bei 10 gibts keine Kollision(i=0) - kommt auf 3,
19 kommt auf 5 (auch da gibts keine probleme),
31 mod 7 wäre 3 - dieser platz ist schon besetzt, daher i=1 -> 31 kommt auf 0,
22 mod 7=1, 1 noch nicht besetzt, also 22 dort einfügen,
14 mod 7=0, doch auf 0 steht bereits 31, i wird wieder 1, doch da kommts zu einer weiteren kollision(5 würde rauskommen, aber der platz ist auch schon besetzt), i bekommt den wert 2 zugewiesen, doch das ergebnis hier ist 3(auch schon besetzt), i wird erhöht -> i=3: ergebnis der hashfunktion ist nun 1 (ebenfalls besetzt), schließlich wird i=4, und hier kommt 6 raus, was noch nicht besetzt ist --> 14 kommt auf 6
bei 16 mod 7 ist das ergebnis 2, daher kommt 16 auf 2

ad Brent's Verbesserung)
allgemein: wenn wir ein element x einfügen wollen, an dieser stelle aber bereits das element y steht, dann wird nicht nur für das x der nächste wert berechnet, sondern auch für das y.

angewendet auf dieses beispiel:
10 kommt ganz normal auf platz 3 und 19 auf platz 5. jetzt kommt 31 dran: 31 mod 7 ist ja 3, was aber besetzt ist. jetzt werden j1 und j2 berechnet: j1= j+h2(k) mod m : j ist die position, an der wir das element eigentlich einfügen wollten(also 3) und k ist ja 31, also 3+h2(k)=5 mod 7=5(j1)
j2=j+h2(k') mod m : k' ist das element, das an der position 3 steht (hier 10). einsetzten - (3+1) mod 7 = 4(j2)
j1 ist besetzt, j2 frei, das bedeutet, dass jetzt das element 10(was auf platz 3 steht) auf j2(4) verschoben wird, und 31 auf platz 3 eingefügt wird.

hoffe das war jetzt halbwegs verständlich!
lg stella

[FaKe]

@abmue&stella danke ... irgendwie war ich schon zu verwirrt um Brent zu verstehen. aber das erklärte hat mir nochmal den stoß in die richtige richtung gegeben