Hashtable ist eine Klasse, die durch Verwendung des »Hashing« das Speichern und Wiederauffinden von Objekten ermöglicht. Mit Hashing wird ein Kompromiss; zwischen verwendetem Speicherplatz und benötigter Zeit zum Wiederauffinden gespeicherter Elemente gemacht. Hashtable ist von der abstrakten Klasse Dictionary abgeleitet.

Einer Hashtable wird ein bestimmtes Object zusammen mit einem anderen Object, das als Schlüssel dient, hinzugefügt. Mit diesem Schlüssel kann man wieder auf das gespeicherte Objekt zugreifen.

hashCode() liefert das Ergebnis der Hash-Funktion eines Objekts. Um dies zu verstehen, sollte man das Prinzip des »Hashing« kennen:

Beim Hashing werden die Werte in einem Array gespeichert. Als Schlüssel für einen Wert kann ein beliebiges anderes Objekt verwendet werden. Über diesen Schlüssel muss eine bestimmte Array-Position indiziert werden können, um den gespeicherten Wert wiederzufinden. Diese Aufgabe übernimmt die Hash-Funktion. Sie liefert nach Möglichkeit für verschiedene Schlüssel einen unterschiedlichen Wert. Mit diesem wird ein Array indiziert, in dem die Werte gespeichert werden. Hat man ganze Zahlen als Schlüssel, könnte man einfach den Zahlenwert als Index in das Array verwenden. Bei anderen Objekten, wie z. B. String, ist eine eindeutige Umwandlung nicht so einfach und muss durch eine komplexere Funktion (die Hash-Funktion) vorgenommen werden.

Bei der Realisierung dieses Prinzips sind zwei Probleme zu berücksichtigen:

• Der durch die Hash-Funktion berechnete Index kann größer als die Länge des Arrays sein. In diesem Fall wird ein neuer Index berechnet, der sich aus dem Original-Index modulo der Array-Länge ergibt. Dadurch wird sicher gestellt, dass der berechnete Index in jedem Fall innerhalb der Array-Grenzen liegt.
• Es kann vorkommen, dass das Array an der berechneten Stelle bereits belegt ist (Hash-Kollision). Das neue Objekt wird an der ersten folgenden freien Stelle zusammen mit dem Schlüssel gespeichert. Alle Einträge, deren Index auf dieselbe Array-Position verweist, werden untereinander verkettet.

Beim Wiederauffinden von Werten wird zuerst der Wert der Hash-Funktion des Schlüssels ermittelt und der Wert an dem so errechneten Index gesucht. Werden mehrere Schlüssel auf den gleichen Index abgebildet, hat man damit den gesuchten Wert noch nicht gefunden. Um den Wert eindeutig zu finden, verwendet man die mit den Werten abgespeicherten Schlüssel. Ab dem berechneten Index wird schrittweise in Reihenfolge der Verkettung jeder Schlüssel mit dem gesuchten Schlüssel verglichen. Stimmen die Schlüssel überein, hat man den gesuchten Wert gefunden. Auf diese Weise ist es möglich, eine große Wertemenge der Schlüssel auf einen viel kleineren Bereich abzubilden.

Dies erklärt die Implementierung von hashCode() und equals(). hashCode() liefert das Ergebnis der Hash-Funktion, also einen möglichst eindeutigen Array-Index, und equals() stellt eine Vergleichsfunktion dar, mit der ein Wert eines Exemplars mit dem Wert eines anderen Exemplars verglichen werden kann.

Da das allgemeine Prinzip des Hashens bekannt ist, wird nun direkt auf die Klasse Hashtable eingegangen:

Dem Konstruktor der Klasse Hashtable kann die Größe, mit der das zugrunde liegende Array initialisiert werden soll, übergeben werden. Wird dies nicht gemacht, besitzt das Array anfangs hundert Elemente.

Der Hashtable werden mit

public synchronized Object put(Object key, Object value)

neue Objekte zugefügt. Die Daten werden als Object übergeben, damit man sie variabel halten kann.

Da jede Klasse in Java von Object abgeleitet ist, können auch Exemplare aller Klassen der Methode put() als Parameter übergeben werden. Allerdings darf für keinen der Parameter der Wert null übergeben werden, da sonst eine NullPointerException ausgelöst wird. Wird der Hashtable ein weiteres Element hinzugefügt, obwohl deren Kapazität schon erschöpft ist, wird automatisch die Methode rehash() aufgerufen:

rehash() nimmt eine Reorganisation der Hashtable vor. Bei der Reorganisation wird das zugrunde liegende Array erweitert, und die enthaltenen Objekte werden an den Positionen gespeichert, die mit der neuen Länge berechnet wurden.

Wird ein Schlüssel angegeben, der bereits in der Hashtable vorhanden ist, wird diesem Schlüssel der neue Wert zugeordnet. Der alte Wert wird überschrieben und von put() als Ergebnis zurückgegeben. Wenn sich der übergebene Schlüssel noch nicht in der Hashtable befindet, hat put() den Rückgabewert null.

Da die Methoden hashCode() und equals() in der Klasse Object definiert sind, sind sie bei allen Java-Objekten verfügbar. Bei Bedarf kann hashCode() überschrieben werden, um gegebenenfalls Kollisionen zu vermeiden.

Die folgende Klasse Person zeigt, wie hashCode() überschrieben wird:

  class Person {
    public String surname;  // Vorname
    public String name;     // Nachname
    public int age;         // Alter
  
    public Person(String surname, String name, int age) {
      // Werte speichern
      this.surname = surname;
      this.name = name;
      this.age = age;
    }
  
    public int hashCode() {
      // Rückgabe des HashCodes
      return  (surname+name).hashCode()+age;
    }
  
    public boolean equals(Object obj) {
      // Ist das übergebene Objekt vom Typ 'Person'?
      if (obj instanceof Person) {
        // Wenn ja, vergleich Werte
        return ((surname.equals(((Person)obj).surname))
               && (name.equals(((Person)obj).name))
               && (age  == ((Person)obj).age));
      }
      return false;
    }
  }

Die Klasse Person stellt die Daten einer Person dar. Wird sie als Schlüssel verwendet, könnte man anhand dieser Daten weitere Merkmale, wie z. B. Beruf oder Wohnort, auffindbar machen.

Die Implementierung von hashCode() sollte für jeden Schlüssel eine möglichst eindeutige Zahl liefern. Hierfür werden in diesem Fall die bereits vorhandenen hashCode()-Methoden von surname und name verwendet. Zu diesem Wert wird zusätzlich age addiert.

Der Methode equals() kann jedes Objekt übergeben werden. Sie muss true liefern, wenn die Werte des übergebenen Objekts mit den eigenen identisch sind. Doch um die Werte von zwei Objekten vergleichen zu können, muss zuerst einmal sichergestellt werden, dass das übergebene Objekt vom richtigen Typ ist. Ist dies der Fall, kann die Werteüberprüfung stattfinden.

Mit der Methode

  public synchronized Object get(Object key)

kann man die zuvor mit der Methode put() gespeicherten Objekte wieder aus der Hashtable auslesen. Wurde kein Wert mit dem Schlüssel key gespeichert, liefert get() als Ergebnis null.

Die Klasse Hashtable besitzt weitere Methoden, mit denen der aktuelle Inhalt abgefragt werden kann. Sie können der elektronischen Referenz entnommen werden.