11.5 Die Klasse Hashtable und assoziative Speicher 

Eine Hashtabelle (engl. Hashtable) ist eine sehr schnelle Datenstruktur, die nach einem interessanten Prinzip funktioniert. Eine Hashtabelle ist ein assoziativer Speicher, der die Schlüssel (engl. Keys) mit Werten (engl. Value) verknüpft. Diese Datenstruktur ist vergleichbar mit einem Wörterbuch oder Nachschlagewerk. Betrachten wir beispielsweise ein Telefonbuch. Dort sind Namen (Schlüssel) mit Nummern (Werten) verbunden. Die Frage nach einer Telefonnummer kann die Datenstruktur schnell beantworten, die andere Richtung dauert wesentlich länger, da hier keine Verknüpfung existiert. Sie ist immer nur einseitig. Für wechselseitige Beziehungen ist die Klasse Hashtable daher schlecht vorbereitet.

11.5.1 Ein Objekt der Klasse Hashtable erzeugen 

Unter Java ist eine Hashtabelle durch ein Exemplar der Klasse Hashtable repräsentiert. Sie eignet sich ideal dazu, viele Elemente zu speichern und sie über die Schlüssel schnell wieder verfügbar zu machen. Für eine geringe Zahl von Elementen ist sie dafür weniger geeignet als ein Vektor, da die Verwaltung der Daten relativ viel Platz benötigt.

class java.util.Hashtable

extends Dictionary
implements Map, Cloneable, Serializable

Hashtable() Erzeugt eine neue Hashtabelle.

11.5.2 Einfügen und Abfragen der Datenstruktur 

Wir haben gesagt, dass die Elemente der Hashtabelle Paare aus Schlüssel und zugehörigem Wert sind. Das Wiederfinden der Werte ist effizient nur über Schlüssel möglich.

Daten einfügen

Zum Hinzufügen von Schlüssel-Wert-Paaren dient die Methode put(). Als Parameter gibt man ein Objekt als Schlüssel und ein weiteres Objekt als dazugehörigen Wert an. Schlüssel und Wert müssen beide ungleich null sein. Für Objekte, die als Schlüssel in einer Hashtabelle dienen sollen, müssen die Methoden hashCode() und equals() in geeigneter Weise (der Bedeutung oder Semantik des Objekts entsprechend) untereinander konsistent implementiert sein.

class java.util.Hashtable

extends Dictionary
implements Map, Cloneable, Serializable

Object put( Object key, Object value ) Speichert den Schlüssel und den Wert in der Hashtabelle. Falls sich zu diesem Schlüssel schon ein Eintrag in der Hashtabelle befand, so wird der vorherige Wert zum Schlüssel zurückgegeben. Andernfalls ist der Rückgabewert null. Die Methode ist vorgegeben vom Interface Map. Sie überschreibt die Methode aus der Oberklasse Dictionary.

Object get( Object key ) Liefert das erfragte Objekt, welches mit dem entsprechenden Schlüssel verbunden ist, vorgegeben vom Interface Map. Es überschreibt die Methode von Dictionary. Falls kein passendes Objekt vorhanden ist, liefert die Funktion null.

Object remove( Object key ) Löscht den Schlüssel und seinen zugehörigen Wert. Wenn der Schlüssel nicht in der Hashtabelle ist, so macht die Funktion nichts. Im letzten Atemzug wird noch der Wert zum Schlüssel zurückgegeben. Die Methode überschreibt remove() von Dictionary, definiert im Interface Map.

void clear() Löscht die Hashtabelle, sodass sie keine Werte mehr enthält.1

Hashtable alidhersteller = new Hashtable();  // 6

 
		alidhersteller.put( "Carbo, spanischer Sekt", "Freixenet" );
alidhersteller.put( "ibu Stapelchips", "Bahlsen Chipsletten" );
alidhersteller.put( "Ko-kra Katzenfutter", "felix Katzenfutter" );

alidhersteller.put( "Küchenpapier", "Zewa" );
alidhersteller.put( "Nuss-Nougat-Creme", "Zentis" );
alidhersteller.put( "Pommes Frites", "McCaine" );
Hashtable num = new Hashtable();
num.put( "zwei", new Integer(2) );
num.put( "drei", new Float(3.0f) );

