Informatik Datenstrukturen – Hashtabellen und Kollisionen
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Was ist eine Hashtabelle? · Welche Eigenschaften muss eine gute Hashfunktion erfüllen?
Karten
15 KartenWas ist eine Hashtabelle?
Rückseite
Ein assoziatives Array, das Schlüssel über eine Hashfunktion auf Array-Indizes abbildet und Werte in Buckets speichert.
Welche Eigenschaften muss eine gute Hashfunktion erfüllen?
Rückseite
Deterministisch, gleichverteilend (uniform), schnell berechenbar und minimiert Kollisionen für typische Eingabedaten.
Was ist eine Kollision bei Hashtabellen?
Rückseite
Zwei verschiedene Schlüssel erzeugen denselben Hashwert und sollen daher im selben Bucket gespeichert werden.
Wie funktioniert Separate Chaining zur Kollisionsbehandlung?
Rückseite
Jeder Bucket enthält eine verkettete Liste (oder einen Baum); kollidierende Einträge werden dort angehängt.
Wie funktioniert Open Addressing zur Kollisionsbehandlung?
Rückseite
Bei Kollision wird über eine Sondierfolge (Probing) ein freier Slot im Array selbst gesucht und genutzt.
Was unterscheidet Linear Probing von Quadratic Probing?
Rückseite
Linear prüft i, i+1, i+2...; Quadratic nutzt i, i+1², i+2²... – reduziert primäres Clustering.
Was ist Double Hashing und welchen Vorteil hat es?
Rückseite
Zweite Hashfunktion bestimmt Schrittweite h2(k); vermeidet sekundäres Clustering besser als quadratisches Probing.
Wie wird der Lastfaktor α einer Hashtabelle berechnet?
Rückseite
α = n / m, wobei n die Anzahl gespeicherter Elemente und m die Tabellengröße (Anzahl Buckets) ist.
Wann sollte Rehashing (Vergrößerung) bei Open Addressing durchgeführt werden?
Rückseite
Bei Erreichen eines Schwellwerts (typisch α > 0,7), um Suchzeiten niedrig zu halten.
Wie ist die durchschnittliche Laufzeit für Suche, Einfügen und Löschen in einer Hashtabelle?
Rückseite
O(1) amortisiert, vorausgesetzt gute Hashfunktion und Lastfaktor α bleibt durch Rehashing konstant.
Wie sieht der Worst Case für Suchoperationen aus und wann tritt er auf?
Rückseite
O(n), wenn alle Schlüssel in denselben Bucket hashen (schlechte Hashfunktion oder gezielte Angriffe).
Was ist primäres Clustering bei Linear Probing?
Rückseite
Aufeinanderfolgend besetzte Slots bilden Blöcke, die Suchwege für neue Einträge verlängern.
Welchen Speicherbedarf hat Separate Chaining gegenüber Open Addressing?
Rückseite
Chaining braucht zusätzlichen Zeigerspeicher für Listen; Open Addressing nur das reine Array, aber Tombstones für Löschungen.
Wie löscht man Einträge korrekt bei Open Addressing?
Rückseite
Markierung als Tombstone (gelöscht), damit Sondierfolgen für spätere Suchen nicht unterbrochen werden.
Nenne drei typische Anwendungen von Hashtabellen in der Praxis.
Rückseite
Programmiersprachen-Dictionaries (Python dict, Java HashMap), Datenbank-Indizes, Caches (Browser, CPU, Memcached).