brent verbesserung

[MrMassaker]

hi leute!

ich weiss es gibt schon 10 andere threads zur brent verbesserung aber irgendwie hab ich doch noch eine frage:

also falls ein platz schon belegt ist in meiner hash tabelle rechne ich mir dieses j1 und j2 aus. nun gibt es folgende möglichkeiten:

- j1 frei: neues element auf j1
- j1 besetzt, j2 frei: altes elememt auf j2 und neues element auf j1

was tu ich aber wenn beide besetzt sind? rechne ich dann mit der ursprünglichen double hash methode weiter oder muss ich da auch dann noch das j1 und j2 berücksichtigen? :confused:

[kambo]

was tu ich aber wenn beide besetzt sind? j1=( j + h2(k) )mod m
j2=( j + h2(k') )mod m

falls j1 und j2 besetzt sind dann muss du "neue" j1 bzw. j2 bestimmem wo j=j1 dh:

j1=(j1 + h2(k) )mod m
j2= (j1 + h2(k') )mod m

lg

[Georg Kraml]

also falls ein platz schon belegt ist in meiner hash tabelle rechne ich mir dieses j1 und j2 aus. nun gibt es folgende möglichkeiten:

- j1 frei: neues element auf j1
- j1 besetzt, j2 frei: altes elememt auf j2 und neues element auf j1

was tu ich aber wenn beide besetzt sind? rechne ich dann mit der ursprünglichen double hash methode weiter oder muss ich da auch dann noch das j1 und j2 berücksichtigen? :confused:

"Vorläufig", "lokal" mit der ursprünglichen Double-Hash-Methode weitermachen:

- j1 frei: neues Element auf j1
- j1 besetzt, j2 frei: altes Element auf j2 und neues Element auf j1
- j1 besetzt und j2 besetzt: mit j1 einen Schritt weitergehen, j1 für die neue Position und j2 für das "neue alte" Element an der neuen Position neuberechnen, dann zurück zum Start.

.

[Merlin]

klingt ein bischen verwirrend "neues altes " Element, ich schätz das ist dann dasselbe wie ein Post davor von kambo....,

[eva_d]

ja genau.
kambo hat das eh sehr schön und v.a. verständlich aufgeschrieben ;)

[sunflower]

seits euch da sicher, wir haben heut auch rumgetüftelt u. laut dem was im skriptum steht nimmt man wenn beide positionen j1 u. j2 belegt sind, wieder die normale doublehashingmethode u. verusucht so ein position zu finden, d.h: jneu=(h1+n*h2) mod m; n=1..m-1; also

[MrMassaker]

na toll.............

wenn der brent kommt sollens mich doch alle gern haben! :o

[eva_d]

algo seite 110 zeile 8:
hier wird im falle wenn j2 besetzt ist oder j1 nicht besetzt ist, j auf j1 gesetzt und somit weitergerechnet.

[clemensp]

hm ich weiß nicht

vielleicht meinst du e das richtige was die andern auch gemeint haben


schau dir den algorithmus 36 dazu nochmal an...

da kommt genau das raus was die andern oben beschrieben haben

wenn beide positionen belegt sind

wird j1 unser jetziges j das is ja sicher belegt

dann probiert man wieder ob man nicht für den schlüssel der auf der jetzign position j steht eine "billige" alternative findet sollte das neue j1 wieder belegt sein...


für JEDE sondierposition wird die verbesserung von brent angewandt nicht nur für die 1.


aber die sondierpositionen werden ganz normal nach double hashing ausgerechnet ja

[MrMassaker]

aber bleiben wir nicht immer in der ersten position? wir setzen i=0 und wenn da nix gescheites rauskommt dann solange brent anwenden bis es passt oder?

:confused:

[clemensp]

nein

das mit da 1. ja ok es wird auch bei der 0. position angewand bei der ursprungsposition sozusagn die noch keine sondierposition ist.


und nein es wird schon immer anders die position

denn:

wir haben unsere position j die wir uns errechnet haben für unseren einzufügenden wert

die ist belegt mit einem schlüssel

jetzt gehen wir her und berechnen uns die 1. sondierposition für unseren eigentlichen wert
das geht mit

j1=(j + hash2(k)) mod m // man beachte das j haben wird durch die hash1 funktion bekommen also beim 1. durchlauf ist j1 das gleiche wie doublehash(h,i=1)

für den schlüssel der unseren wunschplatz belegt berechnen wir die nächste sondierposition
das ist das j2
j2=(j+hash2(k')) mod m

wenn jetzt
j2 belegt ist dann wird aus unsrem j die position j1

und die schleife geht nochmal durch

mit j = sondierposition 1 !!!!!

[MrMassaker]

ach ja....aber über 1 geht sie dann wirklich nicht hinaus oder?

[sunflower]

ok noch mal zu meinem post, im skriptum steht, dass man wenn j1 belegt u. j2 ebenfalls mit der normalen doublehashing methode weiter macht, wenn man sich den algo auf 110 anschaut, wird j1 das in der 1. berechnung gewonnen wird wieder ins neue j1 eingesetzt.lange rede kurzer sinn, wenn man sich die werte ausrechnet kommt das gleiche raus- also j1 wieder in j1 einzusetzen ist das gleich wie (h1+n*h2)mod m aus dem klassischen doublehashing

[clemensp]

klar die sondierpositionen für den wert den man einfügt sind immer die gleichen wie bei double hashing...

nur das bei jeder position die belegt ist überprüft wird ob der schlüssel der da drinn steht nicht um eine sondierposition verschoben werden kann

[clemensp]

ach ja....aber über 1 geht sie dann wirklich nicht hinaus oder?


dooooch ^^

wennst as dann mit j = j1 durchläufst

errechnet er das neue j1 ja basierend auf dem alten j1

[mosQuito]

j1=( j + h2(k) )mod m
j2=( j + h2(k') )mod m

falls j1 und j2 besetzt sind dann muss du "neue" j1 bzw. j2 bestimmem wo j=j1 dh:

j1=(j1 + h2(k) )mod m
j2= (j1 + h2(k') )mod m

lg

k und k´bleiben gleich oder??
und wenn jetzt wieder beide besetzt wären würde ich dann wieder das j1 von der letzten berechnung nehmen ?sozusagen j1=(j1 + h2(k) )mod m das grüne j1???´
aja und diese positionen berechen ich doch eh nur für das element das ich ganz am anfang versucht hab einzufügen oder??

[clemensp]

bitte guckts euch nomal ganz genau algorithmus 36 an und denkts n schritt für schritt durch

1. ja k bleibt immer gleich ... das is das was ich einfügen will
k' bleibt nicht immer gleich...
das wird immer der schlüssel der uns grad die aktuelle sondierungsposition blockiert

für den berechnen wir seine nächste sondierungsposition
die ist j2..
wenn die frei ist dann können wir ihn dorthin gebn und unsren schlüssel den ma einfügen wolln an die freigewordene stelle reingebn


zu deinen grünen und roten j1
wenn ich verstandn hab was du meinst..

dann das grüne j1 is die nächste sondierposition für unseren schlüssel k
das rote j1 is das jetzige j und was beim vorign durchgang der schleife das damalige j1 war

siehe zeile 8:
j=j1;

[mosQuito]

bitte guckts euch nomal ganz genau algorithmus 36 an und denkts n schritt für schritt durch

1. ja k bleibt immer gleich ... das is das was ich einfügen will
k' bleibt nicht immer gleich...
das wird immer der schlüssel der uns grad die aktuelle sondierungsposition blockiert
ooooook das hab ich noch verstanden..der schlüssel in j1 wird dann k´


für den berechnen wir seine nächste sondierungsposition
die ist j2..
wenn die frei ist dann können wir ihn dorthin gebn und unsren schlüssel den ma einfügen wolln an die freigewordene stelle reingebn
wir berechnen uns eine neue position für den schlüssel der uns die position blockiert in dem fall für den, der im j1 steht???das heisst ich setze, das was in j1 ist auf j2 und den schlüssel k setz ich auf j1???


zu deinen grünen und roten j1
wenn ich verstandn hab was du meinst..

dann das grüne j1 is die nächste sondierposition für unseren schlüssel k
das rote j1 is das jetzige j und was beim vorign durchgang der schleife das damalige j1 war

siehe zeile 8:
j=j1;
das hab ich schon verstanden hehe..ich wollt nur wissen ob ich bei einem weitern durchlauf dieses grüne j1 an der stelle des roten j1 jez nehmen müsste

[clemensp]

müsstest du


ookay noch ein versuch

schau dir auf seite 109 die hin2 linken abbildungen unten an

31 is unser k
10 is in dem fall unser k'

j ist die position wo 10 drinnen steht und wo 31 reinsoll

j1 is die position wo der 19er drinnen steht
j2 is die position wo der pfeil vom 10er hinzeigt



so

wenn jetz in j2 was drinnen wär und nicht frei wäre

dann wäre nun
j dort wo da 19er steht
j1 müsste man aus dem j + hash2(k) berechnen

j2 berechnet sich aus dem j + hash2(19)


i hoff des is jetz kloa

(wenn des morgn kommt mach ichs sicher falsch weil i schö langsam dann selber nimma weiß was richtig is *ggg*)

[mosQuito]

guddi das heißt j und k´werden geändert und das einzige was gleich bleibt is k ...merci :thumb: