30.3 Eine Hashtabelle |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Doppelbelegung | Wir haben
mit unserem Programm den Haschkode verschiedener Namen erzeugt. Betrachten
wir nun eine Tabelle, die neben den Namen, ihre Indexnummer noch einen
Schlüsselwert z.B. die Körpergröße enthält. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Die Suche nach der Körpergröße von Ludwig geht jetzt so: Der Hashkode von Ludwig ist 80, wir suchen also unter dem Indexschlüssel 80 und finden die Körpergröße 191 cm. Was aber wenn wir die Körpergröße von 'paris' (war mal ein Grieche, dessen Vorliebe für schöne Frauen einen Krieg auslöste) fragen? Beim Eintrag in die Hasch-Tabelle gibt es eine Schwierigkeit, denn der Index ist bereits von 'ludwig' belegt. Beim Aufbau der Hashtabelle hilft man sich jetzt so: Da der Versuch scheitert 'Paris' an der Stelle einzutragen, die seinem Hashkode entspricht, sucht man die nächste freie Stelle in der Hastabelle. Es ist in unserem Fall der Platz mit der Indexnummer 81. Damit aber 'paris' unter seinem Hashkode nicht zu finden ist, muss dort ein Verweis ablegt werden, der uns sagt, wo wir ihn finden. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Wie
finden wir jetzt in der Hastabelle die Körpergröße von 'paris'? Wir
ermitteln den Haskode, ein Vergleich des Suchschlüssels 'paris' mit dem
Schlüssel unter dem ermittelten Index schlägt fehl. Der Verweis führt uns
zu dem Index 81. Der Vergleich des Suchschlüssels mit dem Schlüssel bei
dem Index 81 ist erfolgreich. Der Schlüsselwert ist 178 cm. Wir sehen,
dass wir kein reines Schlüsselindiziertes Suchen haben, vielmehr ist es
eine Mischung bei der ein Mal sicher, ab und zu auch 2 (evtl. auch mehr
als 2) Mal auch die
Schlüssel verglichen werden. Die Anzahl der Vergleiche ist aber minimal
gegenüber der Anzahl von Vergleichen bei gewöhnlichen Suchen. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Effizienz | Zwei
Faktoren bestimmen die Effizienz des Hashings. Zum ersten die Kapazität,
also das Fassungsvermögen der Hashtabelle und zum anderen der
Füllungsfaktor, der zwischen 0 (leere Tabelle) und 1 (jeder Platz
der Tabelle belegt) liegt. Ist der Füllungsfaktor zu hoch, so spart man
zwar Speicherplatz, aber die Wahrscheinlichkeit, dass man über mehrere
Verweise 'springen' muss, um zu seinem gesuchten Schlüssel zu kommen,
steigt mit dem Füllungsfaktor. Dies macht man sich am besten dadurch klar,
dass man sich einen Schlüssel 'xy' denkt, dessen Hashkode ebenfalls
80 ist. Der Schlüssel müsste jetzt unter dem Index 82 abgelegt werden,
falls dieser Platz überhaupt frei ist. Nehmen wir das mal an, dann müsste
unter dem Index 81 ein Verweis zu 82 abgelegt werden. Für das Finden des
Schlüssels 'xy' ist die Anzahl der Vergleiche schon auf drei
gestiegen. Ist der Füllungsfaktor zu groß und sinkt damit die Effizienz, so wird die Tabelle vergrößert und das Hashen reorganisiert. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
zu | 30.4 Die Java-Klasse Hashtable | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
zur Startseite | www.pohlig.de (C) MPohlig 2004 |