12
PI (Fach) / Hashing (Lektion)
Hashing
Diese Lektion wurde von blace erstellt.
Diese Lektion ist leider nicht zum lernen freigegeben.
Anzeige
- Was ist Hashing und was ist die Motivation dafür? Motivation: Die Suche in sortierten Sammlungen O(log n) Der zugriff auf den Array-Index O(1) wünschenswert - Array-Index berechnen aus Suchwert - dann direkter Zugriff Mögliche Lösung ist Hashing Hashing ist ein Streuspeicherverfahren Eine Hash-Funktion ist eine Abbildung von Werten auf ganze Zahlen(HashCode), dieser hashcode wird asl Schlüssel verwendet Eine Hash Tabelle ist ein Array(oder andere Sammlung mit direktem ZUgriff) und hat den HashCode als Index
- Was ist eine Hash-Funktion und welche Ziele soll sie unterstützen? Gib ein Beispiel an. Eine Hash Funktion ist die Abbildung von Werten auf ganze Zahlen (HashCode), dabei wird dieser hashcode als Schlüssel verwendet. Bsp:Datenbank von Mitarbeitenden der HashCode ist der erste Buchstabe des Nachnamens und seine Position im Alphabet Also Doris Bach -> 2 Anton Wagner -> 23 diese können dann in eine Hash Tabelle eingefügt werden
- Wie wird das Berechnen eines Hash-Codes in Java unterstützt? Um den HashCode zu errechnen kann man in Java die Methode int hashCode() auf einer Object klasse anwenden, solange es kompatibel zur equals Methode ist.
- Was sind Kollisionen und wie wird damit umgegangen? Eine Kollision entsteht, wenn zwei Elemente den gleichen HashCode haben, also am gleichen Index in der Tabelle eingetragen werden würden. Damit umgegangen wird mittels einer Sondierfunktion, durch welche man den neuen Platz des Elementes, das die Kollision verursacht, finden kann.
- Was ist und wie funktioniert Verkettung von Überläufern? Eine Verkettung von Überläufern bedeutet, dass Elemente mit dem gleichen HashCode in der hashtabelle zu einer Überläuferliste hinzugefügt werden. Dieses Funktioniert indem: Die Suche mit dem INdex h(k) beginnt und dann den Eintrag und die Liste aller Überläufer durchsucht und falls gefunden zurückgibt. Wenn das Listenende erreicht wird wurde nichts gefunden. Das Einfügen mit Überprüfung auf Duplikate funktioniert indem falls keine gefunden wurden das element direkt bei h(k), oder am Ende der Überläuferliste eingefügt werden. Ohne Überprüfung auf Duplikate funktioniert es indem das element direkt bei Index h(k), oder am Anfang der Überläuferliste eingefügt wird. Das Löschen funktioniert, indem der Wert gesucht wird und, falls dieser in der hash Tabelle ist der erste Überläufer aus der Liste entfernt wird und in die Tabelle geschrieben wird, oder falls er in der Überläuferliste ist aus der Liste entfernt wird. der Aufwand ist O(n/m) bei Gleichverteilung
- Was ist und wie funktioniert direkte Verkettung von Überläufern? Bei einer direkten Verkettung sind alle Werte immer in der Überläuferliste, die Hashtabelle ist hier im Prinzip nur ein Zeiger und erst die zweiten und folgenden Überläufer sind tatsächliche Überläufer. Diese art der Verkettung ist einfacher zu Implementieren und verschwendet weniger Platz, braucht aber insgesamt mehr Platz und hat einen langsameren Zugriff. Die Überläufer können eine beliebige Dtanstruktur verwenden.
- Was ist offenes Hashing? Offenes Hashing bedeutet, dass alle Werte direkt in der hash tabelle sind um Zeit und Speicher zu sparen. Hierfür wird bei Kollision, mittels Sondierung, ein Ausweichplatz gesucht.
- Welche Sondierungsarten haben wir kennengelernt? Erläutere mindestens eine. Es gibt Lineares Sondieren Quadratisches Sondieren Doppeltes hashing
- Wie funktioniert lineares Sondieren? Erläutere die Arbeitsweise an einem Beispiel. Beim linearen sondieren durchsucht man die hash Tabelle linear - h(k), h(k)-1, h(k-2),....,0, m-1,...., h(k)+1 Sondierungsfunktion: - s(j,k) = j - j-ter Versuch (initial 0) vollständige Hashfunktion: (h(k) -s(j,k)) mod m Bsp. m = 7 h(k) = k mod m s(j,k) = j einfügen 12 | (12-0)mod 7 = 5 Einfügen 53 | (53 -0) mod 7 = 4 Einfügen 5 | (5-0) mod 7 = 5 KOLLISION (5 -1) mod 7 = 4 KOLLISION (5-2) mod 7 = 3 usw. Belegunsfaktor alpha = Anzahl der belegten Elemente/m Nachteile - Häufungspunkte senken Effiziens (primäre Häufung) - Aufwand steigt extrem stark ab alpha = 80%
- Wie funktioniert quadratisches Sondieren? Erläutere die Arbeitsweise an einem Beispiel. Beim quadratischen Sondieren wird die Hash Tabelle quadratisch und alternatierend durchsucht. h(k), h(k)+1, h(k)-1, h(k) +4, h(k)-4 Sondierungsfunktion: s(j,k) = [j/2]^2 *(-1)^j Bsp: m=7 h(k) = k mod m s(j,k) = [j/2]^2 *(-1)^j Einfügen 12 || (5-0 mod 7 = 5 Einfügen 53 || (4-0) mod 7 = 4 Einfügen 5 || (5-0) mod 7 = 5 KOLLISION (5+1) mod 7 = 6 Einfügen 19 || (5-0) mod 7 = 5 KOLLISION (5+1) mod 7 = 6 KOLLISION (5-1) mod 7 = 4 KOLLISION (5+4) mod 7 = 2 Nachteil Synonyme behindern sich gegenseitig (sekundäre Häufung) Aufwand: lineares Sondieren● erfolglose Suche z.B. α=0.75: 8,5● erfolgreiche Suche z.B. α=0.75: 2,5 quadratisches Sondieren● erfolglose Suche z.B. α=0.75: 4,6● erfolgreiche Suche z.B. α=0.75: 2,0
- Anzeige
- Wie funktioniert doppeltes Hashing? Erläutere die Arbeitsweise an einem Beispiel. Beim doppelten Hashing wird, da sich Werte mit gleicher hash Funktion stören, mit der zweiten hash-Funktion sondiert. s(j,k) = j*h´(k) h(k), h(k)-h´(k), h(k)-2*h´(k),..., h(k)-(m-1)*h´(k) H´(k) darf dabei nicht =0, kein Teiler von m (optimalerweise ist m eine Primzahl) sein und muss unaäbhängig von h(k) sein. Eine Gute Wahl für h´(k) ist daher h´(k) = 1+k mod (m-2) falls m Primzahl. Bsp: m = 7 h(k) k mod m h´(k) = 1 + k mod (m-2) s(j,k) = j*h´(k) Einfügen 12 h(k) = 12 mod 7 = 5 h`(k) = 1+(12 mod 5) = 3 -> 5- 0*3 = 5 Einfügen 53 h(k) = 53 mod 7 = 4 h`(k) = 1+(53 mod 5) = 4 -> 5-0*4 = 5 ist bei 4 da keine KOLLISIOn Einfügen 5 h(k) = 5 mod 7 = 5 h`(k) = 1 +(5 mod 5) = 1 -> 5 - 0*1 = 5 KOLLISION 5 - 1*1 = 4 KOLLISION 5 - 2*1 = 3
- Was sind Vor- und Nachteile des jeweiligen Sondierungsverfahrens? Lineares Sondieren: Vorteile: Einfacher zu implementieren Nachteile: Häufungspunkte senken Effiziens (primäre Häufung) Aufwand steigt extrem stark ab alpha = 80% Quadratisches Sindieren: Vorteile: Weniger Aufwand/ schnelleres Sondieren Nachteile: Synonyme behindern sich geenseitig (sekundäre Häufung) Doppeltes hashing: Vorteile: