Hashing Flashcards
1
Q
Was ist direkte Adressierung?
A
- Man speichert ein Element mit dem Schlüssel k, im Array an Position k
- Bei gegebenen Schlüssel finden wir das Element schnell
- Ist anwendbar, wenn man ein Array anlegt, bei dem jede Position ein möglicher Schlüssel ist
- Wenn die Anzahl der möglichen Schlüssel deutlich größer ist als die Anzahl gespeicherter Schlüssel ist direkte Adressierung nicht Sinnvoll
2
Q
Was ist eine Hashtabelle?
A
- Ein Array, dessen Größe proportional zur Anzahl der zu speichernden Schlüssel ist
- Der Schlüssel k wird nicht als Index benutzt
- Es gibt eine Hashfunktion, welche mit dem Schlüssel k den Index berechnen kann
3
Q
Welche Operationen hat eine HashMap und welche Laufzeiten haben sie?
A
- Add, Delete, Search
- Alle eine Laufzeit von O(1)
- Unter der Vorraussetzung: Hashwerte gleichmäßg verteilt und gute Kollisionserkennung
4
Q
Welche zwei Arten mit Kollisionen umzugehen kennen wir?
A
- Verkettung (chaining): An dem Index wird nicht das Element gespeichert sondern eine Liste mit allen Elementen mit diesem Index
- offene Adressierung: Man hat zusätzlich einen laufindex und will man ein Element hinzufügen und es kommt zur Kollision erhöht man diesen und errechnet einen neuen Hashwert bis es keine Kollision mehr gibt
5
Q
Wie sind die Laufzeiten der Operation bei einer HashMap mit Verkettung?
A
- Einfügen O(1), wenn man davon ausgeht, dass das Element nicht in der Liste ist sonst muss man suchen
- Suche: Laufzeit proportional zur Länge der Liste mit Elementen in dem Slot. Worst-Case Θ(n). Durchschnittlicher Fall Θ(1 + α) wobei α = n/m
- Löschen: doppeltverkette Liste O(1) bei einfach verketteter Liste genau so lange wie bei Search
6
Q
Welche Methoden gibt es um eine Hashfunktion zu erstellen?
A
- Divisions und Multiplikationsmethode
- Divisionsmethode ist schneller aber die größe der HashMap kann nur bestimmte Werte annehmen und ist m = 2^x hängt der Hashwert nicht mehr von allen Bits ab
- Multiplikationsmethode ist langsamer dafür ist der Wert von m nicht kritisch
7
Q
Wie funktioniert das Suchen/Einfügen und Löschen in eine HashMap bei offener Adressierung?
A
- Zu Beginn hat man einen index auf 0
- Danach berechnet man den Hashwert mit dem key und dem index
- Ist der slot dann schon belegt, erhöhe den Index um eins und errechne erneut den Hashwert
- Mache solange bis man einen leeren Slot hat beim einfügen oder bis man das gewünschte Element hat beim suchen
- Löschen ist nicht direkt möglich, da es die Such-Liste zerstören würde
- Stattdessen markiert man den Slot als DELETED
8
Q
Welche Arten von Sondierungen gibt es?
A
- Lineares sondieren, welches das Problem von Clustering hat
- Die durchschnittliche Suchzeit steigt schnell an
- Doppeltes Hashing mit zwei Hashfunktionen
- Diese Methode gibt gute Ergebnisse
- Quadratosche Sondierung, welches das Problem des Sekundären Clustering hat
9
Q
Wann sollte man HashMaps mit offener Adressierung nicht nutzen?
A
Anwendung von offener Adressierung in der Regel nur wenn Entfernen nicht benötigt wird
10
Q
Warum benutzt man Universelles Hashing?
A
- Egal wie wir die Hashfunktion bilden, es gibt immer eine Reihe von Schlüsseln, die die mittlere Zugriffszeit in die Höhe schießen lässt
- Durch Univerelles Hashing und dem einfügen eines randomizierten Elements umgeht man das
- Die Idee ist dabei: Wähle die Hash-Funktion nach dem Zufallsprinzip, unabhängig von dem Schlüssel
11
Q
Wie funktioniert Universelles Hashing?
A
- Bei jeder Verwendung wird eine zufällige Hashfunktion aus einer Gruppe von Hashfunktionen benutzt
- Die Hashfunktionen in dieser Familie sind so konstruiert, dass sie für jede Eingabe eine zufällige Verteilung von Hashwerten erzeugen
- Die Familie von Hashfunktionen kann durch eine zufällige Auswahl von Koeffizienten und einer Konstante erzeugt werden
12
Q
Was ist perfektes Hashing?
A
- Hashing ohne, dass Kollisionen auftauchen
- Die Idee hinter Perfektem Hashing besteht darin, eine spezielle Hash-Funktion zu finden, die für eine bestimmte Menge von Schlüsseln eine perfekte Hash-Tabelle generiert
13
Q
Wie wird perfektes Hashing umgesetzt?
A
- Wir haben zwei Hashtabellen und zwei Hashfunktionen mit jeweils anderen Parametern
- Die erste Hashfunktion bestimmt den Slot in der ersten Tabelle
- Die zweite bestimmt den Slot der zweiten Tabelle
- Dabei werden in der Tabelle
