Hashing

Wir wollen uns in diesem Kapitel anschauen, wie man Hashing nutzen kann, um effiziente Datenstrukturen zu implementieren. Als Beispiel wollen wir eine Menge mit Hilfe von Hashing implementieren. Wir haben im Kapitel Listen die Datenstruktur Liste und das Java-Interface List kennengelernt. Dieses Interface gehört zu den sogenannten Collection Classes von Java. Zu den Collection-Klassen gehören verschiedene Klassen und Interfaces, die Datenstrukturen modellieren bzw. implementieren.

Abbildung 1: Teil der Collection-Hierachie von Java

Abbildung 1 zeigt einen Teil der Collection-Klassen in Java. Das Interface Iterable umfasst alle Klassen, die iterierbar sind, das heißt, dass man von einem Element zum nächsten springen kann und dass es möglich ist zu überprüfen, ob man beim letzten Element angekommen ist. Das Interface Collection beschreibt alle Datenstrukturen, die Elemente zusammenfassen. Es gibt keine Klassen, die direkt von Collection erben, stattdessen stellt Java zwei weitere Interfaces zur Verfügung, die List und Set heißen. Das Interface List haben wir im Kapitel Listen bereits kennengelernt. In diesem Kapitel wollen wir uns nun mit dem Interface Set beschäftigen.

Mengen

Das Interface Set modelliert die mathematische Menge in Java. Abbildung 2 zeigt die wichtigsten Methoden des Interface Set.

Signatur	Beschreibung
boolean isEmpty()	Liefert genau dann true, wenn die Megen keine Elemente enthält.
int size()	Liefert die Anzahl der Elemente in der Menge.
boolean contains(Object object)	Testet, ob das Element object in der Menge ist.
boolean add(T elem)	Fügt das Element elem zur Menge hinzu, falls es noch nicht vorhanden ist. Die Methode liefert zurück, ob das Element eingefügt wurde.

Abbildung 2: Der abstrakte Datentyp Menge

Wir werden uns im Folgenden mit der Klasse HashSet beschäftigen, die das Interface Set mithilfe von Hashing implementiert. Zuerst einmal wollen wir uns aber anschauen, wie man das Interface verwendet. Dazu betrachten wir die folgende Verwendung des Interface.

public static void main(String[] args) {
    Set<String> shoppingList = new HashSet<String>();

    var success1 = shoppingList.add("Milch");
    System.out.println("Add: " + success1);

    shoppingList.add("Brot");
    shoppingList.add("Eier");

    var success2 = shoppingList.add("Milch");
    System.out.println("Add: " + success2);

    shoppingList.add("Käse");
    System.out.println("Size: " + shoppingList.size());
    System.out.println("Contains: " + shoppingList.contains("Milch"));
}

Hier wird eine Einkaufsliste als Menge modelliert. Wenn ein Gegenstand zum zweiten Mal zur Einkaufsliste hinzugefügt wird, soll es danach weiterhin nur einmal in der Liste erscheinen. Dazu nutzen wir, dass das zweite Einfügen eines Eintrags in die Struktur Set den Eintrag nicht noch einmal hinzufügt.

Die Klasse HashSet

Die Implementierung der Klasse HashSet basiert auf dem effizienten Einfügen und Nachschlagen von Einträgen in einem Array. Wir nutzen eine Hashfunktion, um für einen Eintrag, den wir zur Menge hinzufügen wollen, einen Index zu berechnen, an dem der Eintrag hinzugefügt wird. Eine Hashfunktion ist eine Funktion, die einen großen Definitionsbereich auf einen kleineren Zielbereich abbildet. Im Fall der HashSet ist der Definitionsbereich die Menge der möglichen Einträge der Menge und der Zielbereich ist der Typ int. In Java stellt die Klasse java.lang.Object eine Methode hashCode() zur Verfügung, die einen int liefert. Wenn wir die Laufzeit der Methode hashCode() außer Acht lassen, können wir das Einfügen und Nachschlagen in einer HashSet auf diese Weise in \(\mathcal{O}(1)\) implementieren.

Die Klasse String, die wir in unserem Beispiel genutzt haben, bietet bereits eine Implementierung der Methode hashCode(). Die Methode hashCode() liefert einen int als Ergebnis. Wenn wir diese Methode nutzen wollen, um einem Element einen Index in einem Array zuzuordnen, müssen wir den Zielbereich noch weiter einschränken. Das heißt, wir benötigen im Grunde noch eine weitere Hashfunktion, die einen beliebigen int als Argument erhält und diesen auf den Bereich 0 bis array.length - 1 abbildet. In der Klasse HashSet steht dazu die folgende Methode zur Verfügung.

private static int index(Object object, int capacity) {
   return object == null ? 0 : Math.floorMod(object.hashCode(), capacity);
}

Man nennt den Ansatz, den diese Methode zum Hashing nutzt, Divisionsmethode. Diese Methode berücksichtigt noch den Sonderfall, dass wir null einfügen wollen und nutzt hierfür den Index 0. Wir nutzen hier die Methode Math.floorMod und nicht den Operator %, da % den Remainder und nicht den Modulus implementiert. Das heißt, dass % für ein negatives Argument auch ein negatives Ergebnis liefert. Um das Ergebnis von index als Index in unserem Array zu nutzen, müssen wir gewährleisten, dass es immer größer gleich 0 ist.

