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.
ich habe ein paar Fragen zur Hashfunktion. Ich habe noch die Unterlagen von leztem Semester und bin jetzt etwas verwirrt.
Sind dieses Semester keine Kollisionsauflösung durch Kombinationsverfahren und Kollisionsauflösung durch Verkettung relevant?
Kann dazu in den neuen Folien irgendwie nichts richtig finden.
Und wird es auch von uns verlangt,d ass wir Hashfunktionen selbst aufstellen können?
naja, eine hashfunktion h(x) = 1 ist offensichtlich unsinn…
h(x) = (x % hashtable.length) * 2 ist auch noch suboptimal, weil sie nur jedes zweite feld überhaupt verwendet
h(x) = (x % hashtable.length) verteilt die elemente gleichmäßig, wenn x gleichmäßig verteilt ist, ist also eine einigermaßen brauchbare hashfunktion.
also algemein: gute hashfunktion ≡ verteilt gleichmäßig und lückenlos.
typische klausurfragen zu dem thema sind auch „warum ist lineares sondieren mit abstand x besser als mit abstand y“, und die antwort ist dann meistens "weil y ein ganzzahliger teiler von hashtable.length ist, und deshalb beim sondieren nicht alle felder berücksichtigt werden.
Hi, ich hab mal die aufgabe 4 aus der Klausur vom 05.08.10 bearbeitet und bin mir ziemlich unsicher. Hier mal die Aufgabenstellung:
Also ich würd ja sagen, dass es sich um eine suboptimale Streufunktion handelt, da die Werte nicht gleichmäßig verteilt werden. Auch der Lastfaktor ist nicht optimal
ich hab die werte gleich eingefügt. Stimmt das so?
Mit dieser Teilaufgabe kann ich gar nichts anfangen. Was muss man da denn machen? Irgendwie ist mir auch die Aufgabenstellung unklar.
keine Ahnung, wegen der Teilaufgabe zuvor.
Hier hab ich auch die Werte gleich eingetragen. Stimmt das so?
Dann gab es noch eine letzte Teilaufgabe:
“Welchen lastfaktor hat diese von Ihnen gefüllte Streutabelle, nachdem alle 9 Vektoren eingefügt wurden?”
Also ich hab da als lösung 9/12 =75 %
(Darf man eigentlich in der Klausur nen Taschenrechner benutzen?)
Wär echt cool, wenn mal jemand drüber schauen könnte
a) Nicht sicher, aber ist das nicht eine relativ gute Streufunktion? Die Vorfaktoren und die Länge sind Teilerfremd, es können also alle Felder belegt werden.
b)
i) Pfeile nicht vergessen und die Werte auch richtig abschreiben …
ii) Z.B. h(x1, x2) = 0
iii) O(n)
c) sieht gut aus …
Und nein, Taschenrechner gibt es keine in der Klausur
Die Aufgabenstellung will eine Hashfunktion die garantiert immer eine Liste ergibt (also wenn Elemente eingefügt werden). D.h. alle Elemente müssen den gleichen Index in der Tabelle haben und genau das soll die Funktion machen. Alle Eingaben der Form (x1, x2) werden auf den Index 0 abgebildet, es entsteht also eine Liste.
Hey das ist ne Vermutung! Immerhin können alle Felder der Tabelle belegt werden, besser also nichts. Ob sie darüber hinaus allerdings die Elemente auch gleichmäßig verteilt, puh, da musst jemand anderen fragen
Danke auf jedenfall mal für die erklärung der Aufgabe
Hab jetzt erst verstanden was gefragt ist. Und so ergibt sich das ganze gar nicht als so schwierig
Mithilfe der Hashfunktion kannst du in O(1) den „Index“ in der Tabelle berechnen.
Da sich an dieser Stelle dann eine Liste der Länge n versteckt, musst du im worst-case einmal durch die Liste wandern. => O(n)
also ich hab ne frage zu der Aufgabe aus der Übung:
Begründen Sie kurz, warum bei der vorangehenden Streutabelle ein lineares Sondieren mit
Schrittweite 3 besser ist, als lineares Sondieren mit Schrittweite 4.
Das hatte doch irgendetwas mit dem teilen zu sein, weiß leider nicht mehr was da genau war, hatte das system nicht so durchschaut.
Wenn du jetzt mit Schrittweite 4 sondierst, dann ist das nicht sonderlich sinnvoll.
0 1 2 3 4 5 6 7
Angenommen wir wollen an Position 0 etwas einfügen, da ist aber schon belegt.
Wir sondieren mit Schrittweite 4 und kommen zu Position 4. Da ist auch schon belegt.
Wir sondieren mit Schrittweite 4 und kommen wieder zu Position 0.
Jetzt können wir weiter sondieren, wir kommen aber immer nur auf die Felder 0 und 4.
→ Schlechte Hashfunktion.
Deswegen sollte die Sondierungsschrittweite teilerfremd zur Länge sein, damit alle Felder erreicht werden bevor solche Zyklen wie oben entstehen.
die streutabelle hat die laenge 8, wenn du immer 4 stellen weitergehst, kommst du genau an zwei stellen, immer wieder,immer wieder,immer wieder,immer wieder,immer wieder,immer wieder,…
wenn du 3 stellen weitergehst, kannst du alle stellen der tabelle erreichen. allgemein ist das der fall, wenn laenge und schrittweite teilerfremd sind.