Lösung von Aufgabe 7
- Als einfache Hashfunktion wird hier der Modulo
verwendet, wobei Double-Werte durch Runden in Integer verwandelt
werden. Was das für Konsequenzen haben kann, erkennt man, wenn man die
SimpleHashtable mit (z.B.) 15000 Werten
betrachtet: Da die Eingabewerte alle im Bereich [0, 10000] liegen,
tritt bei 2/3 Füllgrad eine dramatische Performance-Einbuße auf!
- Einen anderen Effekt sieht man, wenn man die (bessere)
Hashtable mit 20 Werten betrachtet: Das
Programm bricht ab, weil ein Element keinen Platz fand, obwohl wir doch
nur bis zu einem Füllgrad von 90% gehen! Ursache sind Eigenschaften der
Quadratfunktion, die zusammen mit dem Modulo von 20 nur bestimmte Werte
erreicht. Man sollte als Hashgröße daher am besten eine Primzahl
wählen.
- Ein Problem beim Hashen von Double-Werten ist die
Frage, wie ein leerer Platz erkannt wird. Bei höheren Datentypen
erkennt man dies einfach an der null-Referenz.
Beim double könnte man auf die Double-Klasse
ausweichen. Alternativ verwendet man einen speziellen double-Wert, der unter den auftretenden Werten nicht
vorkommt, hier z.B. Double.POSITIVE_INFINITY.
- Bei der Implementierung von put ist zu beachten, dass die Suche nach freiem Platz
irgendwann aufgegeben werden muss. Dies wird hier durch die for-Schleife garantiert, die maximale Zahl von
Versuchen ist also gleich der Größe der Tabelle.
-
Sourcen:
- als lauffähiges Applet