Da eine Hashfunktion einen großen Definitionsbereich auf einen kleineren Zielbereich abbildet, muss eine Hashfunktion für unterschiedliche Argumente das gleiche Ergebnis liefern. Man spricht von einer Kollision, wenn zwei unterschiedliche Argumente einer Hashfunktion auf den gleichen Hashwert abgebildet werden. Kollisionen sind im Kontext der Implementierung der Klasse HashSet sehr wichtig, wie wir im Folgenden noch sehen werden. In der Standardimplementierung der HashSet in Java ist die initiale Kapazität zum Beispiel 16. Das heißt, wir müssen uns darüber Gedanken machen, wie wir mit Kollisionen umgehen. Wir werden hier Chaining nutzen, um Kollisionen zu handhaben.

Abbildung 1: Struktur einer HashSet mit Chaining

Aufgrund des Chaining könnten wir grundsätzlich eine feste Größe für das Array nutzen. Wenn sehr viele Einträge in der HashSet sind, verlieren wir auf diese Weise aber die Vorteile der Verwendung eines Arrays. Wir müssen dann die Listen in den einzelnen Einträgen durchsuchen, was linear in der Anzahl der Elemente ist. Daher sollten Kollisionen möglichst vermieden werden. Wenn das Array zu klein ist, können wir Kollisionen aber nicht vermeiden.

Daher kombiniert die Implementierung der HashSet mehrere Konzepte, die wir aus der Vorlesung bereits kennen. Ähnlich wie bei der Implementierung der ArrayList werden wir das Array vergrößern, wenn nicht mehr ausreichend Platz ist. Im Gegensatz zur Implementierung der ArrayList wird das Array aber nicht erweitert, wenn alle Plätze belegt sind, sondern wenn die HashSet einen gewissen Load Factor überschreitet. Der Load Factor ist wie folgt definiert.

\[\text{Load Factor} = \frac{\text{Anzahl Einträge}}{\text{Länge des Arrays}}\]

Als nächstes implementieren wir die Grundstruktur der Klasse HashSet und die einfachsten Methoden.

public class HashSet<E> implements Set<E> {
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
    private static final float MAX_LOAD_FACTOR = 0.75f;

    private LinkedList<E>[] table;
    private int size;

    public HashSet() {
        @SuppressWarnings("unchecked")
        var table = (LinkedList<E>[]) new LinkedList[DEFAULT_INITIAL_CAPACITY];
        this.table = table;
    }

    @Override
    public boolean isEmpty() {
        return this.size() == 0;
    }

    @Override
    public int size() {
        return this.size;
    }

    private float loadFactor() {
        return this.size() / (float) this.table.length;
    }

    private static int index(Object object, int capacity) {
        return object == null ? 0 : Math.floorMod(object.hashCode(), capacity);
    }
}

Nun wollen wir die Methoden add(T) und contains(Object) implementieren. Wir starten mit der Methode zum Testen, ob ein Element sich in der Menge befindet.

@Override
public boolean contains(Object object) {
    var index = HashSet.index(object, this.table.length);
    return this.table[index] != null && this.table[index].contains(object);
}

Wir nutzen die Methode index, um die Liste zu bestimmen, in der wir das Element suchen. Anschließend nutzen wir die Methode contains der Klasse LinkedList, um das konkrete Element in der Liste zu suchen.

Als nächstes wollen wir die Methode zum Hinzufügen eines Eintrags zur Menge implementieren.

@Override
public boolean add(E element) {
    var index = HashSet.index(element, this.table.length);
    var entryExists = this.table[index] != null && this.table[index].contains(element);
    if (entryExists) {
        return false;
    } else {
        if (this.table[index] == null) {
            this.table[index] = new LinkedList<E>();
        }
        this.table[index].add(0, element);
        this.size++;
        return true;
    }
}

Diese Methode überprüft, ob das Element bereits in der entsprechenden Liste existiert. Falls das Element noch nicht existiert, wird es am Beginn der Liste hinzugefügt. An dieser Stelle ist es wichtig, die konkrete Listenimplementierung zu kennen, um eine Methode zu wählen, die effizient in die Liste einfügt.

Ein Aspekt der Methode add fehlt noch. Diese Methode würde dazu führen, dass die Laufzeit der Methode contains mit der Anzahl der Elemente in der HashSet linear wächst. Um dieses Verhalten zu verhindern, vergrößern wir das Array, wenn in die HashSet zu viele Elemente eingefügt wurden. Ob wir das Array erweitern, wird mit Hilfe des Load Factors überprüft. Zu Beginn der Methode add fügen wir zu diesem Zweck den folgenden Code ein.

if (this.loadFactor() > MAX_LOAD_FACTOR) {
    this.table = this.resizedTable();
}

Für die Restrukturierung der Bins nutzen wir die folgende Implementierung.

private LinkedList<E>[] resizedTable() {
    var newCapacity = 2 * this.table.length;
    @SuppressWarnings("unchecked")
    var newTable = (LinkedList<E>[]) new LinkedList[newCapacity];

    for (LinkedList<E> list : this.table) {
        if (list != null) {
            for (E entry : list) {
                var index = HashSet.index(entry, newCapacity);
                if (newTable[index] == null) {
                    newTable[index] = new LinkedList<E>();
                }
                newTable[index].add(0, entry);
            }
        }
    }

    return newTable;
}

Analog zur Implementierung in einer Arrayliste legt diese Methode zuerst ein neues Array an, das doppelt so viele Einträge zur Verfügung stellt. Dann wird durch alle Elemente in allen Listen der HashSet iteriert. Für jedes Element wird unter Berücksichtigung der neuen Kapazität ein Hashwert berechnet. Anschließend wird das Element am Anfang der entsprechenden Liste eingefügt. Falls die Liste noch nicht existiert, wird sie entsprechend angelegt.

Nachdem wir jetzt eine grundlegende Implementierung der Klasse HashSet fertiggestellt haben, wollen wir uns noch einmal mit der Implementierung der Methode hashCode() beschäftigen.

• zurück
• Inhaltsverzeichnis