Daten auslesen

Um wieder ein Element auszulesen, verwenden wir get(). Da alle erdenklichen Objekte in der Hashtabelle abgelegt werden können, muss beachtet werden, dass eine Typanpassung für den Objekttyp eingesetzt wird.

Integer n = (Integer)numbers.get( "zwei" );

if ( n != null )
  System.out.println( "zwei = " + n.intValue() );

Existiert der Schlüssel, existiert der Wert?

Neben get() kann auch noch mit einer anderen Funktion das Vorhandensein eines Schlüssels getestet werden: containsKey() überprüft, ob ein Schlüssel in der Tabelle vorkommt, und gibt dann ein true zurück. Die Implementierung unterscheidet sich nicht wesentlich von get()²  . Mit size() lässt sich die Anzahl der Werte in der Hashtabelle erfragen. isEmpty() entspricht einem size() == 0, gibt also true zurück, falls die Hashtabelle keine Elemente enthält.

boolean containsKey( Object key ) Liefert true, falls der Schlüssel in der Hashtabelle vorkommt; Vorgabe vom Interface Map. Der Vergleich auf Gleichheit wird mit equals() durchgeführt. Demnach sollte das zu vergleichende Objekt diese Methode aus Object passend überschreiben. hashCode() und equals() müssen miteinander konsistent sein. Aus der Gleichheit zweier Objekte unter equals() muss auch die Gleichheit ihrer hashCode()s folgen.

Im Gegensatz zu get() und containsKey(), die das Auffinden eines Werts bei gegebenem Schlüssel erlauben, lässt sich auch nach den Werten ohne Schlüssel suchen. Dies ist allerdings wesentlich langsamer, da alle Werte der Reihe nach durchsucht werden müssen. Die Klasse bietet hierzu contains() an. Seitdem unter Java 1.2 die Container-Klassen neu strukturiert wurden, ist containtsValue() gleichwertig zu contains() hinzugekommen.

boolean containsValue( Object value ) Liefert true, falls Hashtable ein oder mehrere Werte enthält, die mit dem Objekt inhaltlich übereinstimmen; Vorgabe vom Interface Map.

11.5.3 Die Arbeitsweise einer Hashtabelle 

Die Hashtabelle arbeitet mit Schlüssel-Werte-Paaren. Aus dem Schlüssel wird nach einer Funktion – der so genannten Hashfunktion – ein Hashcode berechnet. Dieser dient dann als Index für ein internes Array. Dieses Array hat zu Anfang eine feste Größe. Wenn später eine Anfrage nach dem Schlüssel gestellt wird, muss einfach diese Berechnung erfolgen und wir können dann an dieser Stelle nachsehen. Wir können uns eine einfache Hashfunktion für folgendes Problem denken: Beliebige Zeichenketten sollen in der Hashtabelle abgelegt werden. Die Hashfunktion summiert einfach alle ASCII-Werte der Buchstaben auf und nimmt sie Modulo 77. Dann können in einem Array mit 77 Elementen 77 verschiedene Wörter aufgenommen werden. Leider hat diese Technik einen entscheidenden Nachteil. Denn wenn zwei unterschiedliche Wörter denselben Hashcode besitzen, dann kommt es zu einer Kollision. Darauf muss die Datenstruktur vorbereitet sein. Hier gibt es verschiedene Lösungsansätze. Die unter Java implementierte Variante benutzt eine verkettete Liste. Falls eine Kollision auftritt, so wird der Hashcode beibehalten und der Schlüssel beziehungsweise Wert in einem Listenelement an den vorhandenen Eintrag angehängt. Eine Sortierung findet nicht statt. Wir merken, dass es auf eine geschickte Wahl der Hashfunktion ankommt. Denn eine »dumme« Hashfunktion, die beispielsweise alle Schlüssel auf nur einen Indexwert abbilden würde, erreicht keine Verteilung, sondern lediglich eine lange Liste von Schlüssel-Wert-Paaren. Doch auch bei der besten Verteilung über 77 Elemente ist nach dem Einfügen des 78. Elements irgendwo eine Liste mit mindestens zwei Elementen aufgebaut. Je länger die Listen der miteinander kollidierenden Einträge werden, desto langsamer wird der Zugriff auf die Datenstruktur Hashtable.

