Sommer Sitzung 06

Softwaretechnologie: Java (Teil II, Sommersemester), Notizen zu Sitzung 6

Thema	Stichworte	Material ___________________________
Überblick	Eine schnelle, praktische Datenstruktur: Hash-Tables	Beispiele und Literatur: Home
Datenstrukturen	Wozu Datenstrukturen? – Elemente spreichern, verwalten, abrufen; wie bisher? – z.B. Arrays, verk. Listen, Queue, Stack; Effizienz von bisherigen Datenstrukturen? – Arrays Zugriff? – O(1); Arrays einfügen? – O(n); Verk. Listen Zugriff? – O(n); Verk. Listen Einfügen? – Queue, Stack? – O(1); was wäre die perfekte Datenstruktur für viele Fälle? – O(1) für Einfügen, Löschen und Abrufen (quasi Vorteile von Array und verkettete Listen in Einem: schnelles Einfügen, schnelles Abrufen, schnelles Löschen); damit Abschluss Grundlagen Suchen und Datenstrukturen	—
Direktzugriff	Arrays haben grundsätzlich das Verhalten das wir uns wünschen: wir können in O(1) einen Wert setzen und abfragen, wenn wir nach dem Index suchen; wie auf diese Weise z.B. Personen speichern? – wenn unsere Elemente eine numerische ID/Key/Schlüssel haben, können wir die ID als Index in einem Array verwenden; z.B. Studenten mit fortlaufenden Matrikelnummern: Student Nr. 1 an Index 1 des Arrays, etc.; wenn wir Student 5 suchen können wir direkt auf das Array an Stelle 5 zugreifen und haben den Studenten; d.h. Direktzugriff statt Suche; Problem? – 1.) nicht-numerische keys; 2.) Speicherverschwendung, U(niverse) vs. K(eys); Implementierung s. Code
Hash-Tables	Idee für beide Probleme? – statt Element mit Schlüssel k an slot k zu speichern, berechnen wir den slot aus k mit der Hash-Funktion h; so mappen wir das Universum U der Werte für k auf die m slots einer Hash-Table, so Menge der Indizes reduzieren, Platz sparen; zudem ist so das Input-Format des Schlüssels prinzipiell unabhängig von der internen numerischen Repräsentation des Index	—
Kollisionen	U ist grösser als K, d.h. es gibt mehr Schlüssel k als Indizes m; wenn wir alle Werte auf Indizes mappen, was muss passieren? – Irgendwann muss für zwei Schlüssel mal der gleiche Index vergeben werden, weil U > K; was dann? – 1.) chaining, aka. closed hashing: am Index ist nicht der Wert direkt, sondern eine verkettete Liste mit den verschiedene Elementen (die alle verschiedene keys haben, und so unterschieden werden, s.u.); 2. open adressing aka. open hashing: alle Werte direkt in Table, bei Kollisionen ungenutzte Felder nehmen (s.u.)
Open-Adressing: Idee und Problem	Alles direkt in Table, keine Listen, keine Pointer; stattdessen: Sequenz aus key berechnen, gut: spart Speicher, potentziell schneller; Problem beim Löschen: einfach null würde später eingefügte Werte unfindbar machen; special case: deleted, als freien Platz behandeln, Suchzeit aber dann nicht mehr abhängig von load factor a; deshalb: wenn delete nötig, eher Chaining verwenden; für Sequenzberechnung wieder verschiedene Ansätze, Thema für sich, s. Literatur bei Interesse	—
Chaining: Implementierung	put, get; s.Code; Impl. Hash-Funktion s.u.
Chaining: Laufzeit	Worst case? – alle n keys hashen zum selben slot, d.h. wir haben eine Liste der Länge n; d.h. statt Hash-Table haben wir? – eine verkettete Liste, mit entsprechender Laufzeit: O(n); d.h. wovon hängt eine optimale Laufzeit ab? – von einer gleichmässigen Verteilung der keys auf die slots; von kleinem load factor a; m slots, n elements; load factor a = n / m, d.h. a = durchschnittliche Zahl von Elementen in einer Liste; z.B. 6 slots, 2 elem.: a = 2/6 = 1/3; oder 2 slots, 6 elem.: a = 6/2 = 2; Annahme zur Analyse: Gleichverteilung (simple uniform hashing); Laufzeit für search: O(1+a), d.h. Hash-Funktion + durchschnittliche Länge der Listen; wenn Zahl der slots m mindestens proportional zu Anzahl der Elemente n steigt, ist alles optimal verteilt: n = O(m); und deshalb a = n/m = O(m)/m = O(1); weil auch put O(1) alle Dictionary-Operationen in O(1)	—
Hash-Funktionen	Grundlegende Hash-Funktion, wie größere Werte auf kleinere Tabelle mappen? – Restwert bei Teilen durch Länge der Table (s.Code); durch großen Wert/Tabelle: viel ungenutzt (s.o.: 2/6); kleiner Wert: engerer Bereich, mehr Kollisionen (s.o.: 6/2); Ideale Hash-Funktion setzt Forderung nach Gleichverteilung auf slots um und ist schnell; spezielle Anforderungen, z.B. häufig ähnliche Symbole im Compiler (pt, pts); hier gutes Hashing um zu verhindern dass solche Ähnlichkeiten zu gleichen slots führen; d.h. für Bsp. schlecht? – nur erste 2 Zeichen; Generelle Idee: möglichst unabhängig von anderen Mustern in den Daten; Hash-Codes für Index numerisch, andere Sachen konvertieren, z.B. Strings: Zeichen als Index im ASCII-Zeichensatz; konkrete Umsetzungstechniken eine Wissenschaft für sich, s. Literatur bei Interesse	—
Hashing in der Praxis: Grundlegend	Praxisrelevant warum? – wir programmieren i.d.R keine Hash-Tables, aber wir implementieren Objekte, die in solchen Datenstrukturen abgelegt werden; d.h.? – wir müssen für unsere Objekte Hash-Codes berechnen und liefern; Object in Java hat hashCode Funktion; hier für eigene Objekte einklinken (damit solche Datenstrukturen, die Hash-Codes verwenden gut arbeiten können)	—
Hashing in der Praxis: Object#equals	Wie in Java Identität überprüfen? – z.B. int? – == und !=; wie bei Objektreferenzen, z.B. Strings? – equals(); was ist mit eigenen Klassen? – z.B. new Person("Jim").equals(new Person("Jim")), was passiert? – sind nur gleich wenn wir equals implementieren; intern hier z.B. den Namen vergleichen; welcher Typ ist Input für equals in Java? – Object, d.h. Vorsicht beim Implementieren: Parameter muss stimmen und wir müssen casten; grundlegende Anforderung in Java: wenn equals überschrieben wird, muss auch hashCode überschrieben werden (Gründe s.u.)	—
Hashing in der Praxis: Object#hashCode	Anforderungen an hashCode in Java (contract der Methode) sind 1.) deterministisch für laufendes Programm; 2.) wenn zwei Objekte laut equals gleich, dann auch gleiche Hash-Codes; 3.) wenn zwei Objekte !equal muss Hash-Code nicht unterschiedlich sein; aber warum sinnvoll? – unterschiedliche Objekte sollen ja gleichmäßig auf die Hash-Table verteilt werden; wenn man equals aber nicht hashCode überschreibt, welcher Punkt verletzt? – Nr. 2: Sachen können über equals gleich sein, aber laut Object#hashCode sind sie unterschiedlich; was passiert wenn man solche Objekte in einer Hash-Table als Key verwendet? – z.B. table.put(new Person("Jim")) und dann table.get(new Person("Jim")); warum finden wir ihn nicht? – es wird an falscher Stelle in der Hash-Table gesucht, weil die Hash-Codes unterschiedlich sind	—
Hashing in der Praxis: Implementierung	Erster Ansatz: einfachster Fall, der contract von hashCode erfüllt? – fester Wert für Objekte einer Klasse, z.B. 42; Laufzeitverhalten? – worst case: alles in einer Liste; Ziel hingegen: gleichmäßig verteilen, für unterschiedliche Objekte unterschiedliche Hash-Codes; Rezept für die Praxis: alle Werte berücksichtigen die in equals berücksichtigt wurden: boolean 1 oder 0, Zahl als Zahl lassen (s. Details Literatur), Objekte wieder hashCode aufrufen, Arrays jedes Element; alle so berechneten c über result (Startwert nicht 0: z.B. int result = 17) so kombinieren: result = 31 * result + c; so kombiniert man die charakteristischen Werte auf deterministische Weise; was ohne Multiplikation z.B. bei String? – alle Anagramme gleiche Hash-Codes; 31 u.A. weil Multiplikation effizient über Bit-Shift, von VM intern automatisch optimiert; in Theorie gibt es bessere Verfahren, aber praktisch heute so state of the art; Vorsicht vor falscher Optimierung: Sachen weglassen nicht gut: schnellere hashCode-Berechnung, aber Hash-Table nicht ausgenutzt (früher nahm z.B. String#hashCode in Java nur wenige Zeichen aus dem String, Problem mit URLs als Strings in Hash-Tables); Implementierung s. Code	—
Anwendungsbeispiel: Wörter zählen	Wie mit Hash-Table Wörter zählen? – Über Text gehen, in Table unter Wort als Key seine Häufigkeit speichern; immer Häufigkeit abfragen, hochzählen, ablegen; Wörter zählen damit was für eine Komplexität? – O(n) für n Wörter prüfen * O(1) für Verwendung der Hash-Table, d.h. Klasse O(n); Implementierung s. Code	—
Hausaufgabe	Anwendung Wörterbuch; Visualisierung Graphviz; Klasse mit equals und hashCode	Sommer-Aufgabe-05