Die (sogenannte) Symboltabelle
Id: symtab.tex,v 1.1 2004/01/05 14:12:41 joe Exp
(eigentlich ist es die Tabelle für Bezeichner)
(Wdhlg.) Tokenklassen:
Inhalt der Symboltabelle
wichtige Attribute der Bezeicher aufbewahren:
Symboltabellen als Abbildungen
Id: map.tex,v 1.1 2004/01/05 14:12:41 joe Exp
Abstrakter Datentyp Map (Abbildung)
interface Map(A, B) { void clear (); void put (A key, B value); B get (A key); void remove (A key); }(anderer Name: Wörterbuch (Dictionary) -- warum ist das inzwischen ``deprecated''?)
Abbildungen in Java
Map
ist ein Typkonstruktor
( Typ höherer Ordnung, wenn und Typen sind, dann ist ein Typ),
aber man darf das in Java nicht hinschreiben. Deswegen (http://java.sun.com/j2se/1.4.2/docs/api/java/util/Map.html):
interface Map { void clear (); void put (Object key, Object value); Object get (Object key); void remove (Object key); }und man muß fleißig casten:
Entry e = (Entry) table.get ("foo");
Das Fehlen von Typen höherer Ordnung
...ist eine schwerwiegende Lücke in vielen gängigen Sprachen (die besonders beim Umgang mit Collections, Containern usw. schmerzt).
Mehr oder wenig zaghafte Versuche, um diese Lücke herumzuturnen, heißen dann Casts, Templates (C++, Java 1.5), Design Patterns usw.
und erfordern dann eigene Vorlesungen, Lehrbücher, Hilfsprogramme (sog. CASE-Tools), Zaubersprüche und Gurus
( und schaffen auf diese Weise immerhin Umsatz und Arbeitsplätze).
Abbildungen: mögliche Implementierungen
Aufgabe (Wdhlg 1. Semester, hoffe ich): diskutiere (für alle 6 Varianten) die Laufzeiten für die o. g. Operationen.
Beispiel: ungeordnete Liste:
put
ist nur eine Operation, also , konstant
get
muß alle Einträge betrachten, also , linear
benutze schnelle Hashfunktion
Idee: Speichere in .
Parameter (Tabellengröße, Hashfunktion) geeignet wählen, dann ``praktisch konstante'' Laufzeit für alle Operationen.
Hash-Kollision: und .
ist schon in , wo soll hin?
Kollisionen behandeln:
Nachteil: Extraplatz für Listenzeiger
Nachteil: Tabelle ,,verklebt``
(belegte Blöcke erzeugen weitere Kollisionen)
Vorteil: kein Verkleben (Schrittweiten sind verschieden!)
Aufgabe: Pseudocode für Einfügen und Suchen bei doppeltem Hashing. was ist mit Löschen?
Re-Hashing
Id: rehash.tex,v 1.1 2004/01/05 14:12:41 joe Exp
Problem:
Lösung: falls Tabelle gewissen Füllstand erreicht, dann zu neuer, größerer Tabelle wechseln ( re-Hashing).
am einfachsten: Tabellengröße ist immer Potenz von 2; dann: vergrößern verdoppeln.
Beim re-Hashing müssen alle Einträge betrachtet werden, das findet aber nur selten statt, so daß die amortisierte Laufzeit trotzdem konstant ist (Aufgabe: nachrechnen).