Hashfunktion - FSI-Informatik-Forum

Forum: Bachelor › Algorithmik › Algorithmen und Datenstrukturen

Hashfunktion

Page: 1 2 next ›

heftig

Member since Oct 2011

138 posts

2012-01-22, 14:09 #1

Subject: 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?

kaut Member since May 2011 380 posts	2012-01-22, 16:01 #2 +0 +0 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?

dario
planlos wie immer

Member since May 2011

94 posts

2012-01-22, 17:20 #3

Quote by kaut:
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?

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.

mergesort list = foldl merge [] $ map mergesort $ split list -- haskell <3

meisterT

Member since Nov 2005

994 posts

2012-01-22, 20:48 #4

In reply to post #1

Quote by heftig:
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.

Schau mal auf Folie 89.

Quote by heftig:
Und wird es auch von uns verlangt,d ass wir Hashfunktionen selbst aufstellen können?

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

FAU Online Judge

edisch

Member since Oct 2011

131 posts

2012-01-24, 11:06 #5

Hi, ich hab mal die aufgabe 4 aus der Klausur vom 05.08.10 bearbeitet und bin mir ziemlich unsicher. Hier mal die Aufgabenstellung:

[Image: http://s14.directupload.net/images/120124/2mbsiuxi.png]

[Image: http://s14.directupload.net/images/120124/2mbsiuxi.png]

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
[Image: http://s1.directupload.net/images/120124/tkv4u7yv.png]

[Image: http://s1.directupload.net/images/120124/tkv4u7yv.png]

ich hab die werte gleich eingefügt. Stimmt das so?

[Image: http://s7.directupload.net/images/120124/ftf5vy7f.png]

Mit dieser Teilaufgabe kann ich gar nichts anfangen. Was muss man da denn machen? Irgendwie ist mir auch die Aufgabenstellung unklar.

[Image: http://s1.directupload.net/images/120124/4skngact.png]

[Image: http://s1.directupload.net/images/120124/4skngact.png]

keine Ahnung, wegen der Teilaufgabe zuvor.

[Image: http://s1.directupload.net/images/120124/ymmdmhji.png]

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

Maddoc Member since May 2011 526 posts	2012-01-24, 11:32 #6 +0 +0 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

edisch Member since Oct 2011 131 posts	2012-01-24, 13:28 #7 +0 +0 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.

Maddoc

Member since May 2011

526 posts

2012-01-24, 14:34 #8

Quote by edisch:
[...] Und wie kommt man auf Z.B. h(x1, x2) = 0 ?

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

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.

Quote by edisch:
[...] und zu a) ok wenn dud as sagst. Ich war mir da auch sehr unsicher.

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

LaCucaracha Member since Jan 2012 43 posts	2012-01-24, 17:58 #9 +0 +0 Hab eure Beiträge mal in den Lösungsvorschlag im Prüfungswiki aufgenommen (https://fsi.informatik.uni-erlangen.de/dw/pruefungen/bache…). Frage: Ist der Lastfaktor nicht 9/13 = 0,69 da Tabellenlänge 13 ist?

edisch

Member since Oct 2011

131 posts

2012-01-24, 20:53 #10

In reply to post #8

Quote by Maddoc:
Quote by edisch:
[...] Und wie kommt man auf Z.B. h(x1, x2) = 0 ?

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

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.

Quote by edisch:
[...] und zu a) ok wenn dud as sagst. Ich war mir da auch sehr unsicher.

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

Dankeschön!

L. F. Ant Member since May 2011 1164 posts	2012-01-25, 00:30 #11 In reply to post #9 +0 +0 Quote by LaCucaracha: Frage: Ist der Lastfaktor nicht 9/13 = 0,69 da Tabellenlänge 13 ist? klar.
	Your argument is irrelephant.

edisch Member since Oct 2011 131 posts	2012-01-25, 11:42 #12 +0 +0 Quote by L. F. Ant: Quote by LaCucaracha: Frage: Ist der Lastfaktor nicht 9/13 = 0,69 da Tabellenlänge 13 ist? klar. ja absolut richtig.

Blubbman Member since Nov 2011 46 posts	2012-02-01, 22:21 #13 +0 +0 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

knix

Member since Oct 2009

242 posts

2012-02-01, 22:44 #14

Quote by Blubbman:
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)

just the BEST theorem: ec(G) = tᵤ(G) ∏(deg(v) - 1)!

bewi1992 Member since Oct 2011 189 posts	2012-02-21, 18:12 #15 +0 +0 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.

Page: 1 2 next ›

Go to forum

Datenschutz | Kontakt