hashverfahren

[the_unclean]

Kann mir jemand die unterschiede und vortiele der einzelnen verfahren sagen, und was primäre häufungen sind?
thx, maz

[Sensei]

premäre häufungen entstehen bei linearem sondieren. d.h. einfach, dass dort wo schon schlüssel sitzen, eher noch welche hintendran kommen. im prinzip eh logisch. sagen wir platz 2,3,4 sind besetzt in hash-tabelle mit 10 plätzen. jetzt is es wahrscheinlicher (3 mal größer is die wahrscheinlichkeit), dass ein schlüssel auf einen dieser drei plätze gesetzt wird, als an einen anderen der restlichen 7 plätze. wird er nun auf 2,3,4 gesetzt, so kann er dort ja nicht hin, wird beim linearen sondieren also auf platz 5 geschoben. und unsere häufung is wieder um eins größer geworden.

unterschiede der verfahren --> siehe skriptum
verfahren aufgelistet:
1) kollision mit linearer liste
2) offene verfahren:
2.1) lineares sondieren (hab ich oben was dazu geschrieben)
2.2) quadratisches sondieren
2.3) double hashing
(Verbesserung nach brent entspr. 2.4)

im prinzip sinds von oben nach unten verbesserungen; beim 2.1 primäre häufungen, beim 2.2 sekundäre häufungen; 2.3 kommt relativ nahe an ideale funktion ran --> kaum häufungen. mit brent-verbesserung noch effizienter.
die genauen funktionen schau dir im skript an...