Um ein Maß für den Füllgrad zu bekommen, wird ein Füllfaktor (Füllgrad) (engl. Load Factor) eingeführt. Dieser liegt zwischen 0 % und 100 %. Ist er 0 %, so bedeutet dies, dass die Hashtabelle leer ist, ist er 100 %, so enthält die Hashtabelle genau so viele Einträge, wie das interne Array Elemente umfasst. Die Verteilung der Einträge auf die Array-Elemente wird dabei in der Regel ungleichmäßig sein. Einige Array-Elemente enthalten bereits (kurze) Listen mit kollidierenden Einträgen, während andere Array-Elemente noch unbenutzt sind. Der Füllfaktor einer Hashtabelle sollte für einen schnellen Zugriff nicht höher als 75% sein, das heißt, ein Viertel der Array-Elemente wird grundsätzlich nicht belegt.

Der Füllfaktor und die Konstruktoren

Wir haben oben schon kurz über den Füllfaktor gesprochen. Dieser gibt an, wie »voll« die Hashtabelle ist. Es lässt sich nun einstellen, dass die Hashtabelle sich automatisch vergrößert, damit der Zugriff wieder schneller wird. Dazu ordnen wir dem Füllgrad einen Prozentwert als Fließkommazahl zwischen 0.0 und 1.0 zu. Ein Wert von 0.75 entspricht also dem oben angesprochenen idealen Füllgrad von 75 Prozent. Es gibt einen Konstruktor für Hashtable-Exemplare, der die Angabe eines Füllgrads erlaubt. Ist dieser überschritten, so wird die Hashtabelle neu berechnet. Dies nennt sich rehash. Dazu wird eine neue Hashtabelle angelegt, deren Array größer als das alte ist. Jeder Wert aus der alten Hashtabelle wird dabei gemäß der Hashfunktion an die passende Stelle in das größere Array eingefügt. Ist dies für alle Elemente geschehen, wird die alte Hashtabelle gelöscht. Dieses Kopieren und Neuberechnen dauert zwar einige Zeit, doch direkt danach lassen sich die Anfragen an die Datenstruktur wieder schnell beantworten. Wenn die Hashtabelle zu oft vergrößert und neu organisiert werden muss, ist dies natürlich ein gewaltiger Geschwindigkeitsnachteil. Doch durch die Vergrößerung wird der Zugriff wieder schneller. Das Rehashen kann nicht ausdrücklich erzwungen werden.

Inklusive des Standard-Konstruktors gibt es drei Konstruktoren:

class java.util.Hashtable

extends Dictionary
implements Map, Cloneable, Serializable

Hashtable() Die Hashtabelle enthält initial eine Kapazität von 11 Einträgen3  und einen Füllfaktor von 75%, also 0.75.

Hashtable( int initialCapacity ) Erzeugt eine Hashtabelle mit einer vorgegebenen Kapazität und dem Füllfaktor 0.75.

Hashtable( int initialCapacity, float loadFactor ) Erzeugt eine Hashtabelle mit einer vorgegebenen Kapazität und dem angegebenen Füllfaktor.

Die anfängliche Größe des Arrays lässt sich in den beiden anderen Konstruktoren angeben. Ist dort ein unsinniger Wert angegeben, wird eine IllegalArgumentException ausgeworfen. Zusätzlich kann der Füllfaktor angegeben werden; ist dieser falsch, so wird ebenfalls diese Exception ausgelöst. initialCapacity muss größer als die geplante Nutzlast der Hashtabelle gewählt werden. Das heißt, bei geplanten 1000 Einträgen etwa 1000*(1/0.75) = 1333. Ist ein Füllfaktor nicht explizit angegeben, so wird die Hashtabelle dann vergrößert und neu organisiert, wenn die Anzahl der Einträge in der Hashtabelle größer gleich 0.75 * Größe des Arrays ist.

11.5.4 Aufzählen der Elemente 

