Advanced   Java   Services

HashSet

Im Unterschied zu Arraylist und Vector ist ein HashSetobjekt die Realisierung einer Menge von Objekten im mathematischen Sinn. In einer Menge darf jedes Element nur genau einmal vorkommen. Dagegen kann in einer ArrayList oder in einem Vector ein Element quasibeliebig oft vorkommen. Jedes dieser Elemente erhält dann einen eigenen Index. In einer Menge gibt es dagegen keinen Index. Bei der Aufnahme eines neuen Elements wird geprüft ob es schon vorhanden ist. Ist es bereits in der Menge wird es nicht (mehr) aufgenommen.

Mit der Methode equals() aus der Klasse Object prüft ein HashSetObjekt ob ein Objekt bereits in die Menge aufgenommen worden. Das neu aufzunehmende Objekt wird mit allen bereits aufgenommenen verglichen. Liefert die Methode equals immer false, so wird das Element aufgenommen. Liefert dagegen ein Vergleich einmal true, so werden die Vergleiche beendet und das Element wird nicht aufgenommen. Daraus ergibt sich sofort die Frage, wann zwei Objekte als gleich angesehen werden.

Wann man zwei Objekte als gleich ansieht, richtet sich nach dem inneren Aufbau der Objekte und nach ihrer Klassenzugehörigkeit. Objekte, deren Klassen nicht in Vererbung stehen können nie gleich sein. Selbst wenn ein Stringobjekt und ein StringBuilderobjekt ein- und dieselbe Zeichenfolge beherbergen sind sie nicht gleich. Zwei Stringobjekte mit gleichem Inhalt sind jedoch gleich, dagegen sind zwei StringBuilderobjekte mit der gleichen Zeichenfolge nicht gleich. Die Erklärung für dieses Verhalten ist garnicht so schwer.

Objekte der Rootklasse Object sind Objekte ohne Dateninhalt, daher könnte man sagen, sie sind alle gleich. Objekte abgeleiteter Klassen können jedoch völlig verschieden sein. Es ist daher weitaus sinnvoller alle Objekte der Klasse Objekt als verschieden anzusehen und die so arbeitende Methode zu vererben. Genau das geschieht. Die Methode equals() aus Object vergleicht daher die Adressen der Objekte. Und da jedes Objekt seinen eigenen Adressraum hat, sind also alle Objekte verschieden voneinander.

Ganz anders dagegen arbeitet die Methode equals aus der Klasse String. Die Entwickler haben die Methode so überschrieben, daß die Zeichenketten verglichen werden. Zwei Strings sind also gleich, wenn ihre Inhalte gleich sind.

Will man also die Methode equals() verwenden, muß man darauf achten, ob eine Klasse diese Methode lediglich von Object erbt - und damit Adressen vergleicht - oder ob - wie etwa in der Klasse String - eine Klasse diese Methode reimplementiert und die Gleichheit neu definiert. Man stellt dies durch einen Blick in die Api fest. Taucht die Methode equals() in der Dokumentation einer abgeleiteten Klasse auf, so wurde sie überschrieben.

Wie funktioniert das Speichern eines Objekte in einem Hashset, und wie das Wiederauffinden eines Objekts? Ein HashCode ist eine Art ID - im Format eines int -, die nach einem bestimmten Algorithmus aus den Daten eines Objektes gebildet wird. Spielen Sicherheitsaspekte eine Rolle, so verwendet man eine sogenannte Einwegfunktion. Diese bildet aus den Daten eine Kennziffer, die nicht zurückverfolgt werden kann, d.h. aus der ID kann man die Daten nicht wiederherstellen. Die ID ist dann eine Testziffer mit der man z. Bsp. feststellen kann ob eine heruntergeladene Datei beschädigt oder manipuliert wurde. Im Falle eines HashSet hat die Kennziffer eine andere Funktion. Die Hashsetnummer verwendet ein HashSetobjekt um alle Objekte mit dieser Nummer an der gleichen Stelle zu speichern. Im englischen verwendet man für diese Speicherstellen gerne das Wort 'bucket', also Eimer. Alle Objekte mit demselben Hashcode landen also im gleichen Eimer. Kommt ein Objekt mit einem neuen Hascode in die Menge, wird - bildlich gesprochen - ein neuer Eimer bereitgestellt. Man kann sich das ganze auch als Büroschrank mit durch den Hashcode numerierten Schubladen vorstellen. Die Elemente werden also nach Hashcodenummern sortiert und liegen dann aber unsortiert in jeder Schublade.

