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.
	Index Schlüssel/Name Schlüsselwert/Körpergröße Verweis 0       ...       4 heinz 188   ...                       26 joachim 173   ...       80 ludwig 191   81       ...       89 dorothea 172   90
	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.
	Index Schlüssel/Name Schlüsselwert/Körpergröße Verweis 0       ...       4 heinz 188   ...                       26 joachim 173   ...       80 ludwig 191 81 81 paris 178   ...       89 dorothea 172   90
	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