Hashfunktion

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.

Hashfunktion
Hallo,

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?


Ich hab auch ne Frage zur Hashfunktion und zwar kommt in alten Klausuren vor, dass man die Qualität der Streufunktion beurteilen soll.

Wie mach ich das denn?

Also zum einen schätz ich ist der Lastfaktor relevant, aber was sonst noch?
die Kollisionanzahl vielleicht? :confused:


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.


Schau mal auf Folie 89.

Nicht ausgeschlossen. Oder auch beurteilen, welche von zwei Hashfunktionen „besser“ ist.


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 :slight_smile:


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 :wink: und die Werte auch richtig abschreiben … :stuck_out_tongue:

ii) Z.B. h(x1, x2) = 0

iii) O(n)

c) sieht gut aus …

Und nein, Taschenrechner gibt es keine in der Klausur :wink:


ups, ja hab ich wohl falsch abgeschrieben.

Und wie kommt man auf Z.B. h(x1, x2) = 0 ?

Also was bedeutet das ? Das ist mir irgendwie nicht klar.

und zu a) ok wenn dud as sagst. Ich war mir da auch sehr unsicher.


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 :smiley: 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 :smiley:


Hab eure Beiträge mal in den Lösungsvorschlag im Prüfungswiki aufgenommen (https://fsi.informatik.uni-erlangen.de/dw/pruefungen/bachelor/aud/loesungss10). Frage: Ist der Lastfaktor nicht 9/13 = 0,69 da Tabellenlänge 13 ist?


Danke auf jedenfall mal für die erklärung der Aufgabe :smiley:
Hab jetzt erst verstanden was gefragt ist. Und so ergibt sich das ganze gar nicht als so schwierig :wink:

Dankeschön!


klar.


ja absolut richtig.


müsste die b) iii) nicht O(n*m) sein?
n…Anzahl der Einträge
m…Anzahl der Tabellenfelder wenn die ganz Liste z.b. im letzten Tabellenfeld ist


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)


Hi,

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.


Angenommen du hast eine Streutabelle der Länge 8.

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.


danke ihr 2! Ihr seid toll :slight_smile: