Hashing Tabelle implementieren mit Java Code

Question

Aufgabe Hashing:

In dieser Aufgabe sollen Sie eine simple Hashabelle implementieren. Zunächst können Sie davon ausgehen, dass die Schlüssel vom Typ Integer sind.

Legen Sie eine Datei SimpleHT.java ohne main-Methode an.

• Ein Object vom Typ SimpleHT verwaltet eine Menge von Schlüssel-Wert-Paaren, wobei Schlüssel und Werte vom Typ Integer sind. Legen Sie in SimpleHT eine private innere Klasse Pair an, sodass ein Pair-Objekt genau ein Schlüssel-Wert-Paar beinhaltet.

• Die Hashtabelle ist als Array (oder ArrayList) mit m Einträgen organisiert, wobei jeder Eintrag eine verkettete Liste von Pair-Objekten enthält. (Die verketteten Listen dienen der Kollisionsauflösung, und die Hashtabelle soll so funktionieren, wie in der Vorlesung beschrieben.) Der Kontruktor von SimpleHT erwartet m als einzigen Parameter.

• Erstmal können Sie einfach die naive Hashfunktion (key mod m) verwenden. Diese Funktion ist sehr schlecht: Stammen die Schlüssel etwa aus dem Universum {m · k | k ∈ N}, dann werden alle Paare in der gleichen verketteten List abgelegt. In Aufgabe 7.3 werden Sie die Implementierung für beliebige Hashfunktionen verallgemeinern. Deswegen sollten Sie bereits jetzt eine private Hilfsfunktion anlegen, welche aus dem Schlüssel die Adresse der verketteten Liste bestimmt:
private int addressOfList(Integer key) // welche Liste ist zuständig? Hinweis: Der Operator % ist in Java streng genommen nicht der Modulo-Operator und
kann ein negatives Ergebnis zurückgeben.

• Die Grundoperationen der Hashtabelle sind Einfügen, Auslesen, und Entfernen. Wenn beim Einfügen bereits ein Paar mit gleichem Schlüssel existiert, wird der Wert einfach überschrieben. Wenn beim Auslesen kein Paar mit dem gewünschten Schlüssel existiert, wird null zurückgegeben. Wenn beim Löschen kein Paar mit dem gewünschten Schlüssel existiert, wird false zurückgegeben (und ansonsten true).

public void insert(Integer key, Integer value)
public Integer get(Integer key)
public boolean remove(Integer key)

Bestimmen Sie die Addresse der zuständigen Liste immer mit addressOfList. Abge- sehen vom Konstruktor und den Grundoperationen hat die Klasse keine öffentlichen Methoden oder Attribute.

Hinweis: Sie dürfen die Bibliotheken ArrayList, LinkedList, List, und ListIterator aus java.util, sowie die Methode java.lang.Math.floorMod verwenden.

Answer 1

Antwort mit KI erzeugt

Hier ist die geforderte Implementierung der Klasse SimpleHT in Java, welche die beschriebene Hash-Tabelle realisiert. Diese Klasse enthält eine innere Klasse Pair zur Verwaltung der Schlüssel-Wert-Paare, und verwendet ArrayLists von verketteten Listen zur Behandlung von Kollisionen in der Hash-Tabelle.

java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;

public class SimpleHT {

    // Innere Klasse für Schlüssel-Wert-Paare
    private class Pair {
        Integer key;
        Integer value;

        Pair(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }

    // Die Hashtabelle als Array von verketteten Listen
    private ArrayList<LinkedList<Pair>> table;
    private int m;

    // Konstruktor der Klasse SimpleHT
    public SimpleHT(int m) {
        this.m = m;
        table = new ArrayList<>(m);
        for (int i = 0; i < m; i++) {
            table.add(new LinkedList<>());
        }
    }

    // Hilfsfunktion zur Bestimmung der Adresse der verketteten Liste
    private int addressOfList(Integer key) {
        return Math.floorMod(key, m);
    }

    // Einfügen eines Schlüssel-Wert-Paares in die Hashtabelle
    public void insert(Integer key, Integer value) {
        int index = addressOfList(key);
        LinkedList<Pair> list = table.get(index);

        // Suchen, ob das Schlüssel bereits existiert
        for (Pair pair : list) {
            if (pair.key.equals(key)) {
                // Wert überschreiben, falls Schlüssel existiert
                pair.value = value;
                return;
            }
        }

        // Neues Paar hinzufügen, wenn Schlüssel nicht existiert
        list.add(new Pair(key, value));
    }

    // Auslesen eines Wertes anhand des Schlüssels aus der Hashtabelle
    public Integer get(Integer key) {
        int index = addressOfList(key);
        LinkedList<Pair> list = table.get(index);

        // Suchen des Schlüssel-Wert-Paares
        for (Pair pair : list) {
            if (pair.key.equals(key)) {
                return pair.value;
            }
        }

        // Rückgabe von null, falls Schlüssel nicht existiert
        return null;
    }

    // Entfernen eines Schlüssel-Wert-Paares aus der Hashtabelle
    public boolean remove(Integer key) {
        int index = addressOfList(key);
        LinkedList<Pair> list = table.get(index);

        ListIterator<Pair> iterator = list.listIterator();
        while (iterator.hasNext()) {
            Pair pair = iterator.next();
            if (pair.key.equals(key)) {
                iterator.remove();
                return true;
            }
        }

        // Rückgabe von false, falls Schlüssel nicht existiert
        return false;
    }
}

Erklärung der Implementierung:

1. Innere Klasse Pair: Diese Klasse speichert ein Schlüssel-Wert-Paar.
2. Konstruktor: Initialisiert die Tabelle mit m verketteten Listen. Jede Position im Array der Hashtabelle ist eine LinkedList von Pair-Objekten.
3. Hilfsfunktion addressOfList: Berechnet die Indexadresse der verketteten Liste für einen gegebenen Schlüssel mithilfe von Math.floorMod.
4. Einfügen (insert): Wenn ein Schlüssel-Wert-Paar mit einem bestehenden Schlüssel eingefügt wird, wird der Wert überschrieben. Wenn der Schlüssel noch nicht vorhanden ist, wird ein neues Paar hinzugefügt.
5. Auslesen (get): Sucht nach einem Schlüssel und gibt den zugehörigen Wert zurück oder null, wenn der Schlüssel nicht gefunden wird.
6. Entfernen (remove): Entfernt ein Schlüssel-Wert-Paar und gibt true zurück, wenn das Paar erfolgreich entfernt wurde. Gibt false zurück, wenn der Schlüssel nicht gefunden wird.