Lesson 4 Hash Functions Flashcards
Was ist eine Hashfunktion?
Eine Hashfunktion ist eine Abbildung H: K -> S, bei der K die Menge der Schlüssel und S die Menge der Hashwerte ist. Die Funktion ordnet jedem Schlüssel einen Hashwert zu, der als Speicherindex dient.
Was ist eine Kollision in einer Hashtabelle?
Eine Kollision tritt auf, wenn zwei unterschiedliche Schlüssel k und k’ denselben Hashwert haben, d. h., wenn H(k) = H(k’) gilt.
Was sind die Anforderungen an eine gute Hashfunktion?
Eine gute Hashfunktion sollte schnell berechenbar sein, eine gleichmäßige Verteilung der Hashwerte erzeugen und Kollisionen minimieren.
Was ist direkte Adressierung?
Bei der direkten Adressierung wird der Schlüssel direkt als Index für den Speicher verwendet. Dies funktioniert jedoch nur, wenn die Menge der möglichen Schlüssel klein ist.
Was ist eine Hashtabelle?
Eine Hashtabelle ist eine Datenstruktur, die verwendet wird, um (Schlüssel, Wert)-Paare zu speichern. Die Speicherposition des Wertes wird durch den Hashwert des Schlüssels bestimmt.
Wie funktioniert die Kollisionserkennung in einer Hashtabelle?
Kollisionen können durch verschiedene Techniken gelöst werden, z. B. Verkettung (Chaining) oder Sondieren (Probing).
Was ist lineares Sondieren?
Beim linearen Sondieren wird** bei einer Kollision der nächste freie Speicherplatz gesucht**, indem linear durch die Hashtabelle iteriert wird.
Was ist quadratisches Sondieren?
Quadratisches Sondieren verwendet eine quadratische Funktion, um den nächsten Speicherplatz zu finden, wenn eine Kollision auftritt.
Was ist doppeltes Hashing?
Beim doppelten Hashing wird eine** zweite Hashfunktion verwendet**, um bei einer Kollision den nächsten Speicherplatz zu berechnen.
Was ist der Belegungsfaktor (Load Factor) einer Hashtabelle?
Der Belegungsfaktor ist definiert als das Verhältnis der belegten Speicherplätze zur Gesamtzahl der verfügbaren Plätze in der Hashtabelle.
Was ist das Geburtstagsparadoxon im Kontext von Hashtabellen?
Das Geburtstagsparadoxon beschreibt, dass bei einer begrenzten Anzahl von möglichen Hashwerten bereits nach relativ wenigen Einträgen die Wahrscheinlichkeit für eine Kollision signifikant steigt.
Was ist die Modulo-Hashfunktion?
Eine Modulo-Hashfunktion berechnet den Hashwert durch Division des Schlüssels k durch die Tabellenlänge m und Verwendung des Restwerts als Hashwert H(k) = k mod m.
Was ist Cuckoo-Hashing?
Cuckoo-Hashing verwendet zwei Hashfunktionen und zwei Hashtabellen, um Kollisionen zu vermeiden. Falls beide Positionen belegt sind, wird ein bereits gespeicherter Wert verschoben.
Was ist der Unterschied zwischen einer Hashtabelle und einem binären Suchbaum (BST)?
Eine Hashtabelle ermöglicht konstante Zeitoperationen O(1) für Einfügen, Suchen und Löschen, während ein binärer Suchbaum geordnete Operationen mit einer garantierten Worst-Case-Zeit von O(log n) ermöglicht.
Welche Anwendungen haben Hashfunktionen?
Hashfunktionen werden in vielen Bereichen eingesetzt, z. B. in Adjazenzlisten von Graphen, Symboltabellen in Compilern, Datenbankindizes und kryptographischen Anwendungen wie digitale Signaturen und Passwortspeicherung.
