Hash-Verfahren sind Speicherungs- und Suchverfahren, bei denen die Adressen von Datensätzen aus den zugehörigen Schlüsseln errechnet werden, d.h., daß Indexpositionen aufgrund der Schlüsselelemente vergeben werden.

Schlüssel und Schlüsselinformation

Schlüssel müssen dazu eindeutig vergeben werden (die Menge der Schlüssel bildet ein Set). Problematisch ist die Verteilung der Schlüssel auf einen Speicherbereich: Man denke sich eine Tabelle mit Indizes, in welche die Schlüssel eingetragen werden sollen. In einem einfachen Ansatz könnte man z.B. Personalnummern als Indizes festlegen. Man steht allerdings vor dem Problem, daß man viel zuviel Speicher belegt, den man gar nicht nutzt. Noch problematischer stellt sich die Speicherung von nicht-ganzahligen Werten dar. In einem Wörterbuch sollte bspw. das Wort der Schlüssel sein. Wie aber kann man einen String auf eine Tabelle abbilden? Dazu muß man den Schlüssel in geeigneter Form transformieren.

Für eine solche Abbildung sind Hash-Verfahren zuständig. Durch Hash-Funktionen erreicht man eine möglichst gleichmäßige Verteilung im Bereich von Tabellenindizes. Solche Verfahren nennt man auch Streuspeicherung. Operationen wie Suchen, Einfügen und Löschen lassen im Allgemeinen viel schneller realisieren, als bei Schlüsselvergleichsverfahren. Die Anzahl der gespeicherten Schlüssel ist (bei genügend Speicherplatz) unabhängig von der Zeit, die benötigt wird, einen Schlüssel zu suchen (vgl. dazu auch das Beispielprogramm SimpleHash).

Problematisch bei Schlüsseltransformationen sind Adresskollisionen, d.h. mehere Schlüssel werden auf dieselbe Adresse abgebildet. Es lassen sich hier zwei Verfahren zur Bewältigung dieser Problematik unterscheiden:

offenes Hashen

Transformierte Schlüssel, die auf bereits besetzte Adressen treffen, werden in derselben Tabelle auf dem nächsten freien Platz abgelegt

geschlossenes Hashen

jedes Element der Hash-Tabelle ist Anfangselement einer Überlaufkette, d.h. in der Hash-Tabelle stehen nur Zeiger auf die ersten Elemente von Listen.

In der Literatur wird das geschlossenes Hashen als schneller bezeichnet. Das ist auch verständlich, da die Suche nach freien Plätzen, v.a. in relativ vollen Tabellen, eigene Suchstrategien erfordert. Beim offenen Hashen hat man allerdings alle Elemente in einem einzigen Array vorliegen, was weitere Verarbeitung, bspw. Sortieren, erleichtert.

Sets und Maps

Im Collection Framework wurde die altehrwürdige Klasse Hashtable (die es natürlich immer noch gibt) durch die Klassen HashSet und HashMap ersetzt. In der Einführung in das Collection Framework wurde bereits auf die Interfaces Set und Map eingegangen. Zur Wiederholung: Sets sind indizierte Zusammenfassungen von Daten, in denen keine Duplikate erlaubt sind. Die Klasse HashSet, die (u.a.) das Interface Set implementiert, enthält die Methode boolean add(Object o), die das übergebene Objekt in das HashSet einträgt, insofern es noch nicht enthalten ist. Sie liefert den Wert true, wenn das Objekt neu eingetragen wurde und false, wenn das Objekt schon vorher Bestandteil des Sets war. Die Klasse HashSet bedient sich beim Auffinden der Elemente einer Schlüsseltransformation nach einem Hash-Verfahren.

Letzteres gilt auch für die Klasse HashMap. Allerdings werden hier auch Objekte eingetragen, die bereits in der Map vorliegen. Einträge in die HashMap erfolgen über die Methode Object put (Object key, Object value). key ist dabei der zu transformierende Schlüssel, value das einzutragende Objekt (es kann auch beides identisch sein). Liegt zum übergebenen Schlüssel schon ein Objekt vor, so wird dieser an die aufrufende Instanz zurückgegeben. Ansonsten wird null zurückgegeben.

Die Object-Methoden equals() und hashCode()

In jeder Collection muss entschieden werden, ob zwei Objekte "gleich" sind oder nicht, damit bspw. die Methode Collection.contains(Object obj) funktionieren kann. In einer HashMap genügt dies allein nicht, denn zusätzlich muss dann, wenn zwei Objekte gleich sind, auch der durch die Methode hashCode() zurückgegebene Wert übereinstimmen. Im Sonderfall der Identität (a == b) ist dies gegeben, in der Regel muss die Überprüfung der Gleichheit jedoch selbst implementiert werden (Vgl. Beispiel vom Seminarplan).

Dazu ist es notwendig, die Methoden equals() und hashCode() zu überschreiben und so zu implementieren, dass die Semantik der jeweiligen Klasse entspricht. Beispiel:

Zwei Objekte der Klasse Student sind genau dann identisch, wenn ihre Matrikelnummer übereinstimmt - dies müsste in der equals()-Methode implementiert werden. Die Methode hashCode() muss gewährleisten, dass zwei als equal() erkannte Objekte auch den gleichen HashCode zurückgeben, was sich in diesem Fall durch Rückgabe der Matrikelnummer realisieren ließe:

public class Student {

private int matrikelNummer;

private String vorname, nachname;

 

public boolean equals(Object other) {

    if(other instanceof Student) {

       return ((Student)other).matrikelNummer == matrikelNummer);

    }

    return false;

}

 

public int hashCode() {

    return matrikelNummer;

}

}