Hashing mit Sondierung
Implementieren Sie eine Hash-Tabelle HashMap<T> mit Strings als Schlüsseln und einem beliebigen Typ T für die Werte.
- Mit get() greifen Sie auf die Werte der Tabelle zu. Falls ein Schlüssel nicht vorhanden ist, wird null zurückgeliefert.
- Mit add() fügen Sie Werte ein. Die Methode soll false zurückliefern falls kein Platz zum Einfügen gefunden wird. Doppelte Schlüssel werden wie üblich überschrieben.
- size() soll die Anzahl der belegten Stellen der Hash-Tabelle zurückliefern, fillRatio() den Füllgrad.
- toList() liefert eine (java.util)-Liste mit den Nutzdaten der belegten Zellen. Zur konkreten Relisierung können Sie java.util.LinkedList verwenden. Die Reihenfolge der Ergebnisliste ist nicht vorgegeben.
- hashcode() liefert den Hash-Wert: Ein String $k = k_1k_2...k_n$ wird mit der Hash-Funktion aus den Vorlesungsvideos auf einen Hash-Code abgebildet ($N \in \mathbb{N}^+$ sei die Größe der Tabelle, $B\in \mathbb{N}^+$ die Basis):
$$
h(k) = \Big( k_1 \cdot B^{n-1} + k_2 \cdot B^{n-2} + ... + k_{n-1} \cdot B^1 + k_{n} \cdot B^0 \Big) \; \% \; N,
%h(k) = \Big( \sum_{i=1}^n B^i \cdot k_i \Big) \, \% \, N.
$$
Vermeiden Sie Überläufe mit dem Horner-Schema. Um Kollisionen zu behandeln sondieren Sie maximal $N$-mal mit folgender rekursiver Funktion ($m$ sei die Anzahl der Sondierungen):
$$
\begin{aligned}
g(m+1) & = ( g(m) + 2m + 1 ) \, \% \, N \\
g(0) & = h(s). \\
\end{aligned}
$$
package de.hsrm.ads;
import java.lang.reflect.Array;
import java.util.LinkedList;
import java.util.List;
public class HashMap<T> {
public class Entry {
String key;
T value;
public Entry(String key, T value) {
this.key = key;
this.value = value;
}
}
// the hash table
Entry[] table;
// size of the hash table
int N;
// used to hash strings with the Horner schema.
int basis;
public HashMap(int N, int basis) {
table = (Entry[]) Array.newInstance(Entry[].class.getComponentType(), N);
this.basis = basis;
this.N = N;
}
public int size() {
// FIXME
}
public double fillRatio() {
// FIXME
}
List<T> toList() {
// FIXME
}
public int hashcode(String key) {
// FIXME
}
public T get(String key) {
// FIXME
}
public boolean add(String key, T value) {
// FIXME
}
}
Subato