Wie schaut nun der Algorithmus aus, wenn ein HashSet feststellen muß, ob ein neues Element aufgenommen werden kann? Mit Hilfe des HashCodes des Aufnahmekandidaten sucht HashSet zuerst die Schublade mit dieser Nummer. Wird Sie nicht gefunden, wird das Element als neu eingestuft und in einer neuen Schublade mit dieser Nummer abgelegt. Andernfalls wird ja eine Schublade mit dieser Nummer gefunden. Dann werden alle Objekte in dieser Schublade mit dem Aufnahmekandidaten verglichen. Dazu verwendet HashSet die Methode equals(). Wird mit dieser Methode kein Objekt gefunden, wird das Objekt in dieser Schublade gespeichert, andernfalls wird es nicht aufgenommen. Das Neuaufnehmen eines Objektes funktioniert also nach demselben Algorithmus wie das Suchen eines Objektes.

Aus der Arbeitsweise des soebenen beschriebenen Algorithmus wird folgendes klar: Ist es für eine selbst entworfene Klasse sinnvoll die Methode equals() zu reimplementieren, so muß man auch die Methode hashCode() neu schreiben. Nur so können die Objekte richtig in einem HashSet gespeichert werden. Objekte, die mit equals gleich sind müssen den gleichen HashCode erzeugen. Andernfalls werden Sie ja - um bei diesen Bild zu bleiben - in verschiedenen Eimern gespeichert. Es gilt daher die einfache

• Regel:
• Überschreibt man in einer Klasse die Methode equals(), so muß man auch die Methode hashCode() überschreiben und dafür sorgen, daß gleiche Elemente einen gleichen HashCode liefern.

Handelt es sich bei den zu vergleichenden Daten um Strings, was oft der Fall ist, so zieht man sich meist auf die hashCode-Methode von String zurück.

Der HashCodeAlgorithmus von String führt zu einer Art lexikographischen Vorsortierung. Unterschiede am Anfang eines Strings fallen stärker ins Gewicht als am Ende eines Strings. So hat der String "Anna" den HashCode 2045632 und "Anne" den HashCode 2045636 (e kommt vier Stellen nach a im Alphabet), wogegen "Enna" den HashCode 2164796 hat. "Enna" ist also auch vom Hashcode her viel weiter 'hinten' als "Anna".

/**
 * Returns a hash code for this string. The hash code for a
 * String object is computed as
 * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 * using int arithmetic, where s[i] is the
 * ith character of the string, n is the length of
 * the string, and ^ indicates exponentiation.
 * (The hash value of the empty string is zero.)
 *
 * @return  a hash code value for this object.
 */
public int hashCode()
{
  int h = hash;
  int len = count;
  if (h == 0 && len > 0)
  {
    int off = offset;
    char val[] = value;

      for (int i = 0; i < len; i++)
      {
        h = 31*h + val[off++];
      }
      hash = h;
  }
  return h;
}

Für die Klasse ArrayList benötigt man das Import java.util.*;

Nehmen Sie einige Objekte des Typs Object in eine HashSet auf und bestätigien Sie das oben beschriebene Verhalten

Zeigen Sie, daß sich StringBuilder- oder StringBufferobjekte genauso verhalten wie Objekte vom Typ Objekt.

Untersuchen nun das Verhalten Hashset bei Aufnahme von Strings.

Verhalten sich Objekte vom Typ Date bei Aufnahme in ein HashSet ehre so wie Stringobjekte oder eher so wie StringBuilderobjekte?

Suchen Sie weitere Klassen in der Api, die equals reimplementiert haben.