Not logged in. · Lost password · Register

Page:  1  2  next 
heftig
Member since Oct 2011
138 posts
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
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
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
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
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]

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]


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]
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
Avatar
Member since May 2011
526 posts
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 ... :-p

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
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
Avatar
Member since May 2011
526 posts
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 :D 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 :D
LaCucaracha
Member since Jan 2012
43 posts
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
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 :D 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 :D


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

 Dankeschön!
L. F. Ant
Avatar
Member since May 2011
1164 posts
In reply to post #9
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
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
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
Avatar
Member since Oct 2009
242 posts
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
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.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Page:  1  2  next 
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen