HashTable - Lastfaktor

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.

HashTable - Lastfaktor
Vllt kann mir jmd aus meiner momentanen Verwirrung helfen:

Gegeben ist eine HashTable mit 10 Plätzen, bei der Kollisionen durch Verkettung gelöst werden. Nun werden 10 Elemente eingefügt. Durch eine schlechte Hashingfunktion verteilen sich die eingefügten Werte gleichmäßig auf die geraden Indizes, d.h. ich habe 5 Plätze mit verketteten Listen und 5 leere Plätze in meiner Tabelle.

Was ist nun der Lastfaktor?

a) L = 10 / 10 = 100%;
b) L = 5 / 10 = 50%;

Meiner Meinung nach wäre b) sinnvoller, da man ausgehend vom Lastfaktor eine qualitative Beurteilung der Hashingfunktion abgeben könnte.
Laut Korrektur der Hashingaufgabe auf Blatt 12 (Aufgabe 12.1 c)) wäre aber a) korrekt.


a ist korrekt. Menge der Zeichen / Tablegröße


Mit der Definition wäre dann Aufgabe 6b) aus der 2003er Klausur (http://www2.cs.fau.de/Lehre/Algoklausuren/04-03-23_klausur.pdf?language=de) relativ sinnlos, da der Lastfaktor dann einfach n / 8 betragen würde.

Die Tatsache, dass die Hashingfunktion nur 4 der 8 Felder erreichen kann (nämlich 0 1 2 und 4) käme hierbei garnicht zur Geltung.


wird halt einfach eine irreführende Frage sein, wo man überprüfen will ob die Definition des Lastfaktors verstanden wurde. Ich habs am anfang auch so verstanden wie dein Beispiel b) wie auf dem Übungsblatt, wo man von sondiertem Table und verkettetem Listentable den Lastfaktor berechnen sollte. Fands da auch unlogisch, dass beide 100% waren, aber ist halt so.


War mir auch ziemlich sicher dass b) richtig ist und hab deshalb mal auf Google gesucht:

http://www.tcs.informatik.uni-muenchen.de/lehre/SS07/EffAlg/kapIII.pdf

Also haben die Übungsleiter in Übung 12 korrekt korrigiert (auch bei mir).

Weder a) noch b) ist also richtig, sondern: n/8

Ziemlich hinterlistige Fragestellung! daumen-runter


Mal eine ähnliche Frage zum gleichen Thema:

In der Klausur vom März 2006, Aufgabe 7 c) heißt es “Wie viele Zugriffe wären im Mittel nötig, wenn die Kollisionauflösung mittels Verkettung erfolgt wäre?”.

Mit Verkettung sieht die zur Frage gehörende Hashtabelle so aus:

0 -
1 [15]
2 [65] [9]
3 -
4 [74] [11]
5 [5]
6 -

Das müsste nun heißen, dass der Lastfaktor 6/7 beträgt, und damit die durchschnittlichen Zugriffe 13/7, wenn man wie laut Vorlesungsfolien zum Lastfaktor 1 dazu zählt.

Kann das stimmen?


Das mit 1 + Belegungsfaktor ist nur eine Abschätzung.
Du musst hier die Zugriffe für jedes Element aufaddieren und durch die Anzahl der Elemente teilen.

Also: 15 - 1 Zugriff, 65 - 1 Zugriff, 9 - 2 Zugriffe, …
Ergibt aufaddiert 8, geteilt durch 6 Elemente => im Schnitt 4/3 Zugriffe.