Das Enumerator-Interface ist für Aufzählungen von Objektgruppen entworfen worden. Mit keys() und elements() bietet Hashtable zwei Methoden an, die eine Aufzählung zurückgeben. Die Reihenfolge der Aufzählung ist dabei nicht festgelegt. Beide Methoden sind synchronized, was aber keine Rolle spielt, da nachfolgende Änderungen am Hashtabellen-Exemplar verboten sind. Wir müssen uns bewusst sein, dass die Aufzählungen auf keiner Kopie der Hashtabelle arbeiten, sondern auf dem Original. Werden also Änderungen in der Datenstruktur vorgenommen, verhalten sich die Aufzählungen in undefinierter Weise. Es ist unbestimmt, ob neu eingefügte Schlüssel oder Werte in einer laufenden Aufzählung berücksichtigt werden. Außerdem können aus der Hashtabelle entfernte Einträge noch als Teil einer bereits laufenden Aufzählung erscheinen.

class java.util.Hashtable

extends Dictionary
implements Map, Cloneable, Serializable

Enumeration keys() Liefert eine Aufzählung der Schlüssel. Überschreibt keys() in Dictionary.

Enumeration elements() Liefert eine Aufzählung der Werte. Überschreibt elements() in Dictionary.

11.5.5 Ausgabe der Hashtabelle und Gleichheitstest 

Die Klasse Hashtable überschreibt toString() von Object. Die Rückgabe besteht aus mehreren Einträgen, durch Kommas getrennt und in Klammern gesetzt. Jeder Eintrag ist wiederum eine ASCII-Repräsentation. Diese wird erzeugt, indem wiederum toString() für jeden Schlüssel und den zugehörigen Wert aufgerufen wird.

class java.util.Hashtable

extends Dictionary
implements Map, Cloneable, Serializable

String toString() Liefert eine Zeichenkette, die eine Repräsentation der Hashtabelle zurückgibt. Die Ausgabe der Hashtabelle liefert jeden enthaltenen Schlüssel, gefolgt von einem Gleichheitszeichen und dem zugehörigen Wert.

boolean equals( Object o ) Damit die Gleichheit von zwei Hashtabellen gezeigt werden kann, vergleicht equals() alle Elemente von beiden Tabellen. Die Methode ist von der Schnittstelle Map vorgegeben. Sie überschreibt die Methode von Object.

int hashCode() Liefert den Hashcode des Hashtable-Objekts wie in der Beschreibung von Map gefordert. Überschreibt damit hashCode() von Object. Dies ist nur dann wichtig, wenn eine Hashtabelle selbst als Schlüssel benutzt werden soll. Dies ist jedoch problematisch, falls die Hashtabelle später noch verändert werden soll.4

11.5.6 Klonen 

Die Hashtabelle erweitert eine allgemeinere Klasse für assoziative Felder, die Klasse java.util.Dictionary. Im nächsten Kapitel wird diese Klasse noch einmal genauer untersucht. Von Dictionary erbt Hashtable eine clone()-Methode. Sie erzeugt eine Kopie der Hashtabelle. Die Kopie bezieht sich allerdings nur auf die Hashtabelle selbst. Die Schlüssel und Werte teilen sich Original und Klon. Diese Form der Kopie nennt sich auch flache Kopie (engl. Shallow Copy). Eine Veränderung an den enthaltenen Schlüssel-/Wert-Objekten betrifft also immer beide Datenstrukturen, und eine unsachgemäße Modifikation kann zu Unregelmäßigkeiten im Original führen. Es bleibt noch zu bemerken, dass das Klonen der Datenstruktur sehr zeit- und platzaufwändig ist.

class java.util.Hashtable

extends Dictionary
implements Map, Cloneable, Serializable

clone() Fertigt eine Kopie der Hashtabelle an, ohne jedoch die Werte selbst zu klonen.

¹   Siehe dazu auch http://www.aldibaran.de/faq/faq5.html#2.

²   Bei get() steht return e.value (wobei das Objekt e den Schlüssel und Wert hält) und in containsKey() einfach dort ein return true.

³   Unter JDK 1.3 besaß die Hashtable im Standard-Konstruktor 101 Elemente. Aber es wird nicht nur im Bundeshaushalt gespart ...

⁴   Fast schon philosophisch wird’s, wenn eine Hashtabelle als Schlüssel oder Wert in sich selbst eingefügt werden soll.