Frage: Hallo,
Weiß jemand wie der Code davon aussieht?
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 Funk- tion 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.
