Warum überhaupt Hashing?
Eine (duplikatfreie) Symboltabelle lässt sich u. a. über eine verkettete Liste, ein geordnetes Array oder einen binären Suchbaum realisieren. Welches Ziel verfolgt Hashing? Was ist der Preis?
Grundidee und Begriff der Hashfunktion
Beschreiben Sie die Grundidee des Hashings. Was leistet eine Hashfunktion in diesem Kontext?
Welche Probleme müssen beim Hashing gelöst werden?
Klassischer Kompromiss zwischen Raum und Zeit
Hashing ist ein Kompromiss zwischen Speicherplatz und Laufzeit. Skizzieren Sie die beiden Extremfälle.
Idealistisches Ziel und die Wahl der Ziffern
Was ist das idealistische Ziel bei der Berechnung einer Hashfunktion?
Definition
Was bedeutet die Bedingung \(|M| \geq |\mathbb{Z}_n|\)[1], und welche Konsequenz folgt daraus unmittelbar?
Surjektiv und gleichverteilt
Was bedeutet es, dass eine Hashfunktion surjektiv bzw. gleichverteilt ist?
Horner-Methode
Warum verwendet Horners Methode zur Berechnung des Hashes einer Zeichenkette den Faktor 31?
Modulo-Hashfunktion und Primzahlen
Warum sollte \(n\) bei der Modulo-Hashfunktion möglichst eine Primzahl sein?
Periodische Schlüssel
Ihre Schlüssel kommen mit einer festen Schrittweite \(a\) (z. B. 12). Sie verwenden \(h(x) = x \bmod n\).Wie wählen Sie \(n\) sinnvoll?
Muss vs. soll
Welche Regel müssen __hash__/__eq__ (Python) bzw. hashCode()/equals(Object) (Java) zwingend erfüllen, welche ist nur wünschenswert?
Konstante Hashfunktion
Eine Klasse gibt in hashCode() / __hash__ immer 1 zurück. Ist das korrekt? Welche Folgen hat es?
Unveränderlichkeit nach dem Einfügen
Warum darf ein Objekt, nachdem es in einem Set/Dictionary gespeichert wurde, hinsichtlich der hash-relevanten Felder nicht mehr verändert werden? Was passiert sonst konkret?
Pythons hash() ändert sich
In Python liefert hash("...") für denselben String nach jedem Neustart der Umgebung einen anderen Wert. Warum — und was folgt daraus?
Zweistufige Indexberechnung
Bei der konkreten Verwendung entsteht der Tabellenindex in zwei Stufen: zuerst die Hashfunktion, dann der eigentliche Index.
Beschreiben Sie beide Stufen und ordnen Sie zu, wer jeweils zuständig ist (Schlüsseltyp vs. Datenstruktur).
Was passiert mit dem Hashwert und mit dem Index, wenn die Tabelle vergrößert wird?
Warum ist diese Trennung sinnvoll?
Belegungsfaktor
Was ist der Belegungsfaktor \(\alpha\) einer Hashtabelle, und warum ist er für die Effizienz entscheidend?
Nennen Sie die zwei grundsätzlichen Strategien zur Kollisionsauflösung und ihren Kernunterschied. Welche erlaubt 𝜶 > 1?
Separate vs. direkte Verkettung
Worin unterscheiden sich separate und direkte Verkettung?
Sondieren kann scheitern
Welche Sondierungsfunktion kann scheitern und somit für einen Wert kein freier Platz gefunden werden, obwohl die Tabelle nicht voll ist?
Einfügen mit linearem Sondieren
Fügen Sie in eine leere Hashtabelle mit \(n = 7\) und \(h^{mod}_7\) nacheinander die Werte 8, 15, 22 mit linearem Sondieren ein. Wie sieht die Tabelle aus?
Löschen bei offener Adressierung
Beim Löschen eines Elements aus einer Hashtabelle mit offener Adressierung darf man den Platz nicht einfach auf frei/nil setzen. Warum nicht — und wie löst man das Problem? Was ist dabei zu beachten?
Denial of Service über Hashkollisionen
Erläutern Sie am Beispiel von Java's String.hashCode(), wie ein Angriff auf die algorithmische Komplexität funktioniert und wie man sich dagegen schützt.