HashMap

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}
  $$