home  |  suche  |  kontakt/johner  |  institut 
studierende  |  tech-docs  |  mindmailer 

HashMap

Dynamische Datenstrukturen können auch mit Hilfe eines Assoziativspeichers realisiert werden. Dieser Speicher bildet Schlüssel-Wert-Paare, d.h. ein Schlüssel wird auf einen Wert abgebildet und mit Hilfe dieses Wertes kann der passende Eintrag wieder gefunden werden. Eine solche Sammlung bzeichnet man als Hashtable.

So kann z.B.

  • ein Buch anhand der ISBN
  • ein Student anhand seiner Matrikelnummer
  • und ein Bürger anhand der Ausweisnummer

gesucht werden.

Für die Bildung des Schlüssel-Wert-Paars muss es eine Hashfunktion geben.

Regeln für die Hashfunktion

  • Übergabeparameter: Object (nur wenn die Hashfunktion nicht auf dem zu berechnenden Object implementiert wird)
  • Rückgabetyp: int
  • verschiedene Objekte sollten zu verschiedenen Ganzzahlen führen (Injektivität)
  • gleiche Objekte müssen zu gleichen Ganzzahlen führen (beim Einfügen und Suchen)
  • die Ganzzahlen müssen im Intervall [1,GrößeArray] liegen
  • der Aufwand für die Erstellung der Ganzzahlen sollte noch oben begrenzt sein
  • Zahlen sollten gleichmäßig über den Wertebereich verteilt sein

Die Tatsache von Punkt 4, das gleiche Objekte zu gleichen Ganzzahlen führen müssen, führt zu einer engen Beziehung zwischen equals() und der Hashfunktion. Das heißt, wenn x.equals(y) true ist muss auch folgendes gelten:

x.hashCode() == y.hashCode()

Um sicherzustellen, dass beide Methoden konsistent zueinander sind, müssen bei der Berechnung des Hashcodes nur die Informationen eingehen, die auch für die Implementierung von equals() berücksichtigt werden. Es müssen natürlich nicht alle Feldwerte auf den Objekte genutzt werden.

Zur Hilfestellung hier eine Vorgehensweise, wie eine Hashfunktion implementiert werden kann. Das ist nicht die einige Berechnung und bestimmt auch nicht die optimale, reicht aber oft aus. Folgende Formel wird verwendet:

hashcodeNeu = hashcodeAlt * multiplikator + feldwert

  • Der Anfangswert ist ungleich 0 und kann frei gewählt werden, im Beispiel wird 17 verwendet.
  • Mulitplikator ist eine nicht zu grosse Primzahl, im Beispiel 59.
  • alle Feldwerte müssen in ein Integert-Wert umgewandelt werden, zum Beispiel wie folgt:

    • boolean: 0 oder 1
    • byte, char, short, int: auf int casten
    • Referenz (anderes Objekt): dessen hashCode() Methode aufrufen
    • long: in zwei Integer zerlegen
    • double: Double.doubleToLongBits(feldwert) aufrufen, dann in long casten und als long behandeln

package progstruk.hashfunktion;

public class Student {

  private String name;
  private int matrikel;
  private Hochschule hochschule;

  @Override
  public int hashCode() {
    // nicht zu große primzahl
    final int multiplikator = 59;
    // start des hashcode auf eine bliebige Zahl setzen (!= 0)
    int hashcode = 17;
    // hochschule ist selbst ein objekt, dessen hashCode() nutzen
    hashcode = multiplikator * hashcode + hochschule.hashCode();
    // der feldwert 'matrikel' ist bereits ein Integer, keine konvertierung
    hashcode = multiplikator * hashcode + matrikel;
    // hashCode() von String nutzen
    hashcode = multiplikator * hashcode + name.hashCode();
    // alle Werte wurden auf den Startwert aufaddierd und kann so
    // zurückgegeben werden
    return hashcode;
  }

  @Override
  public boolean equals(Object obj) {
    // TODO
    // benutze hier ebenfalls die Feldwerte: name, matrikel, hochschule
    return true;
  }

}

Das Problem bei Maps, in der Objekte mit einem Schlüssel abgespeichert werden ist in den Regeln für die Hashfunktion in Punkt 2 beschrieben. Zwar sollten verschiedene Objekte (bzw. Schlüssel) zu verschiedenen Ganzzahlen führen, das kann aber nicht garantiert werden. Es kann und darf durch aus passieren, dass zwei verschiedene Objekte an den gleichen Index im Array gesetzt werden müssen. Für diesen Fall gibt es zwei Verfahren sogenannte Überlaufbehandlungen.

  1.  offenes Hashverfahren
    Wird festgestellt, dass bereits ein Objekt unter dem selben Index gespeichert ist, wird nach einer freien Stelle im Array gesucht. Die Suche nach dieser freien Stelle kann mit Hilfe einer dieser Sondierungsfunktionen erfolgen.

    • suche solange bis etwas frei ist
    • suche bei jedem n-ten Eintrag
    • nutze quadratische/kubische Funktionen (jeder 3.,9.,27.,..Eintrag)

    Egal welche Sondierungsregel benutzt wird um den neuen Index zu berechnen, der neue Index definiert sich wie folgt:

    neuerIndex =
    ( UrspruenglicherIndex(i) + Sondierungsregel(i) ) % groesseHash;

  2. linear verkettete Liste als Überlauf
    Alle Objekte, die den gleichen Index haben, werden in einer linear verketten Liste (Überlaufliste) gespeichert.
    In der Stelle im Array, auf die der Schlüssel verweist, steht jetzt nicht mehr das Objekt, sondern eine lineare Liste, die ein oder mehrere Objekte enthält. Die Objekte in der Liste haben alle einen Schlüssel, aus dem der selbe Index erzeugt wird.

Eine Hashtabelle stellt nun eine Objektstruktur dar, die nicht nur die Objekte mit Hilfe eines Schlüssels in eine Liste speichert, sonder sie stellte einen assoziativen Speicher dar, der sowohl Schlüssel als auch Wert abbildet. Über den Schlüsselbegriff ist ein direkter Zugriff auf den Wert möglich. Der Oberbegriff für solche Ojektstrukturen ist Map.

Im folgender Abbildung wird z.B. das Object 'Christopher' in einer Hashtabelle gespeichert. Der Schlüssel ist hier die Matrikelnummer (christopher.getMatrikelnummer()) und in ein Integer-Object gewrappt, weil der Schüssel auch ein Object sein muss. Mit Hilfe der Hashfunktion und dem Schlüssel wird der Index '3' ermittelt. Somit wird an die Stelle 3 in der Hashtabelle der Schlüssel (Matrikelnummer) und der Wert (Christopher) mit Hilfe der put-Methode gespeichert.