Quadratisches Sondieren vs Lineares Sondieren

[meagain02]

Was ist der Vorteil vom Quadratischen Sondieren gegenüber dem lineraren Sondieren?

bzw was ist der Vorteil vom Double Hashing gegenüber dem linearen Sondieren.

Die 2te Frage kann ich anhand des Buches beantworten aber aus der 1ten werde ich nicht schlau.

Double Hashing ist 1e gute Annäherung an das uniformes Hashing. Ausserdem ist es leicht zu implementieren.
Warum ist es leichter zu implementieren?

Mfg Isabella

[Flowyes]

1. Frage: Der Vorteil ist ja, dass die Suchzeiten beim quad. Sondieren kürzer sind. Warum das genau so ist könnte ich aber nicht erklären, aber aus der Tabelle erkennt man das sofort.
Warum ist es leichter zu implementieren?
Double Hashing arbeitet in der Praxis sehr gut, und ist eine gute Approximation an uniformes Hashing. Na ja, wenn man m gut wählt, zwei Hashfunktionen wählt, und eine Laufvariable i nicht vergisst, dann hat man Double Hashing fast schon implementiert. Für eine Methode, die die im Skriptum genannten Eigenschaften liefern kann, ist diese Implementation also tatsächlich leicht...

[Wolfman]

a) Lineares Sondieren hat nur Deta(m) verschiedne Sondierungsreihenfolgen. Die erste Postion eines Elements legt die gesamte Sequenz der Elmente fest(da immer um eins weiter). wird Primäre Häufung oder Cluster bildung genannt.

b)Qudratisches Sondieren: Hier legt die erste Position des ersten elements nicht die ganze sequenz fest....aber es hat auch nur Deta(m) verschiednen Sondierungsreihenfolgen das heisst das es nach einer zeit zur Sekundären Häufung kommt.

c)Double Hashing: Hier hat man Deta(m^2) verschiedne Sonierungsreihenfolgen...kommt ziemlich an uniform hashing ran so wie Flowyes gesagt hat.

Hoffe das ich nix vergessen hab oder gar was falsches verzapft hab ;) aber das wärs im großen und ganzen..

[Sensei]

Deta(m)
Guat erklärt, der Griechische Buchstabe heißt aber THETA :D :thumb: :D

[Wolfman]

Ahhhh du penner :P hab doch gwusst das da was suckt *gg* frage hast da schon einen Algo gebastelt für 2 fach zusammenhängen graph? wenn nein mach ich jetzt einen also poste schnell..

[Sensei]

Ahhhh du penner :P hab doch gwusst das da was suckt *gg* frage hast da schon einen Algo gebastelt für 2 fach zusammenhängen graph? wenn nein mach ich jetzt einen also poste schnell..
Hab einen eigenen Thread dazu aufgemacht... dort findet sich auch mein Code ;)

[onuris]

Danke

[g4borg]

b)Qudratisches Sondieren: Hier legt die erste Position des ersten elements nicht die ganze sequenz fest....aber es hat auch nur Deta(m) verschiednen Sondierungsreihenfolgen das heisst das es nach einer zeit zur Sekundären Häufung kommt.


hmm. wenn ich mir quadratisches hashing ansehe, ist das immer noch abhängig von der ersten position, es ist bloss eine zusätzliche "variable" eingeführt die weiterspringt. diese jedoch bedingt, dass es nicht mehr ganz so linear abläuft (der quadratteil wächst immerhin quadratisch, aber auch abhängig von der zahl und der konstante). sehe ich das richtig?
abstrakt betrachtet hängt es aber immer noch gewissermassen von h1(k) ab... womöglich* ist es aber spät

* es ist spät.